Solving Parallel Machine Scheduling Problems by Column Generation

References

• Baker K. R. Introduction to Sequencing and Scheduling (1994) (Wiley, New York) Google Scholar
• Barnes J. W. , Brennan J. J. An improved algorithm for scheduling jobs on identical machines. AIIE Trans. (1977) 9 25 31 Crossref, Google Scholar
• Barnhart C. , Johnson E. , Nemhauser G. L. , Savelsberg M. W. P. , Vance P. H. Branch-and-price: Column generation for solving huge integer programs. Math. Programming: State of the Art (1994) 186 207 Google Scholar
• Belouadah H. , Potts C. N. Scheduling identical parallel machines to minimize total weighted completion time. Discrete Appl. Math. (1995) 48 201 218 Crossref, Google Scholar
• Bondy J. A. , Murty U. S. R. Graph Theory with Applications (1976) (Elsevier Science Publishing Co. Inc., North Holland, Amsterdam) Crossref, Google Scholar
• Cattrysse D. , Salomon M. , Kuik R. , Van Wassenhove L. N. A dual ascent and column generation heuristic for the discrete lotsizing and scheduling problem with setup times. Management Sci. (1993) 39 477 486 Link, Google Scholar
• Chan L. M. A. , Kaminsky P. , Muriel A. , Simchi-Levi D. Machine scheduling, linear programming and list scheduling heuristic. (1995) . Technical report, Northwestern University, Chicago Google Scholar
• Chen Z.-L. , Powell W. B. A decomposition approach for a parallel machine just-in-time scheduling problem. (1996) . Technical report, Statistics and Operation Research, Princeton University Google Scholar
• Cheng T. C. E. , Sin C. C. S. A state-of-the-art review of parallel-machine scheduling research. Eur. J. Oper. Res. (1990) 47 271 292 Crossref, Google Scholar
• Dantzig G. B. , Wolfe P. Decomposition principle for linear programs. Oper. Res. (1960) 8 101 111 Link, Google Scholar
• De P. , Ghosh J. B. , Wells C. E. Due-date assignment and early/tardy scheduling on identical parallel machines. Naval Res. Logist. (1994) 41 17 32 Crossref, Google Scholar
• Desrochers M. , Desrosiers J. , Solomon M. A new optimizataion algorithm for the vehicle routing problem with time windows. Oper. Res. (1992) 40 342 354 Link, Google Scholar
• Eastman W. L. , Even S. , Isaacs I. M. Bounds for the optimal scheduling of n jobs on m processors. Management Sci. (1974) 11 268 279 Link, Google Scholar
• Elmaghraby S. E. , Park S. H. Scheduling jobs on a number of identical machines. AIIE Trans. (1974) 6 1 12 Crossref, Google Scholar
• Garey M. R. , Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) (Freeman, San Francisco, CA) Google Scholar
• Gilmore P. C. , Gomory R. E. A linear programming approach to the cutting-stock problem. Oper. Res. (1961) 9 849 859 Link, Google Scholar
• Ho J. C. , Chang Y.-L. Heuristics for minimizing mean tardiness for m parallel machines. Naval Res. Logist. (1991) 38 367 381 Crossref, Google Scholar
• Ho J. C. , Chang Y.-L. Minimizing the number of tardy jobs for m parallel machines. Eur. J. Oper. Res. (1995) 84 343 355 Crossref, Google Scholar
• Karp R. M. , Miller R. E. , Thatcher J. W. Reducibility among combinatorial problems. Complexity of Computations (1972) (Plenum Press, New York) Crossref, Google Scholar
• Lasdon L. S. Optimization Theory for Large Systems (1970) (Mac-Millan, New York) Google Scholar
• Lavoie S. , Minoux M. , Odier E. A new approach for crew pairing problems by column generation with an application to air transport. Eur. J. Oper. Res. (1988) 35 45 58 Crossref, 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 (1993) (North Holland, Amsterdam) Crossref, Google Scholar
• Lawler E. L. , Moore J. M. A functional equation and its applications to resource allocation and sequencing problems. Management Sci. (1969) 16 77 84 Link, Google Scholar
• Mehrotra A. , Trick M. A. A column generation approach to graph coloring. (1993) . Technical report, Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PA Google Scholar
• Nemhauser G. , Wolsey L. Integer and Combinatorial Optimization (1988) (John Wiley & Sons, Inc., Chichester, UK) Crossref, Google Scholar
• Pinedo M. Scheduling: Theory, Algorithm, and System (1995) (Prentice Hall, Englewood Cliffs, NJ) Google Scholar
• Rothkopf M. H. Scheduling independent tasks on parallel processors. Management Sci. (1966) 12 437 447 Link, Google Scholar
• Sarin S. C. , Ahn S. , Bishop A. B. An improved scheme for the branch and bound procedure of scheduling n jobs on m parallel machines to minimize total weighted flowtime. Internat. J. Production Res. (1988) 26 1183 1191 Crossref, Google Scholar
• Smith W. E. Various optimizer for single-stage production. Naval Res. Logist. Quart. (1956) 3 59 66 Crossref, Google Scholar
• van den Akker J. M. , Hoogeveen J. A. , van de Velde S. L. Parallel machine scheduling by column generation. (1995) . Technical report, Center for Operations Research and Econometrics, Universite Catholique de Louvain, Belgium Google Scholar
• Vance P. H. Crew scheduling cutting stock, and column generation: Solving huge integer programs. (1993) . Technical report, Ph.D. dissertation, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA Google Scholar
• Vance P. H. , Barnhart C. , Johnson E. L. , Nemhauser G. L. Solving binary cutting stock problems by column generation and branch-and-bound. Comput. Optim. Appl. (1994) 3 111 130 Crossref, Google Scholar
• Webster S. New bounds for the identical parallel processor weighted flow time problem. Management Sci. (1992) 38 124 136 Link, Google Scholar
• Webster S. A priority rule for minimizing weighted flow time in a class of parallel machine scheduling problems. Eur. J. Oper. Res. (1993) 70 327 334 Crossref, Google Scholar
• Webster S. Weighted flow time bounds for scheduling identical processors. Eur. J. Oper. Res. (1995) 80 103 111 Crossref, Google Scholar