Semi-online scheduling with decreasing job sizes

We investigate the problem of semi-online scheduling jobs on m identical pa rallel machines where the jobs arrive in order of decreasing sizes. We pres ent a complete solution for the preemptive variant of semi-online schedulin g with decreasing job sizes. We give matching lower and upper bounds on the competitive ratio for any fixed number m of machines; these bounds tend To (1 + root3)/2 approximate to 1.36603, as the number of machines goes to in finity. Our results are also the best possible for randomized algorithms. F or the non-preemptive variant of semi-online scheduling with decreasing job sizes, a result of Graham (SIAM J. Appl. Math. 17 (1969) 263-269) yields a (4/3 - 1/(3m))-competitive deterministic non-preemptive algorithm. For m=2 machines, we prove that this algorithm is the best possible (it is 7/6-com petitive). For m=3 machines we give a lower bound of(1 + root 37)/6 approxi mate to 1.18046. Finally, we present a randomized non-preemptive 8/7-compet itive algorithm for m = 2 machines and prove that this is optimal. (C) 2000 Elsevier Science B.V. All lights reserved.