Abstract
This paper considers the on-line problem of scheduling nonpreemptively n independent jobs on m > 1 identical and parallel machines with the objective to maximize the minimum machine completion time. It is assumed that the values of the processing times are unknown but the order of the jobs by their processing times is known in advance. We are asked to decide the assignment of all the jobs to some machines at time zero by utilizing only ordinal data rather than the actual magnitudes of jobs. Algorithms to slove the problem are called ordinal algorithms. In this paper, we give lower bounds and ordinal algorithms. We first propose an algorithm MIN which is at most \((\left\lceil {\sum {_{i = 1}^m {\text{ }}1/} i} \right\rceil + 1)\)-competitive for any m machine case, while the lower bound is ∑ mi=1 1/i. Both are on the order of Θ(ln m). Furthermore, for m = 3, we present an optimal algorithm.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
A. Agnetis, “No-wait flow shop scheduling with large lot size,” Rap 16.89, Dipartimento di Informatica e Sistemistica, Universita Degli Studi di Roma “La Sapienza”, Rome, Italy, 1989.
Y. Azar and L. Epstein, “On-line machine covering,” Algorithms-ESA'97, LNCS, vol. 1284, Springer Verlag, (1997), pp. 23–36.
J. Csirik, H. Kellerer, and G. Woeginger, “The exact LPT-bound for maximizing the minimum machine completion time,” Oper. Res. 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. Disc. Meth., vol. 3, pp. 190–196, 1982.
D. Friesen and B. Deuermeyer, “Analysis of greedy solutions for a replacement part sequencing problem,” Math. Oper. Res., vol. 6, pp. 74–87, 1981.
R.L. Graham, E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy Kan, “Optimization and approximation in deterministic sequencing and scheduling: A survey,” Annals of Oper. Res., vol. 5, pp. 287–326, 1979.
Y. He, “The optimal on-line parallel machine scheduling,” Computers & Mathematics with Applications, vol. 39, pp. 117–121, 2000.
Y. He, “Semi on-line scheduling problem for maximizing the minimum machine completion time,” Acta Mathematica Applicatae Sinica, vol. 17, pp. 107–113, 2001.
Y. He and G. Zhang, “Semi online scheduling on two identical machines,” Computing, vol. 62, pp. 179–197, 1999.
H. Kellerer, V. Kotov, M. Speranza, and Z. Tuza, “Semi online algorithms for the partition problem,” Oper. Res. Letters, vol. 21, pp. 235–242, 1997.
E.L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston: Toronto, 1976.
W.P. Liu and J.B. Sidney, “Ordinal algorithm for packing with target center of gravity,” Order, vol. 13, pp. 17–31, 1996.
W.P. Liu and J.B. Sidney, “Bin packing using semi-ordinal data,” Oper. Res. Letters, vol. 19, pp. 101–104, 1996.
W.P. Liu, J.B. Sidney, and A. van Vliet, “Ordinal algorithms for parallel machine scheduling,” Oper. Res. Letters, vol. 18, pp. 223–232, 1996.
N.V.R. Mahadev, A. Pekec, and F.S. Roberts, “On the meaningfulness of optimal solutions to scheduling problems: Can an optimal solution be nonoptimal,” Oper. Res., vol. 46, pp. S120–S134, 1998.
E. Menipaz, Essentials of Production and Operations Management, Prentice-Hall: Englewood Cliffs, NJ, 1984.
S. Seiden, J. Sgall, and G. Woeginger, “Semi-online scheduling with decreasing job sizes,” Oper. Res. Letters, vol. 27, pp. 215–221, 2000.
D. Sleator and R.E. Tarjan, “Amortized efficiency of list update and paging rules,” Communications of the ACM, vol. 28, pp. 202–208, 1985.
Z.Y. Tan and Y. He, “Semi-on-line scheduling with ordinal data on two uniform machines,” Oper. Res. Letters, vol. 28, pp. 221–231, 2001.
G. Woeginger, “A polynomial time approximation scheme for maximizing the minimum machine completion time,” Oper. Res. Letters, vol. 20, pp. 149–154, 1997.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
He, Y., Tan, Z. Ordinal On-Line Scheduling for Maximizing the Minimum Machine Completion Time. Journal of Combinatorial Optimization 6, 199–206 (2002). https://doi.org/10.1023/A:1013855712183
Issue Date:
DOI: https://doi.org/10.1023/A:1013855712183