Share This Article:

LPT Algorithm for Jobs with Similar Sizes on Three Machines

Abstract Full-Text HTML XML Download Download as PDF (Size:400KB) PP. 947-955
DOI: 10.4236/am.2019.1011066    103 Downloads   232 Views  

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 [1, r]. 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.

1. Introduction

The scheduling problem on m parallel identical machines is defined as follows: Given a job set L = { J 1 , J 2 , , J n } of n jobs where job J j has non-negative processing time p j , assign the jobs on m machines { M 1 , M 2 , , M m } 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 [ 1, r ] with r 1 . 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 L = { J 1 , J 2 , , J n } 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 4 3 1 3 m . H.Kellerer [9] gave the following result.

R ( m , L P T , μ ) ( m ( 2 k 2 ) μ ( k 2 ) k m for μ [ 1 + m ( k 3 ) k 2 , m ( k 2 2 k 2 ) + k ( k 2 ) ( k + 1 ) ] ( k + 2 ) m 1 ( k + 1 ) m for μ [ m ( k 2 2 k 2 ) + k ( k 2 ) ( k + 1 ) , 1 + m ( k 2 ) k 1 ]

where k 3, k N , p 1 p n = 2 μ m , ( 1 μ < m , μ R ). For μ ( m + 3 ) / 4 ( k = 3 ) , the bound of ( 4 m μ ) / 3 m is tight. We use p j [ 1, r ] with r 1 instead of p 1 p n = 2 μ m . Then the tight interval for r is [ 3 2 , 5 3 ] in Kellerer’s result. In this paper, we will give the tight bound as a piecewise linear function of r for m = 3 and all r 1 .

2. Theorem and Its Proof

Before the analysis, we give some symbols used later on.

1) p i ( j ) represents the size of the j-th job assigned on machine M i by LPT algorithm.

2) S i = { j n | J j is assigned on machine M i by L P T algorithm } .

3) S i * = { j | J j is assigned on machine M i by optimal algorithm } .

4) C max L P T , C max O P T represent the makespan of optimal algorithm and LPT algorithm, respectively.

In the following of this paper, for a given job list L = { J 1 , J 2 , , J n } , we always assume p 1 p 2 p n and 1 p j r , j = 1 , 2 , , n .

Lemma 1 If r < 2 , 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 M h and there are k + 2 jobs assigned on M i in the LPT schedule, then we have

s = 1 k p h ( s ) s = 1 k + 1 p i ( s ) .

Hence we get

p h ( 1 ) s = 1 k 1 ( p i ( s ) p h ( s + 1 ) ) + p i ( k ) + p i ( k + 1 )

By the assumption that this is the first time of appearing the case, we have p i ( s ) p h ( s + 1 ) for s = 1 , 2 , 3 , , k 1 . That means

p h ( 1 ) p i ( k ) + p i ( k + 1 ) 2.

This is a contradiction to r < 2 .

By Lemma 1, we can conclude that p i ( s ) p h ( s + 1 ) for any 1 i , h m in the LPT schedule.

Theorem 2. For any job list L = { J 1 , J 2 , , J n } and m = 3 , we have

