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 problem arises: 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 number m of machines. Its competitive ratio increases as the number of machines decreases, but it is optimal for any given choice of m. 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.