×

A class of on-line scheduling algorithms to minimize total completion time. (English) Zbl 1013.90067

Summary: We consider the problem of scheduling jobs on-line on a single machine and on identical machines with the objective to minimize total completion time. We assume that the jobs arrive over time. We give a general 2-competitive algorithm for the single machine problem. The algorithm is based on delaying the release time of the jobs, i.e., making the jobs artificially later available to the on-line scheduler than the actual release times. Our algorithm includes two known algorithms for this problem that apply delay of release times. The proposed algorithm is interesting since it gives the on-line scheduler a whole range of choices for the delays, each of which leading to 2-competitiveness.
We also show that the algorithm is \(2\alpha\) competitive for the problem on identical machines where \(\alpha\) is the performance ratio of the shortest remaining processing Time first rule for the preemptive relaxation of the problem.

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] F. Afrati, E. Bampis, C. Chekuri, D. Karger, C. Kenyon, S. Khanna, I. Milis, M. Queyranne, M. Skutella, C. Stein, M. Sviridenko, Approximation schemes for minimizinge average weighted completion time with release dates, Proceedings of the 40th IEEE Symposium on Foundations of Computer Science, New York City, NY, October 1999.; F. Afrati, E. Bampis, C. Chekuri, D. Karger, C. Kenyon, S. Khanna, I. Milis, M. Queyranne, M. Skutella, C. Stein, M. Sviridenko, Approximation schemes for minimizinge average weighted completion time with release dates, Proceedings of the 40th IEEE Symposium on Foundations of Computer Science, New York City, NY, October 1999.
[2] Chekuri, C.; Motwani, R.; Natarajan, B.; Stein, C., Approximation techniques for average completion time scheduling, SIAM J. Comput., 31, 146-166 (2001) · Zbl 0992.68066
[3] Conway, R. W.; Maxwell, W. L.; Miller, L. W., Theory of Scheduling (1967), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 1058.90500
[4] Du, J.; Leung, J. Y-T.; Young, G. H., Minimizing mean flow time with release time constraint, Theoretical Comput. Sci., 75, 347-355 (1990) · Zbl 0701.68008
[5] J.A. Hoogeveen, A.P.A. Vestjens, Optimal on-line algorithms for single-machine scheduling, Proceedings Fifth International Conference on Integer Programming and Combinatorial Optimization, Vancouver, British Columbia, Canada, June 3-5, 1996, Lecture Notes in Computer Science, Vol. 1084, Springer, Berlin, 1996, pp. 404-414.; J.A. Hoogeveen, A.P.A. Vestjens, Optimal on-line algorithms for single-machine scheduling, Proceedings Fifth International Conference on Integer Programming and Combinatorial Optimization, Vancouver, British Columbia, Canada, June 3-5, 1996, Lecture Notes in Computer Science, Vol. 1084, Springer, Berlin, 1996, pp. 404-414. · Zbl 1414.90152
[6] Lenstra, J. K.; Rinnooy Kan, A. H.G.; Brucker, P., Complexity of machine scheduling problems, Ann. Discrete Math., 1, 343-362 (1977) · Zbl 0301.90025
[7] Phillips, C.; Stein, C.; Wein, J., Minimizing average completion time in the presence of release dates, networks and matroids; Sequencing and scheduling, Math. Programming, 82, 199-223 (1998) · Zbl 0920.90074
[8] Schrage, L., A proof of the shortest remaining processing time processing discipline, Oper. Res., 16, 687-690 (1968) · Zbl 0237.60039
[9] Sgall, J., On-line scheduling, (Fiat, A.; Woeginger, G. J., Online Algorithms: The State of the Art. Online Algorithms: The State of the Art, Lecture Notes in Computer Science, Vol. 1442 (1998), Springer: Springer Berlin), 196-231
[10] A.P.A. Vestjens, On-line Machine Scheduling, Ph.D. Thesis, Department of Mathematics and Computing Science, Technische Universiteit Eindhoven, Eindhoven, The Netherlands, 1997.; A.P.A. Vestjens, On-line Machine Scheduling, Ph.D. Thesis, Department of Mathematics and Computing Science, Technische Universiteit Eindhoven, Eindhoven, The Netherlands, 1997.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.