Abstract
We study classic machine sequencing problems in an online setting. Specifically, we look at deterministic and randomized algorithms for the problem of scheduling jobs with release dates on identical parallel machines, to minimize the sum of weighted completion times: Both preemptive and non-preemptive versions of the problem are analyzed. Using linear programming techniques, borrowed from the single machine case, we are able to design a 2.62-competitive deterministic algorithm for the non-preemptive version of the problem, improving upon the 3.28-competitive algorithm of Megow and Schulz. Additionally, we show how to combine randomization techniques with the linear programming approach to obtain randomized algorithms for both versions of the problem with competitive ratio strictly smaller than 2 for any number of machines (but approaching two as the number of machines grows). Our algorithms naturally extend several approaches for single and parallel machine scheduling. We also present a brief computational study, for randomly generated problem instances, which suggests that our algorithms perform very well in practice.
Similar content being viewed by others
References
Afrati, F., Bampis, E., Chekuri, C., Karger, D., Kenyon, C., Khanna, S., Milis, I., Queyranne, M., Skutella, M., Stein C., Sviridenko, M.: Approximation schemes for minimizing average weighted completion time with release dates. In: Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 32–43 (1999)
Albers S. and Schröder B. (2002). An experimental study of online scheduling algorithms. J. Exp. Algorithmics 7: 3
Anderson E.J. and Potts C.N. (2004). On-line scheduling of a single machine to minimize total weighted completion time. Math. Oper. Res. 29: 686–697
Chakrabarti S., Phillips C., Schulz A.S., Shmoys D.B., Stein C. and Wein J. (1996). Improved scheduling algorithms for minsum criteria,” in Automata, Languages and Programming (ICALP), LNCS, vol. 1099. Springer, Heidelberg, pp 646–657
Chekuri C., Motwani R., Natarajan B. and Stein C. (2001). Approximation techniques for average completion time scheduling. SIAM J. Comput. 31: 146–166
Chou M.C., Queyranne M. and Simchi-Levi D. (2006). The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates. Math. Program. 106: 137–157
Sousa, J.P.: Time Indexed Formulations of Non-Preemptive Single-Machine Scheduling Problems. PhD thesis, Université Catholique de Louvain (1989)
Eastman W.L., Even S. and Isaacs I.M. (1964). Bounds for the optimal scheduling of n jobs on m processors. Manage. Sci. 11: 268–279
Goemans, M.X.: A supermodular relaxation for scheduling with release dates. In: Proceedings of the 5th Integer Programming and Combinatorial Optimization Conference (IPCO), LNCS, vol. 1084, pp. 288–300. Springer, Heidelberg (1996)
Goemans, M.X.: Improved approximation algorithms for scheduling with release dates. In: Proceedings of the 8th Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), New Orleans, LA, 1997. ACM, New York, 1997, pp. 591–598 (1997)
Goemans M., Queyranne M., Schulz A.S., Skutella M. and Wang Y. (2002). Single machine scheduling with release dates. SIAM J. Discrete Math. 15: 165–192
Graham R.L., Lawler E.L., Lenstra J.K. and Rinnooy Kan A.H.G. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5: 287–326
Hall L.A., Schulz A.S., Shmoys D.B. and Wein J. (1997). Scheduling to minimize average completion time: off-line and on-line approximation algorithms. Math. Oper. Res. 22: 513–544
Hall, L.A., Shmoys, D.B., Wein, J.: Scheduling to minimize average completion time: off-line and on-line approximation algorithms. In: Proceedings of the 7th Annual ACM–SIAM Symposium on Discrete Algorithms, pp. 142–151 (1997)
Hoogeveen, J.A., Vestjens, A.P.A.: Optimal on-line algorithms for single-machine scheduling. In: Proceedings of the 5th Integer Programming and Combinatorial Optimization Conference (IPCO), LNCS, vol. 1084, pp. 404–414. Springer, Heidelberg (1996)
Kovács, A., Beck, J.C.: A global constraint for total weighted completion time. In: Proceedings of the 4th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (LNCS 4510), Brussels, pp. 112–126. Springer, Heidelberg (2007)
Megow N. and Schulz A.S. (2004). On-line scheduling to minimize average completion time revisited. Oper. Res. Lett 32: 485–490
Phillips C., Stein C. and Wein J. (1998). Minimizing average completion time in the presence of release dates. Math. Program. 82: 199–223
Savelsbergh M.W.P., Uma R.N. and Wein J. (2005). An experimental study of LP-based approximation algorithms for scheduling problems. INFORMS J. Comput. 17: 123–136
Schulz A.S. (2005). New old algorithms for stochastic scheduling. In: Albers, S., Möhring, R.H., Pflug, G.C. and Schultz, R. (eds) Algorithms for Optimization with Incomplete Information, Dagstuhl Seminar Proceedings 05031, Schloss Dagstuhl, Germany
Schulz A.S. and Skutella M. (2002). Scheduling unrelated machines by randomized rounding. SIAM J. Discrete Math. 15: 450–469
Schulz A.S. and Skutella M. (2002). The power of α-points in preemptive single machine scheduling. J. Sched. 5: 121–133
Seiden, S.: A guessing game and randomized online algorithms. In: Proceedings of the 32nd ACM Symposium on Theory of Computing, pp. 592–601 (2000)
Sitters, R.: Complexity and approximation in routing and scheduling. PhD Thesis, Eindhoven University of Technology, The Netherlands (2004)
Skutella, M.: List scheduling in order of α-points on a single machine. Lecture Notes in Computer Science, vol. 3484, pp. 250–291 (2006)
Smith W.E. (1956). Various optimizers for single-stage production. Nav. Res. Logist. Q. 3: 59–66
Stougie L. and Vestjens A.P.A. (2002). Randomized algorithms for on-line scheduling problems: how low can’t you go?. Oper. Res. Lett. 30: 89–96
Vestjens, A.P.A.: Online machine scheduling. PhD Thesis, Eindhoven University of Technology, The Netherlands (1997)
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this work appears in the Proceedings of the 11th conference on integer programming and combinatorial optimization (IPCO), Berlin, 8–10 June 2005.
Rights and permissions
About this article
Cite this article
Correa, J.R., Wagner, M.R. LP-based online scheduling: from single to parallel machines. Math. Program. 119, 109–136 (2009). https://doi.org/10.1007/s10107-007-0204-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-007-0204-7