Combining Column Generation and Lagrangean Relaxation to Solve a Single-Machine Common Due Date Problem

References

• van den Akker J. M., Hoogeveen J. A., van de Velde S. L. A column generation algorithm for common due date scheduling. (1996) . Working Paper LPOM-96-13, Faculty ofMechanical Engineering, University of Twente, Enschede, The NetherlandsGoogle Scholar
• van den Akker J. M., Hoogeveen J. A., van de Velde S. L. Parallel machine scheduling by column generation. Operations Research (1999) 47:862–872Link, Google Scholar
• van den Akker J. M., Hurkens C. A. J., Savelsbergh M. W. P. Time-indexed formulations for machine scheduling problems: column generation. INFORMS Journal on Computing (2000) 12:111–124Link, Google Scholar
• Baker K. R., Scudder G. D. On the assignment ofoptimal due dates. Journal of the Operational Research Society (1989) 40:93–95Crossref, Google Scholar
• Baker K. R., Scudder G. D. Sequencing with earliness and tardiness penalties: a review. Operations Research (1990) 38:22–36Link, Google Scholar
• Barnhart C., Johnson E. L., Nemhauser G.L., Savelsbergh M. W. P., Vance P. H. Branch-and-price: column generation for solving huge integer programs. Operations Research (1998) 46:316–329Link, Google Scholar
• Bazaraa M. S., Jarvis J. J., Sherali H. D.Linear Programming and Network Flows (1990) (Wiley, New York) Google Scholar
• Chan L. M. A., Muriel A., Simchi-Levi D. Parallel machine scheduling, linear programming, and parameter list scheduling heuristics. Operations Research (1998) 46:729–741Link, Google Scholar
• Chen Z. L., Powell W. P. Solving parallel machine scheduling problems by column generation. INFORMS Journal on Computing (1999a) 11:78–94Link, Google Scholar
• Chen Z. L., Powell W. P. A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem. European Journal of Operational Research (1999b) 116:220–232Crossref, Google Scholar
• CPLEX Optimization, IncUsing the cplex™Linear Optimizer (1990) Google Scholar
• De P., Ghosh J., Wells C. E. Solving a generalized model for CON due-date assignment and scheduling. International Journal of Production Economics (1994) 34:179–185Crossref, Google Scholar
• Desrochers M., Desrosiers J., Solomon M. A new optimization algorithm for the vehicle routing problem with time windows. Operations Research (1992) 40:432–354Link, Google Scholar
• Desrosiers J., Dumas Y., Salomon M. M., Soumis F. Time constrained routing and scheduling. Handbooks in Operations Research and Management Science (1995) 8(Elsevier, Amsterdam, The Netherlands) 35–139Volume on Network RoutingCrossref, Google Scholar
• Farley A. A. A note on bounding a class oflinear programming problems, including cutting stock problems. Operations Research (1990) 38:922–923Link, Google Scholar
• Fisher M. L. The Lagrangean relaxation method for solving integer programming problems. Management Science (1981) 27:1–18Link, Google Scholar
• Freling R.Models and techniques for integrating vehicle and crew scheduling (1997) . Ph.D. Thesis, Erasmus University, Rotterdam, The NetherlandsGoogle Scholar
• Geoffrion A. M. Lagrangean relaxation for integer programming. Mathematical Programming Study (1974) 2:82–114Crossref, Google Scholar
• Hall N. G., Posner M. E. Earliness-tardiness scheduling problems. I: Weighted deviation of completion times about a common due date. Operations Research (1991) 39:836–846Link, Google Scholar
• Hall N. G., Sriskandarajah C. The earliness-tardiness problem with asymmetric weights. (1990) Las Vegas, NevadaPresented at the TIMS/ORSA Joint National MeetingGoogle Scholar
• Hoogeveen J. A., Oosterhout H., van de Velde S. L. New lower and upper bounds for scheduling around a small common due date. Operations Research (1994) 42:102–110Link, Google Scholar
• Mehrotra A., Trick M. A. A column generation approach for graph coloring. INFORMS Journal on Computing (1997) 8:344–354Link, Google Scholar
• Pardalos P. M., Rodgers G. P. Computational aspects of a branch-and-bound algorithm for zero-one programming. Computing (1990) 45:131–144Crossref, Google Scholar
• Quaddus M. A. A generalized model ofoptimal due date assignment by linear programming. Journal of the Operational Research Society (1987) 38:353–359Crossref, Google Scholar
• Savelsbergh M. W. P. A branch-and-price algorithm for the generalized assignment problem. Operations Research (1997) 45:831–841Link, Google Scholar
• Soumis F., Dell'Amico M., Maffioli F., Martello S. Decomposition and column generation. Annotated Bibliography of Combinatorial Optimization (1997) (Wiley, Chichester, UK) Google Scholar
• Vanderbeck F. Computational study of a column generation algorithm for bin packing and cutting stock problems. Mathematical Programming (1999) 86:565–594Crossref, Google Scholar
• Vanderbeck F. On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and price algorithm. Operations Research (2000) 48:111–128Link, Google Scholar
• Vanderbeck F., Wolsey L. A. An exact algorithm for IP column generation. Operations Research Letters (1996) 19:151–159Crossref, Google Scholar
• Wolsey L. A.Integer Programming (1998) (Wiley, New York) Google Scholar