Abstract
This paper investigates the preemptive parallel machine scheduling to maximize the minimum machine completion time. We first show the off-line version can be solved in O(mn) time for general m-uniform-machine case. Then we study the on-line version. We show that any randomized on-line algorithm must have a competitive ratio m for m-uniform-machine case and ∑i = 1m1/i for m-identical-machine case. Lastly, we focus on two-uniform-machine case. We present an on-line deterministic algorithm whose competitive ratio matches the lower bound of the on-line problem for every machine speed ratio s≥ 1. We further consider the case that idle time is allowed to be introduced in the procedure of assigning jobs and the objective becomes to maximize the continuous period of time (starting from time zero) when both machines are busy. We present an on-line deterministic algorithm whose competitive ratio matches the lower bound of the problem for every s≥ 1. We show that randomization does not help.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Y. Azar and L. Epstein, “On-line machine covering, ESA'97,” Lecture Notes in Computer Science, vol. 1284, pp. 23–36, 1997.
Y. Azar and L. Epstein, “Approximation schemes for covering and scheduling on related machines machine covering,” Proc. of APPROX'1998, pp. 39–47, 1998.
B. Chen, A. van Vliet, and G. Woeginger, “An optimal algorithm for preemptive on-line scheduling,” Operations Research Letters, vol. 18, pp. 127–131, 1995.
J. Csirik, H. Kellerer, and G. Woeginger, “The exact LPT-bound for maximizing the minimum completion time,” Operations Research Letters, vol. 11, pp. 281–287, 1992.
B. Deuermeyer, D. Friesen, and M. Langston, “Scheduling to maximize the minimum processor finish time in a multiprocessor system,” SIAM J. Discrete Methods, vol. 3, pp. 190–196, 1982.
L. Epstein, “Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios,” Operations Research Letters, vol. 29, pp. 93–98, 2001.
L. Epstein, “Tight bounds for online bandwidth allocation on two links,” Proc. of the 3rd ARACNE, pp. 39–50, 2002.
L. Epstein and L. Favrholdt, “Optimal preemptive semi-online scheduling to minimize makespan on two related machines,” Operations Research Letters, vol. 30, pp. 269–275, 2002.
L. Epstein, J. Noga, S. Seiden, J. Sgall, and G. Woeginger, “Randomized on-line scheduling on two uniform machines,” Journal of Scheduling, vol. 4, pp. 71–92, 2001.
L. Epstein and J. Sgall, “A lower bound for on-line scheduling on uniformly related machines,” Operations Research Letters, vol. 26, pp. 17–22, 2000.
T. Gonzalez and S. Sahni, “Preemptive scheduling of uniform processor systems,” Journal of the Association for Computing Machinery, vol. 25, pp. 92–101, 1978.
Y. He, “The optimal on-line parallel machine scheduling,” Computers & Mathematics with Applications, vol. 39, pp. 117–121, 2000.
Y. He and Y. W. Jiang, “Optimal algorithms for semi-online preemptive scheduling problems on two uniform machines,” Acta Informatica, vol. 40, pp. 367–383, 2004.
Y. He and Z.Y. Tan, “Ordinal on-line scheduling for maximizing the minimum machine completion time,” Journal of Combinatorial Optimization, vol. 6, pp. 199–206, 2002.
E.C. Horvath, S. Lam, and R. Sethi, “A level algorithm for preemptive scheduling,” Journal of the Association for Computing Machinery, vol. 24, pp. 32–43, 1977.
S. Seiden, J. Sgall, and G. Woeginger, “Semi-online scheduling with decreasing job sizes,” Operations Research Letters, vol. 27, pp. 215–221, 2000.
J. Sgall, “A lower bound for randomized on-line multiprocessor scheduling,” Information Processing Letters, vol. 63, pp. 51–55, 1997.
A.P.A. Vestjens, “Scheduling uniform machines on-line requires nondecreasing speed ratios,” Mathematical Programming, vol. 82, pp. 225–234, 1998.
J. Wen and D. Du, “Preemptive on-line scheduling for two uniform processors,” Operations Research Letters, vol. 23, pp. 113–116, 1998.
G. Woeginger, “A polynomial time approximation scheme for maximizing the minimum machine completion time,” Operations Research Letters, vol. 20, pp. 149–154, 1997.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Jiang, Y., Tan, Z. & He, Y. Preemptive Machine Covering on Parallel Machines. J Comb Optim 10, 345–363 (2005). https://doi.org/10.1007/s10878-005-4923-5
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10878-005-4923-5