Semi-online scheduling with decreasing job sizes

We investigate the problem of semi-online scheduling jobs on m identical parallel machines where the jobs arrive in order of decreasing sizes. We present a complete solution for the preemptive variant of semi-online scheduling 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 infinity. Our results are also the best possible for randomized algorithms. For 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-competitive). For m=3 machines we give a lower bound of(1 + root 37)/6 approximate to 1.18046. Finally, we present a randomized non-preemptive 8/7-competitive algorithm for m = 2 machines and prove that this is optimal. (C) 2000 Elsevier Science B.V. All lights reserved.