Single-Machine Scheduling with Precedence Constraints

References

• Balas E. On the facial structure of scheduling polyhedra. Math. Programming Stud. (1985) 24:179–218Crossref, Google Scholar
• Balinski M. On a selection problem. Management Sci. (1970) 17:230–231Link, Google Scholar
• Chang G. J., Edmonds J. The poset scheduling problem. Order (1985) 2:113–118Crossref, Google Scholar
• Chekuri C., Motwani R. Precedence constrained scheduling to minimize sum of weighted completion time on a single machine. Discrete Appl. Math. (1999) 98:29–38Crossref, Google Scholar
• Chudak F. A., Hochbaum D. S. A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine. Oper. Res. Lett. (1999) 25:199–204Crossref, Google Scholar
• Dushnik B., Miller E. W. Partially ordered sets. Amer. J. Math. (1941) 63:600–610Crossref, Google Scholar
• Dyer M. E., Wolsey L. A. Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Appl. Math. (1990) 26:255–270Crossref, Google Scholar
• Eastman W. L., Even S., Isaacs I. Bounds for the optimal scheduling of n jobs on m processors. Management Sci. (1964) 11:268–279Link, Google Scholar
• Goemans M. X., Williamson D. P. Two-dimensional Gantt charts and a scheduling algorithm of Lawler. SIAM J. Discrete Math. (2000) 13:281–294Crossref, Google Scholar
• Graham R. L., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G. Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Math. (1979) 5:287–326Crossref, Google Scholar
• Hall L. A., Shmoys D. B., Wein J. Scheduling to minimize average completion time: Off-line and on-line algorithms. Proc. 7th Annual ACM-SIAM Sympos. on Discrete Algorithms (1996) Atlanta, GA(SIAM, Philadelphia, PA) 142–151Google Scholar
• Hall L. A., Schulz A. S., Shmoys D. B., Wein J. Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Math. Oper. Res. (1997) 22:513–544Link, Google Scholar
• Hochbaum D. S. Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Appl. Math. (1983) 6:243–254Crossref, Google Scholar
• Kolliopoulos S. G., Steiner G., Möhring R. H., Raman R. Partially-ordered knapsack and applications to scheduling. Algorithms–ESA 2002 (2002) 2461(Springer, Heidelberg, Germany) 612–624Lecture Notes in Computer ScienceCrossref, 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
• Lenstra J. K., Rinnooy Kan A. H. G. Complexity of scheduling under precedence constraints. Oper. Res. (1978) 26:22–35Link, Google Scholar
• Margot F., Queyranne M., Wang Y. Decompositions, network flows, and a precedence constrained single-machine scheduling problem. Oper. Res. (2003) 51:981–992Link, Google Scholar
• Möhring R. H., Rival I. Computationally tractable classes of ordered sets. Algorithms and Order (1989) (Kluwer Academic, Dordrecht, The Netherlands) 105–193Crossref, Google Scholar
• Nemhauser G. L., Trotter L. E. Properties of vertex packing and independence system polyhedra. Math. Programming (1974) 6:48–61Crossref, Google Scholar
• Nemhauser G. L., Trotter L. E. Vertex packing: Structural properties and algorithms. Math. Programming (1975) 8:232–248Crossref, Google Scholar
• Ore O.Theory of Graphs (1962) XXXVIII(Providence, RI). Colloquium Publications. American Mathematical SocietyCrossref, Google Scholar
• Picard J.-C. Maximal closure of a graph and applications 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 Stud. (1980) 13:8–16Crossref, Google Scholar
• Pnueli A., Lempel A., Even S. Transitive orientation of graphs and identification of permutation graphs. Canadian J. Math. (1971) 23:160–175Crossref, Google Scholar
• Potts C. N. An algorithm for the single machine sequencing problem with precedence constraints. Math. Programming Stud. (1980) 13:78–87Crossref, 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. (1994) . Technical report 408/1994, Department of Mathematics, Technische Universität Berlin, Berlin, GermanyGoogle Scholar
• Queyranne M., Wang Y. Single-machine scheduling polyhedra with precedence constraints. Math. Oper. Res. (1991) 16:1–20Link, Google Scholar
• Rhys J. M. W. A selection problem of shared fixed costs and network flows. Management Sci. (1970) 17:200–207Link, Google 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) 1084(Springer, Heidelberg, Germany) 301–315Lecture Notes in Computer ScienceCrossref, Google Scholar
• Schulz A. S., Skutella M., Rolim J. D. P. Random-based scheduling: New approximations and LP lower bounds. Randomization and Approximation Techniques in Computer Science (1997) 1269(Springer, Heidelberg, Germany) 119–133Lecture Notes in Computer ScienceCrossref, Google Scholar
• Sidney J. B. Decomposition algorithms for single machine scheduling with precedence relations and deferral costs. Oper. Res. (1975) 23:283–298Link, Google Scholar
• Smith W. E. Various optimizers for single-stage production. Naval Res. Logist. Quart. (1956) 3:59–66Crossref, Google Scholar
• Woeginger G. J. On the approximability of average completion time scheduling under precedence constraints. Discrete Appl. Math. (2003) 131:237–252Crossref, Google Scholar
• Wolsey L. A. Mixed integer programming formulations for production planning and scheduling problems. (1985) Invited talk at the 12th Internat. Sympos. Math. Programming(MIT, Cambridge, MA) 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