Solving Lot-Sizing Problems on Parallel Identical Machines Using Symmetry-Breaking Constraints

References

• Ahmadi R. H., Dasu S., Tang C. S. The dynamic line allocation problem. Management Sci. (1992) 38(9):1341–1353Link, Google Scholar
• Artiouchine K., Baptiste P., van Beek P. Inter-distance constraint: An extension of the all-different constraint for scheduling equal length jobs. Principles and Practice of Constraint Programming (CP 2005), Lecture Notes in Computer Science (2005) 3709(Springer, Berlin) 62–76Crossref, 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. Oper. Res. (1998) 46(3):316–329Link, Google Scholar
• Baptiste P., Le Pape C., Nuijten W.Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems (2001) (Kluwer Academic Publishers, Boston) Crossref, Google Scholar
• Belvaux G., Wolsey L. A. Modelling practical lot-sizing problems as mixed-integer programs. Management Sci. (2001) 47(7):993–1007Link, Google Scholar
• Ben Amor H., de Carvalho J. V., Desaulniers G., Desrosiers J., Solomon M. Cutting stock problems. Column Generation (2005) (Springer, New York) 131–162Crossref, Google Scholar
• Brailsford S., Potts C., Smith B. M. Constraint satisfaction problems: Algorithms and applications. Eur. J. Oper. Res. (1999) 119:557–581Crossref, Google Scholar
• Caseau Y., Laburthe F., Deza M., Euler R., Manoussakis I. Improving branch and bound for jobshop scheduling with constraint propagation. Combinatorics and Computer Science: 8th Franco-Japanese and 4th Franco-Chinese Conf., Lecture Notes in Computer Science (1995) 1120(Springer, Berlin) 129–149Google Scholar
• Cheng C.-C., Smith S. F. Applying constraint satisfaction techniques to job shop scheduling. Ann. Oper. Res. (1997) 70:327–357Crossref, Google Scholar
• Clark A. R. Optimization approximations for capacity constrained material requirements planning. Internat. J. Production Econom. (2003) 84(2):115–131Crossref, Google Scholar
• Clark A. R., Clark S. J. Rolling-horizon lot-sizing when set-up times are sequence-dependent. Internat. J. Production Res. (2000) 38(10):2287–2307Crossref, Google Scholar
• Darby-Dowman K., Little J. Properties of some combinatorial optimization problems and their effect on the performance of integer programming and constraint logic programming. INFORMS J. Comput. (1998) 10(3):276–286Link, Google Scholar
• Dastidar S. G., Nagi R. Scheduling injection molding operations with multiple resource constraints and sequence dependent setup times and costs. Comput. Oper. Res. (2005) 32:2987–3005Crossref, Google Scholar
• Degraeve Z., Jans R. A new Dantzig-Wolfe reformulation and branch-and-price algorithm for the capacitated lot sizing problem with set up times. Oper. Res. (2007) 55(5):909–920Link, Google Scholar
• Degraeve Z., Gochet W., Jans R. Alternative formulations for a layout problem in the fashion industry. Eur. J. Oper. Res. (2002) 143(1):80–93Crossref, Google Scholar
• De Matta R., Guignard M. Dynamic production scheduling for a process industry. Oper. Res. (1994a) 42(3):492–503Link, Google Scholar
• De Matta R., Guignard M. Studying the effects of production loss due to setup in dynamic production scheduling. Eur. J. Oper. Res. (1994b) 72:62–73Crossref, Google Scholar
• De Matta R., Guignard M. The performance of rolling production schedules in a process industry. IIE Trans. (1995) 27(5):564–573Crossref, Google Scholar
• Dillenberger C., Escudero L. F., Wollensak A., Zhang W. On practical resource allocation for production planning and scheduling with period overlapping setups. Eur. J. Oper. Res. (1994) 75:275–286Crossref, Google Scholar
• Dos Santos-Meza E., Dos Santos M. O., Arenales M. N. A lot-sizing problem in an automated foundry. Eur. J. Oper. Res. (2002) 139:490–500Crossref, Google Scholar
• Dumoulin A., Vercellis C. Tactical models for hierarchical capacitated lot-sizing problems with set-ups and changeovers. Internat. J. Production Res. (2000) 38(1):51–67Crossref, Google Scholar
• Eppen G. D., Martin R. K. Solving multi-item capacitated lot-sizing problems using variable redefinition. Oper. Res. (1987) 35(6):832–848Link, Google Scholar
• Fahle T., Schambergerm S., Sellmann M., Walsh T. Symmetry breaking. Principles and Practice of Constraint Programming (CP 2001), Lecture Notes in Computer Science (2001) 2239(Springer, Berlin) 93–107Crossref, Google Scholar
• Focacci F., Milano M., Walsh T. Global cut framework for removing symmetries. Principles and Practice of Constraint Programming (CP 2001), Lecture Notes in Computer Science (2001) 2239(Springer, Berlin) 77–92Crossref, Google Scholar
• Frisch A. M., Miguel I., Walsh T. Symmetry and implied constraints in the steel mill slab design problem. Proc. CP-2001 Workshop on Modelling and Problem Formulation (Formul'01) (2001) Paphos, Cyprus:8–15Google Scholar
• Gent I. P., Smith B. Symmetry during search in constraint programming. (1999) . Research Report 99.02, School of Computer Studies, University of Leeds, Leeds, UKGoogle Scholar
• Gent I. P., Petrie K. E., Puget J.-F., Rossi F., van Beek P., Walsh T. Symmetry in constraint programming. Handbook of Constraint Programming (2006) (Elsevier, New York) 329–376Crossref, Google Scholar
• Gent I. P., Kelsey T., Linton S. A., McDonald I., Miguel I., Smith B. M., van Beek P. Conditional symmetry breaking. Principles and Practice of Constraint Programming (CP 2005), Lecture Notes in Computer Sciemce (2005) 3709(Springer, Berlin) 256–270Crossref, Google Scholar
• Gopalakrishnan M., Miller D. M., Schmidt C. P. A framework for modeling setup carryover in the capacitated lot sizing problem. Internat. J. Production Res. (1995) 33(7):1973–1988Crossref, Google Scholar
• Gopalakrishnan M., Ding K., Bourjolly J. M., Mohanm S. A tabu-search heuristic for the capacitated lot-sizing problem with set-up carryover. Management Sci. (2001) 47(6):851–863Link, Google Scholar
• Hooker J. N. Logic, optimization and constraint programming. INFORMS J. Comput. (2002) 14(4):295–321Link, Google Scholar
• Hooker J. N. A hybrid method for planning and scheduling. Constraints (2005) 10:385–401Crossref, Google Scholar
• Hooker J. N. An integrated method for planning and scheduling to minimize tardiness. Constraints (2006) 11:139–157Crossref, Google Scholar
• Hung Y. F., Cheng G. J. Hybrid capacity modeling for alternative machine types in linear programming production planning. IIE Trans. (2002) 34(2):157–165Crossref, Google Scholar
• Jain V., Grossmann I. E. Algorithms for hybrid MILP/CP models for a class of optimization problems. INFORMS J. Comput. (2001) 13(4):258–276Link, Google Scholar
• Jans R., Degraeve Z. Improved lower bounds for the capacitated lotsizing problem with setup times. Oper. Res. Lett. (2004a) 32:185–195Crossref, Google Scholar
• Jans R., Degraeve Z. An industrial extension of the discrete lot sizing and scheduling problem. IIE Trans. (2004b) 36(1):47–58Crossref, Google Scholar
• Jans R., Degraeve Z. Meta-heuristics for lot sizing problems: Review and comparison of solution approaches. Eur. J. Oper. Res. (2007) 177:1855–1875Crossref, Google Scholar
• Jans R., Degraeve Z. Modeling industrial lot sizing problems: A review. Internat. J. Production Res. (2008) 46(6):1619–1643Crossref, Google Scholar
• Jordan C., Drexl A. A comparison of constraint and mixed-integer programming solvers for batch sequencing with sequence-dependent setups. INFORMS J. Comput. (1995) 7(2):180–185Link, Google Scholar
• Kaibel V., Pfetsch M. E. Packing and partitioning orbitopes. Math. Programming (2008) 114:1–36Crossref, Google Scholar
• Kang S., Malik K., Thomas L. J. Lotsizing and scheduling on parallel machines with sequence-dependent setup costs. Management Sci. (1999) 45(2):273–289Link, Google Scholar
• Kimms A., Drexl A. Proportional lot sizing and scheduling: Some extenstions. Networks (1998) 32:85–101Crossref, Google Scholar
• Law Y. C., Lee J. H. M. Symmetry breaking constraints for value symmetries in constraint satisfaction. Constraints (2006) 11:221–267Crossref, Google Scholar
• Leachman R. C., Carmon T. F. On capacity modeling for production planning with alternative machine types. IIE Trans. (1992) 24(4):62–72Crossref, Google Scholar
• Le Pape C., Baptiste P. Resource constraints for preemptive job-shop scheduling. Constraints (1998) 3:263–287Crossref, Google Scholar
• Madan M. S., Gilbert K. C. An exact solution algorithm for a class of production planning and scheduling problems. J. Oper. Res. Soc. (1992) 43(10):961–970Crossref, Google Scholar
• Margot F. Pruning by isomorphism in branch-and-cut. Math. Programming Ser. A (2002) 94:71–90Crossref, Google Scholar
• Margot F. Exploiting orbits in symmetric ILP. Math. Programming Ser. B (2003) 98:3–21Crossref, Google Scholar
• Margot F. Symmetric ILP: Coloring and small integers. Discrete Optim. (2007) 4:40–62Crossref, Google Scholar
• Mehrotra A., Trick M. A. A column generation approach for graph coloring. INFORMS J. Comput. (1996) 8(4):344–354Link, Google Scholar
• Meyr H. Simultaneous lotsizing and scheduling on parallel machines. Eur. J. Oper. Res. (2002) 139:277–292Crossref, Google Scholar
• Nuijten W., Le Pape C. Constraint-based job shop scheduling with ILOG scheduler. J. Heuristics (1998) 3:271–286Crossref, Google Scholar
• Nuijten W. P. M., Aarts E. H. L. A computational study of constraint satisfaction for multiple capacitated job shop scheduling. Eur. J. Oper. Res. (1996) 90:269–284Crossref, Google Scholar
• Ottosson G., Thorsteinsson E. S., Hooker J. N. Mixed global constraints and inference in hybrid CLP-IP solvers. Ann. Math. Artificial Intelligence (2002) 34:271–290Crossref, Google Scholar
• Özdamar L., Barbarosoğlu G. Hybrid heuristics for the multi-stage capacitated lot sizing and loading problem. J. Oper. Res. Soc. (1999) 50:810–825Crossref, Google Scholar
• Özdamar L., Birbil S. I. Hybrid heuristics for the capacitated lot sizing and loading problem with setup times and overtime decisions. Eur. J. Oper. Res. (1998) 110:525–547Crossref, Google Scholar
• Plastria F. Formulating logical implications in combinatorial optimization. Eur. J. Oper. Res. (2002) 140:338–353Crossref, Google Scholar
• Pochet Y., Wolsey L. A.Production Planning by Mixed Integer Programming (2006) (Springer, New York) Google Scholar
• Proll L., Smith B. Integer linear programming and constraint programming approaches to a template design problem. INFORMS J. Comput. (1998) 10(3):265–275Link, Google Scholar
• Puget J.-F. Symmetry breaking revisited. Constraints (2005a) 10:23–46Crossref, Google Scholar
• Puget J.-F., van Beek P. Automatic detection of variable and value symmetry. Principles and Practice of Constraint Programming (CP 2005), Lecture Notes in Computer Science (2005b) 3709(Springer, Berlin) 475–489Crossref, Google Scholar
• Sadykov R., Wolsey L. A. Integer programming and constraint programming solving a multimachine assignment scheduling problem with deadlines and release dates. INFORMS J. Comput. (2006) 18(2):209–217Link, Google Scholar
• Salomon M., Kroon L. G., Kuik R., Van Wassenhove L. N. Some extensions of the discrete lotsizing and scheduling problem. Management Sci. (1991) 37(7):801–812Link, Google Scholar
• Sellmann M., Van Hentenryck P. Structural symmetry breaking. Proc. Joint Internat. Conf. Artificial Intelligence (IJCAI'05) (2005) Edinburgh, UK:298–303Google Scholar
• Sherali H. D., Smith J. C. Improving discrete model representations via symmetry considerations. Management Sci. (2001) 47(10):1396–1407Link, Google Scholar
• Sherali H. D., Fraticelli B. M. P., Meller R. D. Enhanced model formulation for optimal facility layout. Oper. Res. (2003) 51(4):629–644Link, Google Scholar
• Sherali H. D., Smith J. C., Lee Y. Enhanced model representations for an intra-ring synchronous optical network design problem allowing demand splitting. INFORMS J. Comput. (2000) 12(4):284–298Link, Google Scholar
• Smith B. Reducing symmetry in a combinatorial design problem. Proc. CP-AI-OR'01, Third Internat. Workshop Integration AI OR Techniques Constraint Programming Combin. Optim. Problems (2001) Wye College (Imperial College), Ashford, Kent, UKGoogle Scholar
• Sox C. R., Gao Y. The capacitated lot sizing problem with setup carry-over. IIE Trans. (1999) 31(2):173–181Crossref, Google Scholar
• Stadtler H. Multilevel lot sizing with setup times and multiple constrained resources: Internally rolling schedules with lot-sizing windows. Oper. Res. (2003) 51(3):487–502Link, Google Scholar
• Suerie C., Stadtler H. The capacitated lot-sizing problem with linked lot sizes. Management Sci. (2003) 49(8):1039–1054Link, Google Scholar
• Timpe C. Solving planning and scheduling problems with combined integer and constraint programming. OR Spectrum (2002) 24:431–448Crossref, Google Scholar
• Trigeiro W., Thomas L. J., McClain J. O. Capacitated lot sizing with set-up times. Management Sci. (1989) 35(3):353–366Link, Google Scholar
• Vanderbeck F. Lot-sizing with start-up times. Management Sci. (1998) 44(10):1409–1425Link, Google Scholar
• Van Hentenryck P. Constraint and integer programming in OPL. INFORMS J. Comput. (2002) 14(4):345–372Link, Google Scholar
• Wagner H. M., Whitin T. M. Dynamic version of the economic lot size model. Management Sci. (1958) 5(1):89–96Link, Google Scholar
• Wolsey L. A. Solving multi-item lot-sizing problems with an MIP solver using classification and reformulation. Management Sci. (2002) 48(12):1587–1602Link, Google Scholar