Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem

References

• Ahuja R. K., Magnanti T. L., Orlin J. B.Network Flows (1993) (Prentice Hall, Englewood Cliffs, NJ) Google Scholar
• Balas E. On the facial structure of scheduling polyhedra. Math. Programming Study (1985) 24:179–218Crossref, Google Scholar
• Chekuri C., Motwani R. Precedence constrained scheduling to minimize sum of weighted completion times on a single machine. Discrete Appl. Math. (1999) 98:29–38Crossref, Google Scholar
• Davey B. A., Priestley H. A.Introduction to Lattices and Order (1990) (Cambridge University Press, Cambridge, U.K) Google Scholar
• Gallo G., Grigoriadis M. D., Tarjan R. E. A fast parametric maximum flow algorithm and applications. SIAM J. Comput. (1989) 18:30–55Crossref, Google Scholar
• Goemans M. X., Queyranne M., Schulz A. S., Skutella M., Wang Y. Single machine scheduling with release dates. SIAM J. Discrete Math. (2002) 15:165–192Crossref, Google Scholar
• Goldfarb D., Grigoriadis M. D. A computational comparison of the dinic and network simplex methods for maximum flow. Ann. Oper. Res. (1988) 13:83–123Crossref, Google Scholar
• Grätzer G.General Lattice Theory (1978) (Academic Press, New York) Crossref, Google Scholar
• Hall L. A., Schulz A. S., Shmoys D. B., Wein J. Scheduling to minimize average completion time: Off-line and online approximation algorithms. Math. Oper. Res. (1997) 22:513–544Link, Google Scholar
• Hoogeveen J. A., Van de Velde S. L. Stronger Lagrangian bounds by use of slack variables: Applications to machine scheduling problems. Math. Programming (1996) 70:173–190Google Scholar
• Hu T. C.Integer Programming and Network Flows (1970) (Addison-Wesley, Reading, MA) Google Scholar
• Lawler E. L.Combinatorial Optimization: Networks and Matroids (1976) (Holt, Rinehart and Winston, New York) Google Scholar
• Lawler E. L. Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Ann. Discrete Math. (1978) 2:75–90Crossref, Google Scholar
• Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B., Graves S. C., Rinnooy Kan A. H. G., Zipkin P. H. Sequencing and scheduling: algorithms and complexity. Logistics of Production and Inventory, Handbooks in Operations Research and Management Science (1993) 4(North-Holland, Amsterdam, The Netherlands) 445–522Crossref, Google Scholar
• McCormick S. T. Fast algorithms for parametric scheduling come from extensions to parametric maximum flow. Oper. Res. (1998) 47:744–756Link, Google Scholar
• Phillips C., Stein C., Wein J. Minimizing average completion time in the presence of release dates. Math. Programming (1998) 82:199–223Crossref, Google Scholar
• Picard J.-C. Maximum closure of a graph and application to combinatorial problems. Management Sci. (1976) 22:1268–1272Link, Google Scholar
• Picard J.-C., Queyranne M. On the structure of all minimum cuts in a network and applications. Math. Programming Study (1980) 13:8–16Crossref, Google Scholar
• Potts C. N. A Lagrangean based branch-and-bound algorithm for single machine sequencing with precedence constraints to minimize total weighted completion time. Management Sci. (1985) 31:1300–1311Link, Google Scholar
• Queyranne M. Structure of a simple scheduling polyhedron. Math. Programming (1993) 58:263–285Crossref, Google Scholar
• Queyranne M., Schulz A. S. Polyhedral approaches to machine scheduling. (1996) . Report 408/1994, Department of Mathematics, University of Technology, Berlin, Germany. November 1994, revised October 1996Google Scholar
• Queyranne M., Wang Y. Single-machine scheduling polyhedra with precedence constraints. Math. Oper. Res. (1991a) 16:1–20Link, Google Scholar
• Queyranne M., Wang Y. A cutting plane procedure for precedence-constrained single machine scheduling. (1991b) . Working paper, Faculty of Commerce, University of British Columbia, Vancouver, British Columbia, Canada, AugustGoogle Scholar
• Schulz A. S., Cunningham W. H., McCormick S. T., Queyranne M. Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds. Integer Programming and Combinatorial Optimization (1996) (Springer, Berlin, Germany) 301–315LNCS 1084Crossref, Google Scholar
• Sidney J. B. Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs. Oper. Res. (1975) 23:283–298Link, Google Scholar
• Wolsey L. A., Gabszewicz J. J., Richard J.-F., Wolsey L. A. Formulating single machine scheduling problems with precedence constraints. Economic Decision-Making: Games, Econometrics and Optimisation (1990) (North-Holland, Amsterdam, The Netherlands) 473–484Google Scholar