C max L P T ( L ) C max O P T ( L ) ( 11 9 ; r [ 5 3 , + ) , ( 2 k + 1 ) r + k + 2 3 k + 3 ; r [ ( 2 k + 3 ) ( 3 k + 2 ) ( 2 k + 1 ) ( 3 k + 4 ) , 6 k + 5 6 k + 3 ) , 9 k + 14 3 ( 3 k + 4 ) ; r [ 3 k + 4 3 ( k + 1 ) , ( 2 k + 3 ) ( 3 k + 2 ) ( 2 k + 1 ) ( 3 k + 4 ) ) , 2 ( k + 1 ) r + k + 2 3 k + 4 ; r [ 1 + 3 k + 4 9 ( k + 1 ) ( k + 2 ) , 3 k + 4 3 ( k + 1 ) ) , 9 k + 20 9 ( k + 2 ) ; r [ 6 ( k + 1 ) + 5 3 [ 2 ( k + 1 ) + 1 ] , 1 + 3 k + 4 9 ( k + 1 ) ( k + 2 ) ) , 1 ; r = 1 ,

where k is non-negative integer. Furthermore the bound is tight.

Proof: Case 1: r 5 3 . For any m 1 , Graham [10] proved that

C max L P T ( L ) C max O P T ( L ) 4 3 1 3 m

and the quality can hold. We get the conclusion by letting m = 3 .

For r < 5 3 , if the theorem is not true, then there is a job list L = { J 1 , J 2 , , J n } 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 J n is finished at last. Hence we have

C max L P T ( L ) C max O P T ( L ) L 1 + L 2 + L 3 + 3 p n 3 C max O P T ( L ) j = 1 n p j + 2 p n 3 C max O P T ( L ) 1 + 2 p n 3 C max O P T ( L ) , (1)

Case 2: ( 2 k + 3 ) ( 3 k + 2 ) ( 2 k + 1 ) ( 3 k + 4 ) r < 6 k + 5 3 ( 2 k + 1 ) .

In this case, we should prove

C max L P T ( L ) C max O P T ( L ) ( 2 k + 1 ) r + k + 2 3 k + 3 . (2)

If (2) is not true, by (1) we get

( 2 k + 1 ) r + k + 2 3 k + 3 < C max L P T ( L ) C max O P T ( L ) 1 + 2 p n 3 C max O P T ( L ) .

That means

C max O P T ( L ) < 2 ( k + 1 ) p n ( 2 k + 1 ) ( r 1 ) ( 3 k + 4 ) p n .

Hence we get n 9 k + 9 .

Case 2.1: n = 9 k + 9 .

In this case we have | S 1 | = | S 2 | = 3 k + 3 , | S 3 | = 3 k + 2 , | S 1 * | = | S 2 * | = | S 3 * | = 3 k + 3 . It is easy to see that there exists i { 1,2,3 } satisfying | S i * S 3 | k + 1 . Without loss of generality, suppose | S 1 * S 3 | k + 1 , then | S 3 \ S 1 * | 2 k + 1 . Therefore we get

C max L P T ( L ) C max O P T ( L ) j S 3 p j + p n j S 1 * p j = j S 3 S 1 * p j + j S 3 \ S 1 * p j + 1 j S 3 S 1 * p j + j S 1 * \ S 3 p j | S 3 S 1 * | + | S 3 \ S 1 * | r + 1 | S 3 S 1 * | + | S 1 * \ S 3 | = | S 3 | + | S 3 \ S 1 * | ( r 1 ) + 1 | S 1 * | ( 2 k + 1 ) r + k + 2 3 k + 3 .

Similarly we can get (2) for the case of n = 9 k + 7 , 9 k + 8 .

Case 2.2: n = 3 k + 1 , k 3 k + 1 .

Let | S 1 | = | S 2 | = | S 3 | = k , | S 1 * | = | S 2 * | = k , | S 3 * | = k + 1 , or | S 1 * | = k 1 , | S 2 * | = | S 3 * | = k + 1 . At any case | S 3 * | = k + 1 holds and there exists i { 1,2,3 } satisfying | S i S 3 * | k + 1 3 . W.l.o.g, suppose | S 1 S 3 * | k + 1 3 , then | S 1 \ S 3 * | 2 k 1 3 . Hence we get

C max L P T ( L ) C max O P T ( L ) j S 1 p j + p n j S 3 * p j = j S 1 S 3 * p j + j S 1 \ S 3 * p j + 1 j S 1 S 3 * p j + j S 3 * \ S 1 p j | S 1 S 3 * | + | S 1 \ S 3 * | r + 1 | S 1 S 3 * | + | S 3 * \ S 1 | = | S 1 \ S 3 * | ( r 1 ) + | S 1 | + 1 | S 3 * | = ( 2 k 1 ) r + k + 4 2 k 1 + k + 4 ( 2 k + 1 ) r + k + 1 + 4 2 k + 1 + k + 1 + 4 = ( 2 k + 1 ) r + k + 5 2 k + 1 + k + 5 ( 6 k + 3 ) r + 3 k + 6 9 k + 9 = ( 2 k + 1 ) r + k + 2 3 k + 3 ,

where the last two inequalities result from the facts that function y = ( 2 x 1 ) r + x + 4 3 x + 3 and y = ( x + 1 ) r + x + 5 3 x + 6 are increasing function of x. Similarly we can get (2) for the case of n = 3 k + i , k 3 k + 1 , i = 2 , 3 .

Case 3: 3 k + 4 3 ( k + 1 ) r < ( 2 k + 3 ) ( 3 k + 2 ) ( 2 k + 1 ) ( 3 k + 4 ) .

In this case, if the claim is not true, then by (1) there is a the minimal counter example L satisfying

9 k + 14 3 ( 3 k + 4 ) < C max L P T ( L ) C max O P T ( L ) 1 + 2 p n 3 C max O P T ( L ) .

Hence we get

C max O P T ( L ) < ( 3 k + 4 ) p n .

That means n 9 k + 9 . By the proof of Case 2 we get

C max L P T ( L ) C max O P T ( L ) ( 2 k + 1 ) r + k + 2 3 k + 3 9 k + 14 3 ( 3 k + 4 ) .

Case 4: 1 + 3 k + 4 9 ( k + 1 ) ( k + 2 ) r < 3 k + 4 3 ( k + 1 ) .

In this case, if the claim is not true, then by (1) there is a the minimal counter example L satisfying

2 ( k + 1 ) r + k + 2 3 k + 4 < C max L P T ( L ) C max O P T ( L ) 1 + 2 p n 3 C max O P T (L)

Hence we get

C max O P T ( L ) < 3 k + 4 3 ( k + 1 ) ( r 1 ) ( 3 k + 6 ) p n .

That means n 9 k + 15 .

Case 4.1: n = 9 k + 15 .

In this case we have | S 1 | = | S 2 | = 3 k + 5 , | S 3 | = 3 k + 4 , | S 1 * | = | S 2 * | = | S 3 * | = 3 k + 5 . It is easy to see that there exists i { 1,2,3 } satisfying | S 3 S i * | k + 2 . W.l.o.g, suppose | S 3 S 3 * | k + 2 . That means | S 3 \ S 3 * | 2 k + 2 . Hence we get

C max L P T ( L ) C max O P T ( L ) j S 3 p j + 1 j S 3 * p j = j S 3 S 3 * p j + j S 3 \ S 3 * p j + 1 j S 3 * S 3 p j + j S 3 * \ S 3 p j | S 3 S 3 * | + | S 3 \ S 3 * | r + 1 | S 3 * | = | S 3 \ S 3 * | ( r 1 ) + | S 3 | + 1 | S 3 * | ( 2 k + 2 ) ( r 1 ) + 3 k + 4 + 1 3 k + 5 ( 2 k + 2 ) r + k + 3 3 k + 5 ( 2 k + 2 ) r + k + 2 3 k + 4 ,

where the last inequality results from the fact that y = x + b x + 1 ( b 1 ) is a decreasing function of x.

Similarly we can show that the claim is true for the cases of n = 9 k + i , i = 13 , 14 .

Case 4.2: n = 3 k + 3 , k 3 k + 3 .

In this case, let | S 1 | = | S 2 | = k + 1 , | S 3 | = k . If There exists i { 1,2,3 } satisfying | S 3 S i * | k + 1 3 , w.l.o.g, suppose | S 3 S 1 * | k + 1 3 , then we have | S 3 \ S 1 * | 2 k 1 3 . Therefore we get

C max L P T ( L ) C max O P T ( L ) j S 3 p j + p n j S 1 * p j = j S 3 S 1 * p j + j S 3 \ S 1 * p j + p n j S 1 * S 3 p j + j S 1 * \ S 3 p j | S 3 S 1 * | + | S 3 \ S 1 * | r + 1 | S 3 S 1 * | + | S 1 * \ S 3 | = | S 3 \ S 1 * | ( r 1 ) + | S 3 | + 1 | S 1 * | 2 k 1 3 ( r 1 ) + k + 1 k + 1 6 k r + 5 r + 3 k + 7 3 ( 3 k + 4 ) ( 2 k + 2 ) r + k + 2 3 k + 4 .

If | S 1 * | = | S 2 * | = | S 3 * | = k + 1 , it is easy to see that there exists i { 1,2,3 } satisfying | S 3 S i * | k + 1 3 . Then we get the claim is true by above discussion.

If | S 1 * | k + 2, | S 3 S 1 * | k + 1 3 , we also get the claim is true by above discussion.

If | S 1 * | k + 2, | S 3 S 1 * | < k + 1 3 , then there exists i { 1,2 } satisfying | S i S 1 * | k + 3 3 , w.l.o.g, suppose | S 1 S 1 * | k + 3 3 , then | S 1 \ S 1 * | 2 k 3 . Hence we get

C max L P T ( L ) C max O P T ( L ) j S 1 p j + 1 j S 1 * p j = j S 1 S 1 * p j + j S 1 \ S 1 * p j + 1 j S 1 * S 1 p j + j S 1 * \ S 1 p j | S 1 S 1 * | + | S 1 \ S 1 * | r + 1 | S 1 S 1 * | + | S 1 * \ S 1 | = | S 1 \ S 1 * | ( r 1 ) + | S 1 | + 1 | S 1 * | 2 k 3 ( r 1 ) + k + 1 + 1 k + 2 ( 6 k + 6 ) r + 3 k + 9 3 ( 3 k + 5 ) ( 2 k + 2 ) r + k + 2 3 k + 4 ,

where the last inequality results from the fact that y = x + b x + 1 ( b 1 ) is a decreasing function of x.

Case 5: 6 ( k + 1 ) + 5 3 [ 2 ( k + 1 ) + 1 ] r < 1 + 3 k + 4 9 ( k + 1 ) ( k + 2 ) .

In this case we should prove

C max L P T ( L ) C max O P T ( L ) 9 k + 20 9 ( k + 2 ) .

If it is not true, then by (1) the minimal counter example satisfies

9 k + 20 9 ( k + 2 ) < C max L P T ( L ) C max O P T ( L ) i = 1 n p i + 2 p n 3 C max O P T (L)

Hence we get

C max O P T ( L ) < ( 3 k + 6 ) p n .

That means n 9 k + 15 . By the proof of Case 4 we get

C max O P T ( L ) 2 ( k + 1 ) r + k + 2 3 k + 4 9 k + 14 3 ( 3 k + 4 ) .

By the above discussions of Case 1-5, the inequality in Theorem 2 is proved.

Now we prove the tightness of the inequalities. For ( 2 k + 3 ) ( 3 k + 2 ) ( 2 k + 1 ) ( 3 k + 4 ) r < 6 k + 5 3 ( 2 k + 1 ) , let L = { J 1 , J 2 , , J 9 k + 7 } with p j = r , j = 1 , 2 , , 6 k + 2 , p 6 k + 3 = p 6 k + 4 = r = r + 1 2 , p j = 1 , j = 6 k + 5 , , 9 k + 7 . Then L 1 = ( 2 k + 1 ) r + k + 2 , L 2 = ( 2 k + 1 ) r + k + 1 , L 3 = 2 k r + k + 2 r , L 1 * = 3 k + 3 , L 2 * = L 3 * = ( 3 k + 1 ) r + r . Hence we get

C max L P T ( L ) C max O P T ( L ) = ( 2 k + 1 ) r + k + 2 3 k + 3 . (3)

For 3 k + 4 3 ( k + 1 ) r < ( 2 k + 3 ) ( 3 k + 2 ) ( 2 k + 1 ) ( 3 k + 4 ) . let L = { J 1 , J 2 , , J 9 k + 10 } with p j = r , j = 1 , , 6 ; p j = r = 3 k + 4 3 r 3 k , j = 7 , , 6 k + 6 , p j = 1 , j = 6 k + 7 , , 9 k + 10 . Then we have L 1 = 2 r + 2 k r + k + 2 , L 2 = L 3 = 2 r + 2 k r + k + 1 , L 1 * = 3 k + 4 , L 2 * = L 3 * = 3 r + 3 k r . Hence we get

C max L P T ( L ) C max O P T ( L ) = 9 k + 14 3 ( 3 k + 4 ) . (4)

For 1 + 3 k + 4 9 ( k + 1 ) ( k + 2 ) r < 3 k + 4 3 ( k + 1 ) , let L = { J 1 , J 2 , , J 9 k + 10 } with p j = r , j = 1 , 2 , , 6 k + 6 , p j = 1 , j = 6 k + 7 , , 9 k + 10 . Then we have L 1 = 2 ( k + 1 ) r + k + 2 , L 2 = L 3 = 2 ( k + 1 ) r + k + 1 , , . 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. , Li, R. and Zhou, Y. (2019) LPT Algorithm for Jobs with Similar Sizes on Three Machines. Applied Mathematics, 10, 947-955. doi: 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.

  
comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.