Abstract
We discuss the problem of sequencing precedence-constrained jobs on a single machine to minimize the average weighted completion time. This problem has attracted much attention in the mathematical programming community since Sidney’s pioneering work in 1975. We look at the problem from a polyhedral perspective and uncover a relation between Sidney’s decomposition theorem and different linear programming relaxations. More specifically, we present a generalization of Sidney’s result, which particularly allows us to reason that virtually all known 2-approximation algorithms comply with his decomposition. Moreover, we establish a connection between the single-machine scheduling problem and the vertex cover problem. Indeed, in the special case of series-parallel precedence constraints, we prove that the sequencing problem can be seen as a special case of vertex cover. We also argue that this result is true for general precedence constraints if one can show that a certain integer program represents a valid formulation of the sequencing problem. Finally, we provide a characterization of the active inequalities of a linear programming relaxation in completion time variables.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Balas, E.: On the facial structure of scheduling polyhedra. Mathematical Programming Study 24, 179–218 (1985)
Chekuri, C., Motwani, R.: Precedence constrained scheduling to minimize sum of weighted completion time on a single machine. Discrete Applied Mathematics 98, 29–38 (1999)
Chudak, F., Hochbaum, D.S.: A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine. Operations Research Letters 25, 199–204 (1999)
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)
Eastman, W.L., Even, S., Isaacs, I.M.: Bounds for the optimal scheduling of n jobs on m processors. Management Science 11, 268–279 (1964)
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., 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, pp. 142–151 (1996)
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)
Hochbaum, D.S.: Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Applied Mathematics 6, 243–254 (1983)
Kolliopoulos, S., Steiner, G.: Partially-ordered knapsack and applications to scheduling. In: Möhring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 612–624. Springer, Heidelberg (2002)
Lawler, E.L.: Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Annals of Discrete Mathematics 2, 75–90 (1978)
Lenstra, J.K., Rinnooy Kan, A.H.G.: Complexity of scheduling under precedence constraints. Operations Research 26, 22–35 (1978)
Margot, F., Queyranne, M., Wang, Y.: Decompositions, network flows, and a precedence constrained single-machine scheduling problem. Operations Research 51, 981–992 (2003)
Nemhauser, G.L., Trotter, L.E.: Vertex packing: Structural properties and algorithms. Mathematical Programming 8, 232–248 (1978)
Picard, J.C.: Maximum closure of a graph and applications to combinatorial problems. Management Science 22, 1268–1272 (1976)
Potts, C.N.: An algorithm for the single machine sequencing problem with precedence constraints. Mathematical Programming Study 13, 78–87 (1980)
Queyranne, M.: Structure of a simple scheduling polyhedron. Mathematical Programming 58, 263–285 (1993)
Queyranne, M., Schulz, A.S.: Polyhedral approaches to machine scheduling. Technical Report 408, Department of Mathematics, Technische Universität Berlin, Germany (1994)
Queyranne, M., Wang, Y.: Single-machine scheduling polyhedra with precedence constraints. Mathematics of Operations Research 16, 1–20 (1991)
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)
Sidney, J.B.: Decomposition algorithms for single machine scheduling with precedence relations and deferral costs. Operations Research 23, 283–298 (1975)
Smith, W.E.: Various optimizers for single-stage production. Naval Research and Logistics Quarterly 3, 59–66 (1956)
Woeginer, 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. Invited talk at the 12th International Symposium on Mathematical Programming, MIT, Cambridge (1985)
Wolsey, L.A.: Formulating single machine scheduling problems with precedence constraints. In: Gabszewic, J.J., Richard, J.F., Wolsey, L.A. (eds.) Economic Decision-Making: Games, Econometrics and Optimisation, pp. 473–484. North-Holland, Amsterdam (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Correa, J.R., Schulz, A.S. (2004). Single Machine Scheduling with Precedence Constraints. In: Bienstock, D., Nemhauser, G. (eds) Integer Programming and Combinatorial Optimization. IPCO 2004. Lecture Notes in Computer Science, vol 3064. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-25960-2_22
Download citation
DOI: https://doi.org/10.1007/978-3-540-25960-2_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22113-5
Online ISBN: 978-3-540-25960-2
eBook Packages: Springer Book Archive