Parallel Machine Scheduling, Linear Programming, and Parameter List Scheduling Heuristics

References

• van den Akker J. M. LP-based solution methods for single-machine scheduling problems. (1994) . Ph.D. Thesis, Eindhoven University of Technology, Eindhoven, The Netherlands Google Scholar
• van den Akker J. M. , Hoogeveen J. A. , van de Velde S. L. , Faigle U. , Hoede C. Parallel machine scheduling by column generation. Proc. of the 4th Twente Workshop on Graphs and Combinatorial Optimization (1995) . Also appeared as a working paper, Eindhoven University, Memorandum COSOR 95-35 Google Scholar
• Bramel J. , Simchi-Levi D. On the effectiveness of set covering formulations for the vehicle routing problem. Opns. Res. (1997) 45 295 301 Link, Google Scholar
• Chakrabarti S. , Phillips C. A. , Schulz A. S. , Schmoys D. B. , Stein C. , Wein J. , Meyer auf der Heide F. , Monien B. Improved scheduling algorithms for minsum criteria. Automata, Languages and Programming (1996) (Springer, Berlin, Germany) . number 1099 in Lecture Notes in Computer Science. Proceedings 23rd International Colloquium (ICALP '96) Crossref, Google Scholar
• Chan L. , Simchi-Levi D. , Bramel J. Worst-case analyses, linear programming and the bin-packing problem. Math. Programming (1994) . To appear in Google Scholar
• Chandra A. , Wong C. Worst-case analysis of a placement algorithm related to storage allocation. SIAM J. Comput. (1975) 4 3 249 263 Crossref, Google Scholar
• Coffman E. G. , Lueker G. S. Probabilistic Analysis of Packing and Partitioning Algorithms (1991) (John Wiley & Sons Ltd., New York) Google Scholar
• Desrochers M. , Desrosiers J. , Solomon M. A new optimization algorithm for the vehicle routing problem with time windows. Opns. Res. (1992) 40 342 354 Link, Google Scholar
• Dyer M. , Wolsey L. Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Appl. Math. (1990) 26 255 270 Crossref, Google Scholar
• Eastman W. , Even S. , Isaacs I. Bounds for the optimal scheduling of n jobs on m processors. Management Sci. (1964) 11 2 268 279 Link, Google Scholar
• Goemans M. X. , Cunningham W. H. , McCormick S. T. , Queyranne M. A supermodular relaxation for scheduling with release dates. Integer Programming and Combinatorial Optimization (1996a) (Springer, Berlin) 288 300 . number 1084 in Lecture Notes in Computer Science Crossref, Google Scholar
• Goemans M. X. Improved approximation algorithms for scheduling with release dates. (1996b) (Department of Mathematics, MIT, Cambridge, MA) Google Scholar
• Graham R. L. Bounds for certain multiprocessing anomalies. Bell System Tech. J. (1966) 45 1563 1581 Crossref, Google Scholar
• Hall L. A. , Schulz A. S. , Schmoys D. B. , Wein J. Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. (1996a) . Preprint 516/1996, Department of Mathematics, University of Technology, Berlin, Germany Google Scholar
• Hall L. A. , Schmoys D. B. , Wein J. Scheduling to minimize average completion time: Off-line and on-line algorithms. Proc. of the 7th ACMSIAM Sympos. Discrete Algorithms (1996b) 142 151 Google Scholar
• Hoffman K. L. , Padberg M. Solving airline crew scheduling problems by branch-and-cut. Management Sci. (1993) 39 657 682 Link, Google Scholar
• Johnson E. , Mehrotra A. , Nemhauser G. Mincut clustering. Math. Programming (1993) 62 133 151 Crossref, Google Scholar
• Kawaguchi T. , Kyan S. Worst-case bound of an LRF schedule for the mean weighted flow-time problem. SIAM J. Comput. (1986) 4 1119 1129 Crossref, Google Scholar
• Lash S. Scheduling parallel machines with tardiness penalties. (1994) . Ph.D. thesis, Northwestern University Google Scholar
• Lawler E. L. , Lenstra J. K. , Rinnoy Kan A. H. G. , Schmoys D. B. , Graves S. C. , Rinnooy Kan A. H. G. , Zipkin P. H. Sequencing and scheduling: Algorithms and complexity. Handbooks of Operations Research and Management Science (1993) 4 (North-Holland, Amsterdam, The Netherlands) . Logistics of Production and Inventory Google Scholar
• Möhring R. H. , Schäfter M. W. , Schulz A. S. Scheduling jobs with communication delays: Using infeasible solutions for approximation. (1996) . Lecture Notes in Computer Science. Springer. Proceedings of the 4th European Symposium on Algorithms, to appear. 1136 London, UK, 76–90 Google Scholar
• Muriel A. On the effectiveness of the set-partitioning formulation for various difficult combinatorial problems. (1997) . Ph.D. thesis, Northwestern University Google Scholar
• Pinedo M. Scheduling: Theory, Algorithms and Systems (1995) (Prentice Hall, Inc., Englewood Cliffs, New Jersey) Google Scholar
• Queyranne M. , Schulz A. Polyhedral approaches to machine scheduling. (1994) . Working Paper, University of British Columbia and Technische Universität Berlin Google Scholar
• Schulz A. S. Polytopes and scheduling. (1995) . Ph.D. thesis, University of Technology, Berlin, Germany 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) (Springer, Berlin) 301 315 . number 1084 in Lecture Notes in Computer Science Crossref, Google Scholar
• Smith W. E. Various optimizers for single-stage production. Naval Res. Logist. (1956) 3 59 66 Crossref, Google Scholar
• Spaccamela A. M. , Rhee W. S. , Stougie L. , van de Geer S. Probabilistic analysis of the minimum weighted flowtime scheduling problem. O. R. Lett. (1992) 11 67 71 Crossref, Google Scholar
• Sousa J. P. Time indexed formulations of non-preemptive single-machine scheduling problems. (1989) . Ph.D. Thesis, Université Catholique de Louvain, Belgium Google Scholar
• Sousa J. P. , Wolsey L. A. A time-indexed formulation of non-preemptive single machine scheduling problems. Math. Programming (1992) 54 353 367 Crossref, Google Scholar