AbstractDistributed systems execute background or alternative jobs while waiting for data or requests to arrive from another processor. In those cases, the following

shut-down scheduling problemarises: given a set of jobs of known processing time, schedule them on m machines so as to maximize the total weight of jobs completed before an initially unknown deadline. We present optimally competitive deterministic and randomized algorithms for shut-down scheduling. Our deterministic algorithm is parameterized by the numbermof machines. Its competitive ratio increases as the number of machines decreases, but it is optimal for any given choice ofm. Such a family of deterministic algorithms can be translated into a family of randomized algorithms that use progressively less randomization and that are optimal for any given number of fair coin tosses. Hence, we establish a precise trade-off between the amount of randomization and the best possible competitive ratio.

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems

Additional Key Words and Phrases: algorithms, online algorithms, competitive analysis, scheduling, knapsack

Selected references

- Baruch Awerbuch, Yair Bartal, Amos Fiat, and Adi Rosén. Competitive non-preemptive call control. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 312-320, Arlington, Virginia, 23-25 January 1994.

- Juan A. Garay, Inder S. Gopal, and Shay Kutten. Efficient on-line call control algorithms. Journal of Algorithms, 23(1):180-194, April 1997.

- A. V. Goldberg and A. Marchetti-Spaccamela. On finding the exact solution of a zero-one knapsack problem. In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, pages 359-368, Washington, D.C., 1984.

- Bala Kalyanasundaram and Kirk R. Pruhs. Fault-tolerant scheduling. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 115-124, Montréal, Québec, Canada, 23-25 May 1994.

- Richard J. Lipton and Andrew Tomkins. Online interval scheduling. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 302-311, Arlington, Virginia, 23-25 January 1994.

- George S. Lueker. Average-case analysis of off-line and on-line knapsack problems. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 179-188, San Francisco, California, 22-24 January 1995.

- George Markowsky. Best Huffman trees. Acta Informatica, 16:363-370, 1981.