Applied Mathematics
Vol.10 No.11(2019), Article ID:96315,9 pages
10.4236/am.2019.1011066
LPT Algorithm for Jobs with Similar Sizes on Three Machines
Yajie Ma1, Rongheng Li1*, Yunxia Zhou2
1Key Laboratory of Computing and Stochastic Mathematics (Ministry of Education), School of Mathematics and Statistics, Hunan Normal University, Changsha, China
2College of Information Science and Engineering, Hunan Normal University, Changsha, China
Copyright © 2019 by author(s) and Scientific Research Publishing Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
Received: October 18, 2019; Accepted: November 8, 2019; Published: November 11, 2019
ABSTRACT
In this paper, LPT (largest processing time) algorithm is considered for scheduling jobs with similar sizes on three machines. The objective function is to minimize the maximum completion time of all machines. The worst case performance ratio of the LPT algorithm is given as a piecewise linear function of r if job sizes fall in . Our result is better than the existing result. Furthermore, the ratio given here is the best. That means our result cannot be improved any more.
Keywords:
LPT Algorithm, Parallel Machine, Performance Ratio, Schedule
1. Introduction
The scheduling problem on m parallel identical machines is defined as follows: Given a job set of n jobs where job has non-negative processing time , assign the jobs on m machines so as to minimize the maximum completion times of the jobs on each machine. Since scheduling problem was proposed by Graham [1], it has been studied extensively in many varieties and from many viewpoints. In classic scheduling problem, there is no constraint on the size of jobs. However, in practice, the size of job can neither be too large nor too small. This motivates researchers to study scheduling problems in which the sizes of all jobs fall in with . Researches of such model can be found in [2] - [9] to name a few.
LPT (Largest Processing Time) algorithm is a famous algorithm proposed by Graham [10]. For a given job list of n jobs, LPT algorithm firstly sorts the jobs with a non-increasing order of their sizes. Then LPT algorithm assigns the jobs one by one according to the non-increasing order and always assigns the current job to the machine with least load. The worst case
performance ratio of LPT is . H.Kellerer [9] gave the following result.
where ,, ( ). For , the bound of is tight. We use with instead of . Then the tight interval for r is in Kellerer’s result. In this paper, we will give the tight bound as a piecewise linear function of r for and all .
2. Theorem and Its Proof
Before the analysis, we give some symbols used later on.
1) represents the size of the j-th job assigned on machine by LPT algorithm.
2) .
3) .
4) represent the makespan of optimal algorithm and LPT algorithm, respectively.
In the following of this paper, for a given job list , we always assume and .
Lemma 1 If , then in LPT schedule, the difference of the numbers of jobs on any two machines is at most 1.
Proof: If it is not true, suppose it is the first time that there are k jobs assigned on and there are jobs assigned on in the LPT schedule, then we have
Hence we get
By the assumption that this is the first time of appearing the case, we have for . That means
This is a contradiction to .
By Lemma 1, we can conclude that for any in the LPT schedule.
Theorem 2. For any job list and , we have
where k is non-negative integer. Furthermore the bound is tight.
Proof: Case 1: . For any , Graham [10] proved that
and the quality can hold. We get the conclusion by letting .
For , if the theorem is not true, then there is a job list with minimal n such that L violates the theorem. We call such a job list as a minimal counter example. For a minimal counter example, it is easy to show that the last job is finished at last. Hence we have
(1)
Case 2: .
In this case, we should prove
(2)
If (2) is not true, by (1) we get
That means
Hence we get .
Case 2.1: .
In this case we have ,,. It is easy to see that there exists satisfying . Without loss of generality, suppose , then . Therefore we get
Similarly we can get (2) for the case of .
Case 2.2: .
Let ,,, or ,. At any case holds and there exists satisfying . W.l.o.g, suppose , then . Hence we get
where the last two inequalities result from the facts that function and are increasing function of x. Similarly we can get (2) for the case of .
Case 3: .
In this case, if the claim is not true, then by (1) there is a the minimal counter example L satisfying
Hence we get
That means . By the proof of Case 2 we get
Case 4: .
In this case, if the claim is not true, then by (1) there is a the minimal counter example L satisfying
Hence we get
That means .
Case 4.1: .
In this case we have ,,. It is easy to see that there exists satisfying . W.l.o.g, suppose . That means . Hence we get
where the last inequality results from the fact that is a decreasing function of x.
Similarly we can show that the claim is true for the cases of .
Case 4.2: .
In this case, let ,. If There exists satisfying , w.l.o.g, suppose , then we have . Therefore we get
If , it is easy to see that there exists satisfying . Then we get the claim is true by above discussion.
If , we also get the claim is true by above discussion.
If , then there exists satisfying , w.l.o.g, suppose , then . Hence we get
where the last inequality results from the fact that is a decreasing function of x.
Case 5: .
In this case we should prove
If it is not true, then by (1) the minimal counter example satisfies
Hence we get
That means . By the proof of Case 4 we get
By the above discussions of Case 1-5, the inequality in Theorem 2 is proved.
Now we prove the tightness of the inequalities. For , let with ,,. Then ,,,,. Hence we get
(3)
For . let with ; ,. Then we have ,,,. Hence we get
(4)
For , let with ,. Then we have ,, , . Hence we get
(5)
For, let with , , , . Then we have, , , ,. Hence we get
(6)
Hence Theorem 2 is proved.
3. Conclusion and Future Work
In this paper, LPT algorithm is considered for the scheduling jobs with similar sizes in on three machines. The objective function is to minimize the maximum completion time of all machines. The worst performance ratio of the LPT algorithm is given as a piecewise linear function of r. The result is better than the existing result and cannot be improved any more. It is interesting to consider general number of machines and give tight bound of worst case performance.
Acknowledgements
The authors would like to express their thanks to the National Natural Science Foundation of China for financially supporting under Grant No. 11471110 and the Foundation Grant of Education Department of Hunan (No. 16A126).
Conflicts of Interest
The authors declare no conflicts of interest regarding the publication of this paper.
Cite this paper
Ma, Y.J., Li, R.H. and Zhou, Y.X. (2019) LPT Algorithm for Jobs with Similar Sizes on Three Machines. Applied Mathematics, 10, 947-955. https://doi.org/10.4236/am.2019.1011066
References
- 1. Graham, R.L. (1969) Bounds on Multiprocessing Timing Anomalies. SIAM Journal on Applied Mathematics, 17, 416-429. https://doi.org/10.1137/0117039
- 2. Cheng, T.C.E., Kellerer, H. and Kotov, V. (2012) Algorithms Better than LPT for Semi-Online Scheduling with Decreasing Processing Times. Operations Research Letters, 40, 349-352. https://doi.org/10.1016/j.orl.2012.05.009
- 3. He, Y.G. (2005) Semi-Online Scheduling Jobs with Tightly-Grouped Processing Times on Three Identical Machines. Discrete Applied Mathematics, 150, 140-159. https://doi.org/10.1016/j.dam.2004.12.005
- 4. He, Y. and Zhang, G. (1999) Semi On-Line Scheduling on Two Identical Machines. Computing, 62, 179-187. https://doi.org/10.1007/s006070050020
- 5. Kellerer, H., Kotov, V., Speranza, M.G. and Tuza, Z. (1997) Semi On-Line Algorithms for the Partition Problem. Operations Research Letters, 21, 235-242. https://doi.org/10.1016/S0167-6377(98)00005-4
- 6. Li, R.H. and Huang, H.C. (2007) List Scheduling for Jobs with Arbitrary Release Times and Similar Lengths. Journal of Scheduling, 10, 365-373. https://doi.org/10.1007/s10951-007-0042-8
- 7. Lin, L. and Tan, Z. (2014) Inefficiency of Nash Equilibrium for Scheduling Games with Constrained Jobs: A Parametric Analysis. Theoretical Computer Science, 521, 123-134. https://doi.org/10.1016/j.tcs.2013.11.012
- 8. He, Y. and Dosa, G. (2005) Semi-Online Scheduling Jobs with Tightly-Grouped Processing Times on Three Identical Machines. Discrete Applied Mathematics, 150, 140-159. https://doi.org/10.1016/j.dam.2004.12.005
- 9. Kellerer, H. (1991) Bounds for Non-Preemptive Scheduling Jobs with Similar Processing Times on Multiprocessor Systems Using LPT-Algorithm. Computing, 46, 183-191. https://doi.org/10.1007/BF02238297
- 10. Graham, R.L. (1976) Bounds on the Performance of Scheduling Algorithms, Computer and Job-Shop Scheduling Theory. John Wiley Sons, New York, 165-227.