LP-based online scheduling: from single to parallel machines

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

   Article  Google Scholar 

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

   Article  MATH  MathSciNet  Google Scholar 

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

   Google Scholar 

5. Chekuri C., Motwani R., Natarajan B. and Stein C. (2001). Approximation techniques for average completion time scheduling. SIAM J. Comput. 31: 146–166

   Article  MATH  MathSciNet  Google Scholar 

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

   Article  MATH  MathSciNet  Google Scholar 

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

   Article  MathSciNet  Google Scholar 

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)

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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)

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)

17. Megow N. and Schulz A.S. (2004). On-line scheduling to minimize average completion time revisited. Oper. Res. Lett 32: 485–490

    Article  MATH  MathSciNet  Google Scholar 

18. Phillips C., Stein C. and Wein J. (1998). Minimizing average completion time in the presence of release dates. Math. Program. 82: 199–223

    MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Google Scholar 

21. Schulz A.S. and Skutella M. (2002). Scheduling unrelated machines by randomized rounding. SIAM J. Discrete Math. 15: 450–469

    Article  MATH  MathSciNet  Google Scholar 

22. Schulz A.S. and Skutella M. (2002). The power of α-points in preemptive single machine scheduling. J. Sched. 5: 121–133

    Article  MATH  MathSciNet  Google Scholar 

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)

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 α-points on a single machine. Lecture Notes in Computer Science, vol. 3484, pp. 250–291 (2006)

26. Smith W.E. (1956). Various optimizers for single-stage production. Nav. Res. Logist. Q. 3: 59–66

    Article  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

28. Vestjens, A.P.A.: Online machine scheduling. PhD Thesis, Eindhoven University of Technology, The Netherlands (1997)

Download references