Abstract
Many approximation results for single machine scheduling problems rely on the conversion of preemptive schedules into (preemptive or non-preemptive) solutions. The initial preemptive schedule is usually an optimal solution to a combinatorial relaxation or a linear programming relaxation of the scheduling problem under consideration. It therefore provides a lower bound on the optimal objective function value. However, it also contains structural information which is useful for the construction of provably good feasible schedules. In this context, list scheduling in order of so-called α-points has evolved as an important and successful tool. We give a survey and a uniform presentation of several approximation results for single machine scheduling with total weighted completion time objective from the last years which rely on the concept of α-points.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
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 Annual IEEE Symposium on Foundations of Computer Science, New York City, NY, pp. 32–43 (1999)
van den Akker, J.M.: LP–Based Solution Methods for Single–Machine Scheduling Problems. PhD thesis, Eindhoven University of Technology, Eindhoven, The Netherlands (1994)
Anderson, E.J., Potts, C.N.: On-line scheduling of a single machine to minimize total weighted completion time. Mathematics of Operations Research 29, 686–697 (2004)
Baker, K.R.: Introduction to Sequencing and Scheduling. John Wiley & Sons, New York (1974)
Cavalcante, C.C.B., de Souza, C.C., Savelsbergh, M.W.P., Wang, Y., Wolsey, L.A.: Scheduling projects with labor constraints. Discrete Applied Mathematics 112, 27–52 (2001)
Chakrabarti, S., Muthukrishnan, S.: Resource scheduling for parallel database and scientific applications. In: Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures, Padua, Italy, pp. 329–335 (1996)
Chakrabarti, S., Phillips, C., Schulz, A.S., Shmoys, D.B., Stein, C., Wein, J.: Improved scheduling algorithms for minsum criteria. In: Meyer auf der Heide, F., Monien, B. (eds.) ICALP 1996. LNCS, vol. 1099, pp. 646–657. Springer, Heidelberg (1996)
Chan, L.M.A., Muriel, A., Simchi-Levi, D.: Parallel machine scheduling, linear programming and list scheduling heuristics. Operations Research 46, 729–741 (1998)
Chekuri, C.S., Johnson, R., Motwani, R., Natarajan, B., Rau, B.R., Schlansker, M.: Profile–driven instruction level parallel scheduling with applications to super blocks. In: Proceedings of the 29th Annual International Symposium on Microarchitecture, Paris, France, pp. 58–67 (1996)
Chekuri, C.S., Motwani, R.: Precedence constrained scheduling to minimize weighted completion time on a single machine. Discrete Applied Mathematics 98, 29–38 (1999)
Chekuri, C.S., Motwani, R., Natarajan, B., Stein, C.: Approximation techniques for average completion time scheduling. SIAM Journal on Computing 31, 146–166 (2001)
Correa, J.R., Schulz, A.S.: Single machine scheduling with precedence constraints. In: Bienstock, D., Nemhauser, G.L. (eds.) IPCO 2004. LNCS, vol. 3064, pp. 283–297. Springer, Heidelberg (2004)
Dyer, M.E., Wolsey, L.A.: Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Applied Mathematics 26, 255–270 (1990)
Epstein, L., van Stee, R.: Lower bounds for on-line single machine scheduling. Theoretical Computer Science 299, 439–450 (2003)
Goemans, M.X.: A supermodular relaxation for scheduling with release dates. In: Cunningham, W.H., Queyranne, M., McCormick, S.T. (eds.) IPCO 1996. 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, New Orleans, LA, pp. 591–598 (1997)
Goemans, M.X., Queyranne, M., Schulz, A.S., Skutella, M., Wang, Y.: Single machine scheduling with release dates. SIAM Journal on Discrete Mathematics 15, 165–192 (2002)
Goemans, M.X., Wein, J., Williamson, D.P.: A 1.47-approximation algorithm for a preemptive single-machine scheduling problem. Operations Research Letters 26, 149–154 (2000)
Goemans, M.X., Williamson, D.P.: Two-dimensional Gantt charts and a scheduling algorithm of Lawler. SIAM Journal on Discrete Mathematics 13, 281–294 (2000)
Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics 5, 287–326 (1979)
Hall, L.A., Schulz, A.S., Shmoys, D.B., Wein, J.: Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Mathematics of Operations Research 22, 513–544 (1997)
Hall, L.A., Shmoys, D.B., Wein, J.: Scheduling to minimize average completion time: Off-line and on-line algorithms. In: Proceedings of the 7th Annual ACM–SIAM Symposium on Discrete Algorithms, Atlanta, GA, pp. 142–151 (1996)
Hoogeveen, J.A., Vestjens, A.P.A.: Optimal on-line algorithms for single-machine scheduling. In: Cunningham, W.H., Queyranne, M., McCormick, S.T. (eds.) IPCO 1996. LNCS, vol. 1084, pp. 404–414. Springer, Heidelberg (1996)
Labetoulle, J., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Preemptive scheduling of uniform machines subject to release dates. In: Pulleyblank, W.R. (ed.) Progress in Combinatorial Optimization, pp. 245–261. Academic Press, New York (1984)
Margot, F., Queyranne, M., Wang, Y.: Decomposition, network flows and a precedence constrained single machine scheduling problem. Operations Research 51, 981–992 (2003)
Möhring, R.H., Schulz, A.S., Stork, F., Uetz, M.: Solving project scheduling problems by minimum cut computations. Management Science 49, 330–350 (2003)
Möhring, R.H., Schulz, A.S., Uetz, M.: Approximation in stochastic scheduling: The power of LP-based priority policies. Journal of the ACM 46, 924–942 (1999)
Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)
Phillips, C., Stein, C., Wein, J.: Minimizing average completion time in the presence of release dates. Mathematical Programming 82, 199–223 (1998)
Potts, C.N.: An algorithm for the single machine sequencing problem with precedence constraints. Mathematical Programming Studies 13, 78–87 (1980)
Queyranne, M.: Structure of a simple scheduling polyhedron. Mathematical Programming 58, 263–285 (1993)
Savelsbergh, M.W.P., Uma, R.N., Wein, J.M.: An experimental study of LP-based approximation algorithms for scheduling problems. In: Proceedings of the 9th Annual ACM–SIAM Symposium on Discrete Algorithms, San Francisco, CA, pp. 453–462 (1998)
Schulz, A.S.: Polytopes and scheduling. PhD thesis, TU Berlin, Germany (1996)
Schulz, A.S.: Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds. In: Cunningham, W.H., Queyranne, M., McCormick, S.T. (eds.) IPCO 1996. LNCS, vol. 1084, pp. 301–315. Springer, Heidelberg (1996)
Schulz, A.S., Skutella, M.: Random-based scheduling: New approximations and LP lower bounds. In: Rolim, J.D.P. (ed.) RANDOM 1997. LNCS, vol. 1269, pp. 119–133. Springer, Heidelberg (1997)
Schulz, A.S., Skutella, M.: The power of α-points in preemptive single machine scheduling. Journal of Scheduling 5, 121–133 (2002)
Schulz, A.S., Skutella, M.: Scheduling unrelated machines by randomized rounding. SIAM Journal on Discrete Mathematics 15, 450–469 (2002)
Schuurman, P., Woeginger, G.J.: Polynomial time approximation algorithms for machine scheduling: Ten open problems. Journal of Scheduling 2, 203–213 (1999)
Sgall, J.: On-line scheduling — a survey. In: Fiat, A. (ed.) Dagstuhl Seminar 1996. LNCS, vol. 1442, pp. 196–231. Springer, Heidelberg (1998)
Shmoys, D.B., Tardos, É.: An approximation algorithm for the generalized assignment problem. Mathematical Programming 62, 461–474 (1993)
Sidney, J.B.: Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs. Operations Research 23, 283–298 (1975)
Skutella, M.: Approximation and randomization in scheduling. PhD thesis, Technische Universität Berlin, Germany (1998)
Skutella, M., Uetz, M.: Scheduling precedence-constrained jobs with stochastic processing times on parallel machines. In: Proceedings of the 12th Annual ACM–SIAM Symposium on Discrete Algorithms, Washington, DC, pp. 589–590 (2001)
Skutella, M., Uetz, M.: Stochastic machine scheduling with precedence constraints. SIAM Journal on Computing (2005) (to appear)
Smith, W.E.: Various optimizers for single-stage production. Naval Research and Logistics Quarterly 3, 59–66 (1956)
Sousa, J.P.: Time indexed formulations of non-preemptive single-machine scheduling problems. PhD thesis, Université Catholique de Louvain (1989)
Stein, C., Wein, J.: On the existence of schedules that are near-optimal for both makespan and total weighted completion time. Operations Research Letters 21, 115–122 (1997)
Stougie, L., Vestjens, A.P.A.: Randomized algorithms for on-line scheduling problems: How low can’t you go? Operations Research Letters 30, 89–96 (2002)
Uma, R.N., Wein, J.M.: On the relationship between combinatorial and LP-based approaches to NP-hard scheduling problems. In: Bixby, R.E., Boyd, E.A., Ríos-Mercado, R.Z. (eds.) IPCO 1998. LNCS, vol. 1412, pp. 394–408. Springer, Heidelberg (1998)
Vestjens, A.P.A.: On-line machine scheduling. PhD thesis, Eindhoven University of Technology, The Netherlands (1997)
Woeginger, G.J.: On the approximability of average completion time scheduling under precedence constraints. Discrete Applied Mathematics 131, 237–252 (2003)
Wolsey, L.A.: Mixed integer programming formulations for production planning and scheduling problems (1985); Invited talk at the 12th International Symposium on Mathematical Programming. MIT, Cambridge
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Skutella, M. (2006). List Scheduling in Order of α-Points on a Single Machine. In: Bampis, E., Jansen, K., Kenyon, C. (eds) Efficient Approximation and Online Algorithms. Lecture Notes in Computer Science, vol 3484. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11671541_9
Download citation
DOI: https://doi.org/10.1007/11671541_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32212-2
Online ISBN: 978-3-540-32213-9
eBook Packages: Computer ScienceComputer Science (R0)