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 + √(3))/2 ≈ 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 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 + √(37))/6 ≈ 1.18046. Finally, we present a randomized non-preemptive 8/7-competitive algorithm for m = 2 machines and prove that this is optimal.
