IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v278y2019i2p563-577.html
   My bibliography  Save this article

Discrete and continuous-time formulations for dealing with break periods: Preemptive and non-preemptive scheduling

Author

Listed:
  • Castro, Pedro M.
  • Harjunkoski, Iiro
  • Grossmann, Ignacio E.

Abstract

This paper presents new mixed-integer linear programming (MILP) approaches for handling preemption both in discrete and continuous-time scheduling formulations. Preemption refers to the capability of interrupting the execution of a task when encountering a pre-defined break period, assuming that the task continues immediately after the end of such time window. We rely on Generalized Disjunctive Programming to derive the constraints for the continuous-time formulations and on a compact convex hull reformulation to make them computationally efficient. We investigate both the general precedence and multiple time grids representation concepts. Generalization of the discrete-time formulation is simpler, involving a change in the model parameters. Validation and comparison of the mathematical formulations is done through the solution of sixteen benchmark problems, involving instances with one to four sets of breaks. The results show that the general precedence formulation is computationally more effective for flexible flowshops, being outperformed by the discrete-time approach when considering common rather than machine-dependent breaks. For single stage plants with parallel units, the continuous multiple time grid formulation prevails.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:278:y:2019:i:2:p:563-577
    DOI: 10.1016/j.ejor.2019.04.025
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221719303595
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2019.04.025?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 search for a different version of it.

    References listed on IDEAS

    as
    1. Kress, Dominik & Dornseifer, Jan & Jaehn, Florian, 2019. "An exact solution approach for scheduling cooperative gantry cranes," European Journal of Operational Research, Elsevier, vol. 273(1), pages 82-101.
    2. Edmund Burke & Michael Pinedo, 2019. "Journal of scheduling (2019)," Journal of Scheduling, Springer, vol. 22(1), pages 1-2, February.
    3. Mosheiov, Gur & Sarig, Assaf & Strusevich, Vitaly A & Mosheiff, Jonathan, 2018. "Two-machine flow shop and open shop scheduling problems with a single maintenance window," European Journal of Operational Research, Elsevier, vol. 271(2), pages 388-400.
    4. Lee, Kangbok & Zheng, Feifeng & Pinedo, Michael L., 2019. "Online scheduling of ordered flow shops," European Journal of Operational Research, Elsevier, vol. 272(1), pages 50-60.
    5. 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.
    6. Christodoulos Floudas & Xiaoxia Lin, 2005. "Mixed Integer Linear Programming in Process Scheduling: Modeling, Algorithms, and Applications," Annals of Operations Research, Springer, vol. 139(1), pages 131-162, October.
    7. Shioura, Akiyoshi & Shakhlevich, Natalia V. & Strusevich, Vitaly A., 2018. "Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: A review of solution approaches," European Journal of Operational Research, Elsevier, vol. 266(3), pages 795-818.
    8. Peteghem, Vincent Van & Vanhoucke, Mario, 2010. "A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 201(2), pages 409-418, March.
    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. Lu, Haimin & Pei, Zhi, 2023. "Single machine scheduling with release dates: A distributionally robust approach," European Journal of Operational Research, Elsevier, vol. 308(1), pages 19-37.

    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. Ma, Ran & Guo, Sainan, 2021. "Applying “Peeling Onion” approach for competitive analysis in online scheduling with rejection," European Journal of Operational Research, Elsevier, vol. 290(1), pages 57-67.
    2. Myoung-Ju Park & Byung-Cheon Choi & Yunhong Min & Kyung Min Kim, 2020. "Two-Machine Ordered Flow Shop Scheduling with Generalized Due Dates," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 37(01), pages 1-16, January.
    3. Bowen Pang & Xiaolei Xie & Feng Ju & James Pipe, 2022. "A dynamic sequential decision-making model on MRI real-time scheduling with simulation-based optimization," Health Care Management Science, Springer, vol. 25(3), pages 426-440, September.
    4. Wendi Tian & Erik Demeulemeester, 2014. "Railway scheduling reduces the expected project makespan over roadrunner scheduling in a multi-mode project scheduling environment," Annals of Operations Research, Springer, vol. 213(1), pages 271-291, February.
    5. Jin Qian & Haiyan Han, 2022. "Improved algorithms for proportionate flow shop scheduling with due-window assignment," Annals of Operations Research, Springer, vol. 309(1), pages 249-258, February.
    6. Nima Zoraghi & Aria Shahsavar & Babak Abbasi & Vincent Peteghem, 2017. "Multi-mode resource-constrained project scheduling problem with material ordering under bonus–penalty policies," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 25(1), pages 49-79, April.
    7. Jiang, Yiwei & Wu, Mengjing & Chen, Xin & Dong, Jianming & Cheng, T.C.E. & Blazewicz, Jacek & Ji, Min, 2024. "Online early work scheduling on parallel machines," European Journal of Operational Research, Elsevier, vol. 315(3), pages 855-862.
    8. Baruch Mor & Gur Mosheiov & Dvir Shabtay, 2021. "Minimizing the total tardiness and job rejection cost in a proportionate flow shop with generalized due dates," Journal of Scheduling, Springer, vol. 24(6), pages 553-567, December.
    9. Luis F. Machado-Domínguez & Carlos D. Paternina-Arboleda & Jorge I. Vélez & Agustin Barrios-Sarmiento, 2021. "A memetic algorithm to address the multi-node resource-constrained project scheduling problem," Journal of Scheduling, Springer, vol. 24(4), pages 413-429, August.
    10. Lara, Cristiana L. & Koenemann, Jochen & Nie, Yisu & de Souza, Cid C., 2023. "Scalable timing-aware network design via lagrangian decomposition," European Journal of Operational Research, Elsevier, vol. 309(1), pages 152-169.
    11. Yanina Fumero & Gabriela Corsano & Jorge Montagna, 2012. "Planning and scheduling of multistage multiproduct batch plants operating under production campaigns," Annals of Operations Research, Springer, vol. 199(1), pages 249-268, October.
    12. Moukrim, Aziz & Quilliot, Alain & Toussaint, Hélène, 2015. "An effective branch-and-price algorithm for the Preemptive Resource Constrained Project Scheduling Problem based on minimal Interval Order Enumeration," European Journal of Operational Research, Elsevier, vol. 244(2), pages 360-368.
    13. Kramer, Arthur & Dell’Amico, Mauro & Iori, Manuel, 2019. "Enhanced arc-flow formulations to minimize weighted completion time on identical parallel machines," European Journal of Operational Research, Elsevier, vol. 275(1), pages 67-79.
    14. Alireza Etminaniesfahani & Hanyu Gu & Leila Moslemi Naeni & Amir Salehipour, 2024. "An efficient relax-and-solve method for the multi-mode resource constrained project scheduling problem," Annals of Operations Research, Springer, vol. 338(1), pages 41-68, July.
    15. Farahmand, H. & Doorman, G.L., 2012. "Balancing market integration in the Northern European continent," Applied Energy, Elsevier, vol. 96(C), pages 316-326.
    16. Abdelrahman Hosny & Sherief Reda, 2024. "Automatic MILP solver configuration by learning problem similarities," Annals of Operations Research, Springer, vol. 339(1), pages 909-936, August.
    17. Dayal Madhukar & Verma, Sanjay, 2014. "Breadth-first and Best-first Exact Procedures for Regular Measures of the Multi-mode RCPSP," IIMA Working Papers WP2014-10-04, Indian Institute of Management Ahmedabad, Research and Publication Department.
    18. Stefansson, Hlynur & Sigmarsdottir, Sigrun & Jensson, Pall & Shah, Nilay, 2011. "Discrete and continuous time representations and mathematical models for large production scheduling problems: A case study from the pharmaceutical industry," European Journal of Operational Research, Elsevier, vol. 215(2), pages 383-392, December.
    19. Moo-Sung Sohn & Jiwoong Choi & Hoseog Kang & In-Chan Choi, 2017. "Multiobjective Production Planning at LG Display," Interfaces, INFORMS, vol. 47(4), pages 279-291, August.
    20. 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.

    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:278:y:2019:i:2:p:563-577. 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.