LP-based online scheduling: From single to parallel machines. (English) Zbl 1162.90009
This paper considers the problem of scheduling \(n\) jobs with given release dates on \(m\) identical parallel machines such that the sum of weighted completion times becomes minimal. Both the non-preemptive and the preemptive problems are considered in an online version. The paper uses linear programming techniques and generalizes the ideas given by M. X. Goemans et al. [SIAM J. Discrete Math. 15, No. 2, 165–192 (2002; Zbl 1009.90096)] for the single machine problem to the parallel machine case. In particular, it improves the 3.28-competitive algorithm by N. Megow and A. S. Schulz [Oper. Res. Lett. 32, No. 5, 485–490 (2004; Zbl 1054.90037)] for the non-preemptive version and is 2.618-competitive. Moreover, it is shown that the algorithm can be improved further using randomization. More precisely, randomized algorithms with a competitive ratio strictly smaller than two are given for any number of machines, approaching to two as the number of machines grows. This improves former algorithms by A. S. Schulz and M. Skutella [SIAM J. Discrete Math. 15, No. 4, 450–469 (2002; Zbl 1055.90040)]. Finally, computational results are given for problems with up to 500 jobs and 25 machines.
Reviewer: Frank Werner (Magdeburg)
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 68W20 | Randomized algorithms |
| 68W25 | Approximation algorithms |
| 68Q25 | Analysis of algorithms and problem complexity |
Keywords:
Online algorithms; Parallel machine scheduling; Linear programming; Weighted sum of completion timesReferences:
| [1] | 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) |
| [2] | Albers S. and Schröder B. (2002). An experimental study of online scheduling algorithms. J. Exp. Algorithmics 7: 3 · Zbl 1083.68523 · doi:10.1145/944618.944621 |
| [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 · Zbl 1082.90033 · doi:10.1287/moor.1040.0092 |
| [4] | 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 · Zbl 1046.68505 |
| [5] | Chekuri C., Motwani R., Natarajan B. and Stein C. (2001). Approximation techniques for average completion time scheduling. SIAM J. Comput. 31: 146–166 · Zbl 0992.68066 · doi:10.1137/S0097539797327180 |
| [6] | 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 · Zbl 1134.90382 · doi:10.1007/s10107-005-0588-1 |
| [7] | Sousa, J.P.: Time Indexed Formulations of Non-Preemptive Single-Machine Scheduling Problems. PhD thesis, Université Catholique de Louvain (1989) |
| [8] | 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 · doi:10.1287/mnsc.11.2.268 |
| [9] | 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) |
| [10] | 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) · Zbl 1321.68502 |
| [11] | 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 · Zbl 1009.90096 · doi:10.1137/S089548019936223X |
| [12] | 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 · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X |
| [13] | 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 · Zbl 0883.90064 · doi:10.1287/moor.22.3.513 |
| [14] | 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) · Zbl 0845.90071 |
| [15] | 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) |
| [16] | 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) · Zbl 1214.90054 |
| [17] | Megow N. and Schulz A.S. (2004). On-line scheduling to minimize average completion time revisited. Oper. Res. Lett 32: 485–490 · Zbl 1054.90037 · doi:10.1016/j.orl.2003.11.008 |
| [18] | Phillips C., Stein C. and Wein J. (1998). Minimizing average completion time in the presence of release dates. Math. Program. 82: 199–223 · Zbl 0920.90074 |
| [19] | 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 · Zbl 1239.90053 · doi:10.1287/ijoc.1030.0055 |
| [20] | 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 |
| [21] | Schulz A.S. and Skutella M. (2002). Scheduling unrelated machines by randomized rounding. SIAM J. Discrete Math. 15: 450–469 · Zbl 1055.90040 · doi:10.1137/S0895480199357078 |
| [22] | Schulz A.S. and Skutella M. (2002). The power of {\(\alpha\)}-points in preemptive single machine scheduling. J. Sched. 5: 121–133 · Zbl 1038.90037 · doi:10.1002/jos.93 |
| [23] | Seiden, S.: A guessing game and randomized online algorithms. In: Proceedings of the 32nd ACM Symposium on Theory of Computing, pp. 592–601 (2000) · Zbl 1296.68071 |
| [24] | Sitters, R.: Complexity and approximation in routing and scheduling. PhD Thesis, Eindhoven University of Technology, The Netherlands (2004) |
| [25] | Skutella, M.: List scheduling in order of {\(\alpha\)}-points on a single machine. Lecture Notes in Computer Science, vol. 3484, pp. 250–291 (2006) · Zbl 1132.90333 |
| [26] | Smith W.E. (1956). Various optimizers for single-stage production. Nav. Res. Logist. Q. 3: 59–66 · doi:10.1002/nav.3800030106 |
| [27] | 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 · Zbl 1030.90041 · doi:10.1016/S0167-6377(01)00115-8 |
| [28] | Vestjens, A.P.A.: Online machine scheduling. PhD Thesis, Eindhoven University of Technology, The Netherlands (1997) · Zbl 0941.68515 |
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.
