IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v260y2017i3p949-963.html

Changeover formulations for discrete-time mixed-integer programming scheduling models

Author

Listed:
  • Velez, Sara
  • Dong, Yachao
  • Maravelias, Christos T.

Abstract

Changeover times can have a significant impact on the scheduling of manufacturing operations. Unfortunately, accounting for changeovers in mixed-integer programming (MIP) scheduling formulations makes the resulting models computationally more expensive. We propose five new formulations for sequence-dependent changeovers, applicable to a wide range of scheduling problems. We generate constraints for different sets of time points and sets of tasks. We also propose valid inequalities for makespan minimization. Furthermore, we prove results regarding the relative tightness of each formulation. Finally, we perform a computational study. Interestingly, we find that tighter formulations do not always lead to faster solution times, and we show that some of the new formulations perform better than the previously proposed ones.

Suggested Citation

  • Velez, Sara & Dong, Yachao & Maravelias, Christos T., 2017. "Changeover formulations for discrete-time mixed-integer programming scheduling models," European Journal of Operational Research, Elsevier, vol. 260(3), pages 949-963.
    • Handle: RePEc:eee:ejores:v:260:y:2017:i:3:p:949-963
    DOI: 10.1016/j.ejor.2017.01.004
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221717300097
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2017.01.004?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. Kopanos, Georgios M. & Méndez, Carlos A. & Puigjaner, Luis, 2010. "MIP-based decomposition strategies for large-scale scheduling problems in multiproduct multistage batch plants: A benchmark scheduling problem of the pharmaceutical industry," European Journal of Operational Research, Elsevier, vol. 207(2), pages 644-655, December.
    2. Baptiste, Philippe & Peridy, Laurent & Pinson, Eric, 2003. "A branch and bound to minimize the number of late jobs on a single machine with release time constraints," European Journal of Operational Research, Elsevier, vol. 144(1), pages 1-11, January.
    3. Ruslan Sadykov & Laurence A. Wolsey, 2006. "Integer Programming and Constraint Programming in Solving a Multimachine Assignment Scheduling Problem with Deadlines and Release Dates," INFORMS Journal on Computing, INFORMS, vol. 18(2), pages 209-217, May.
    4. J. N. Hooker, 2007. "Planning and Scheduling by Logic-Based Benders Decomposition," Operations Research, INFORMS, vol. 55(3), pages 588-602, June.
    5. Wolsey, L. A., 1997. "MIP modelling of changeovers in production planning and scheduling problems," LIDAM Reprints CORE 1271, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    6. J.M. van den Akker & C.A.J. Hurkens & M.W.P. Savelsbergh, 2000. "Time-Indexed Formulations for Machine Scheduling Problems: Column Generation," INFORMS Journal on Computing, INFORMS, vol. 12(2), pages 111-124, May.
    7. Danielle Zyngier & Jeffrey D. Kelly, 2009. "Multi-Product Inventory Logistics Modeling in the Process Industries," Springer Optimization and Its Applications, in: Wanpracha Chaovalitwongse & Kevin C. Furman & Panos M. Pardalos (ed.), Optimization and Logistics Challenges in the Enterprise, pages 61-95, Springer.
    8. John N. Hooker, 2007. "Integrated Methods for Optimization," International Series in Operations Research and Management Science, Springer, number 978-0-387-38274-6, May.
    9. Vipul Jain & Ignacio E. Grossmann, 2001. "Algorithms for Hybrid MILP/CP Models for a Class of Optimization Problems," INFORMS Journal on Computing, INFORMS, vol. 13(4), pages 258-276, November.
    10. Christian Artigues & Dominique Feillet, 2008. "A branch and bound method for the job-shop problem with sequence-dependent setup times," Annals of Operations Research, Springer, vol. 159(1), pages 135-159, March.
    11. SADYKOV, Ruslan & WOLSEY, Laurence A., 2006. "Integer programming and constraint programming in solving a multimachine assignment scheduling problem with deadlines and release dates," LIDAM Reprints CORE 1854, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    12. WOLSEY, Laurence A., 1990. "Valid inequalities for 0-1 knapsacks and maps with generalised upper bound constraints," LIDAM Reprints CORE 915, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    13. Elvin Coban & J. Hooker, 2013. "Single-facility scheduling by logic-based Benders decomposition," Annals of Operations Research, Springer, vol. 210(1), pages 245-272, November.
    14. Wolsey, Laurence A., 1997. "MIP modelling of changeovers in production planning and scheduling problems," European Journal of Operational Research, Elsevier, vol. 99(1), pages 154-165, May.
    15. Uday S. Karmarkar & Linus Schrage, 1985. "The Deterministic Dynamic Product Cycling Problem," Operations Research, INFORMS, vol. 33(2), pages 326-345, April.
    16. SOUSA, Jorge P. & WOLSEY, Laurence A., 1992. "A time indexed formulation of non-preemptive single machine scheduling problems," LIDAM Reprints CORE 984, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Castro, Pedro M. & Harjunkoski, Iiro & Grossmann, Ignacio E., 2019. "Discrete and continuous-time formulations for dealing with break periods: Preemptive and non-preemptive scheduling," European Journal of Operational Research, Elsevier, vol. 278(2), pages 563-577.
    2. Hao, Jun & Li, Jianping & Wu, Dengsheng & Sun, Xiaolei, 2020. "Portfolio optimisation of material purchase considering supply risk – A multi-objective programming model," International Journal of Production Economics, Elsevier, vol. 230(C).
    3. Stéphane Dauzère-Pérès & Sigrid Lise Nonås, 2023. "An improved decision support model for scheduling production in an engineer-to-order manufacturer," 4OR, Springer, vol. 21(2), pages 247-300, June.
    4. Kramer, Arthur & Iori, Manuel & Lacomme, Philippe, 2021. "Mathematical formulations for scheduling jobs on identical parallel machines with family setup times and total weighted completion time minimization," European Journal of Operational Research, Elsevier, vol. 289(3), pages 825-840.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Elvin Coban & J. Hooker, 2013. "Single-facility scheduling by logic-based Benders decomposition," Annals of Operations Research, Springer, vol. 210(1), pages 245-272, November.
    2. Gedik, Ridvan & Rainwater, Chase & Nachtmann, Heather & Pohl, Ed A., 2016. "Analysis of a parallel machine scheduling problem with sequence dependent setup times and job availability intervals," European Journal of Operational Research, Elsevier, vol. 251(2), pages 640-650.
    3. Lotte Berghman & Roel Leus & Frits Spieksma, 2014. "Optimal solutions for a dock assignment problem with trailer transportation," Annals of Operations Research, Springer, vol. 213(1), pages 3-25, February.
    4. Laureano Escudero & Javier Salmeron, 2005. "On a Fix-and-Relax Framework for a Class of Project Scheduling Problems," Annals of Operations Research, Springer, vol. 140(1), pages 163-188, November.
    5. Vitoriano, B. & Ortuno, M. T. & Recio, B. & Rubio, F. & Alonso-Ayuso, A., 2003. "Two alternative models for farm management: Discrete versus continuous time horizon," European Journal of Operational Research, Elsevier, vol. 144(3), pages 613-628, February.
    6. Luca Benini & Michele Lombardi & Michela Milano & Martino Ruggiero, 2011. "Optimal resource allocation and scheduling for the CELL BE platform," Annals of Operations Research, Springer, vol. 184(1), pages 51-77, April.
    7. Francesco Gaglioppa & Lisa A. Miller & Saif Benjaafar, 2008. "Multitask and Multistage Production Planning and Scheduling for Process Industries," Operations Research, INFORMS, vol. 56(4), pages 1010-1025, August.
    8. Karina Copil & Martin Wörbelauer & Herbert Meyr & Horst Tempelmeier, 2017. "Simultaneous lotsizing and scheduling problems: a classification and review of models," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(1), pages 1-64, January.
    9. Roshanaei, Vahid & Luong, Curtiss & Aleman, Dionne M. & Urbach, David, 2017. "Propagating logic-based Benders’ decomposition approaches for distributed operating room scheduling," European Journal of Operational Research, Elsevier, vol. 257(2), pages 439-455.
    10. Jans, R.F. & Degraeve, Z., 2005. "Modeling Industrial Lot Sizing Problems: A Review," ERIM Report Series Research in Management ERS-2005-049-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    11. Detienne, Boris, 2014. "A mixed integer linear programming approach to minimize the number of late jobs with and without machine availability constraints," European Journal of Operational Research, Elsevier, vol. 235(3), pages 540-552.
    12. Raf Jans, 2009. "Solving Lot-Sizing Problems on Parallel Identical Machines Using Symmetry-Breaking Constraints," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 123-136, February.
    13. BELVAUX, Gaetan & WOLSEY, Laurence A., 1998. "Lot-sizing problems: modelling issues and a specialized branch-and-cut system BC-PROD," LIDAM Discussion Papers CORE 1998049, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    14. Sadykov, Ruslan, 2008. "A branch-and-check algorithm for minimizing the weighted number of late jobs on a single machine with release dates," European Journal of Operational Research, Elsevier, vol. 189(3), pages 1284-1304, September.
    15. Jans, Raf & Degraeve, Zeger, 2007. "Meta-heuristics for dynamic lot sizing: A review and comparison of solution approaches," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1855-1875, March.
    16. Meyr, H., 2000. "Simultaneous lotsizing and scheduling by combining local search with dual reoptimization," European Journal of Operational Research, Elsevier, vol. 120(2), pages 311-326, January.
    17. de Lima, Vinícius L. & Alves, Cláudio & Clautiaux, François & Iori, Manuel & Valério de Carvalho, José M., 2022. "Arc flow formulations based on dynamic programming: Theoretical foundations and applications," European Journal of Operational Research, Elsevier, vol. 296(1), pages 3-21.
    18. Nascimento, Paulo Jorge & Silva, Cristóvão & Antunes, Carlos Henggeler & Moniz, Samuel, 2024. "Optimal decomposition approach for solving large nesting and scheduling problems of additive manufacturing systems," European Journal of Operational Research, Elsevier, vol. 317(1), pages 92-110.
    19. Baptiste, Philippe & Sadykov, Ruslan, 2010. "Time-indexed formulations for scheduling chains on a single machine: An application to airborne radars," European Journal of Operational Research, Elsevier, vol. 203(2), pages 476-483, June.
    20. Daniel Kowalczyk & Roel Leus & Christopher Hojny & Stefan Røpke, 2024. "A Flow-Based Formulation for Parallel Machine Scheduling Using Decision Diagrams," INFORMS Journal on Computing, INFORMS, vol. 36(6), pages 1696-1714, December.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:260:y:2017:i:3:p:949-963. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.