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

A combinatorial Benders decomposition algorithm for parallel machine scheduling with working-time restrictions

Author

Listed:
  • Fang, Kan
  • Wang, Shijin
  • Pinedo, Michael L.
  • Chen, Lin
  • Chu, Feng

Abstract

This paper addresses a parallel machine scheduling problem with restrictions on employees’ working-times and break times. Tasks must be processed by employees nonpreemptively on unrelated parallel machines with different thresholds that specify for each employee the maximum total and consecutive working-time, and the minimum break time. The objective is to minimize the weighted sum of the makespan, the machine depreciation costs, and the labor costs. To solve this problem, a mixed integer linear programming model is formulated, and two different decomposition-based exact algorithms are implemented as well as a list scheduling (LS)-based heuristic method. Extensive computational experiments are performed on randomly generated instances, and the results demonstrate the efficiency of our proposed combinatorial Benders decomposition approach.

Suggested Citation

  • Fang, Kan & Wang, Shijin & Pinedo, Michael L. & Chen, Lin & Chu, Feng, 2021. "A combinatorial Benders decomposition algorithm for parallel machine scheduling with working-time restrictions," European Journal of Operational Research, Elsevier, vol. 291(1), pages 128-146.
    • Handle: RePEc:eee:ejores:v:291:y:2021:i:1:p:128-146
    DOI: 10.1016/j.ejor.2020.09.037
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221720308419
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2020.09.037?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. Matteo Fischetti & Silvano Martello & Paolo Toth, 1989. "The Fixed Job Schedule Problem with Working-Time Constraints," Operations Research, INFORMS, vol. 37(3), pages 395-403, June.
    2. Ethel Mokotoff & José Jimeno & Ana Gutiérrez, 2001. "List scheduling algorithms to minimize the makespan on identical parallel machines," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 9(2), pages 243-269, December.
    3. Saddoune, Mohammed & Desaulniers, Guy & Elhallaoui, Issmail & Soumis, François, 2011. "Integrated airline crew scheduling: A bi-dynamic constraint aggregation method using neighborhoods," European Journal of Operational Research, Elsevier, vol. 212(3), pages 445-454, August.
    4. Benavides, Alexander J. & Ritt, Marcus & Miralles, Cristóbal, 2014. "Flow shop scheduling with heterogeneous workers," European Journal of Operational Research, Elsevier, vol. 237(2), pages 713-720.
    5. De Bruecker, Philippe & Van den Bergh, Jorne & Beliën, Jeroen & Demeulemeester, Erik, 2015. "Workforce planning incorporating skills: State of the art," European Journal of Operational Research, Elsevier, vol. 243(1), pages 1-16.
    6. Ernst, A. T. & Jiang, H. & Krishnamoorthy, M. & Sier, D., 2004. "Staff scheduling and rostering: A review of applications, methods and models," European Journal of Operational Research, Elsevier, vol. 153(1), pages 3-27, February.
    7. Olivier Guyon & Pierre Lemaire & Éric Pinson & David Rivreau, 2014. "Solving an integrated job-shop problem with human resource constraints," Annals of Operations Research, Springer, vol. 213(1), pages 147-171, February.
    8. Asvin Goel, 2009. "Vehicle Scheduling and Routing with Drivers' Working Hours," Transportation Science, INFORMS, vol. 43(1), pages 17-26, February.
    9. Nickolas K. Freeman & Sharif H. Melouk & John Mittenthal, 2016. "A Scenario-Based Approach for Operating Theater Scheduling Under Uncertainty," Manufacturing & Service Operations Management, INFORMS, vol. 18(2), pages 245-261, May.
    10. Brucker, Peter & Qu, Rong & Burke, Edmund, 2011. "Personnel scheduling: Models and complexity," European Journal of Operational Research, Elsevier, vol. 210(3), pages 467-473, May.
    11. Gianni Codato & Matteo Fischetti, 2006. "Combinatorial Benders' Cuts for Mixed-Integer Linear Programming," Operations Research, INFORMS, vol. 54(4), pages 756-766, August.
    12. Hans Kellerer & Vitaly A. Strusevich, 2008. "Scheduling parallel dedicated machines with the speeding‐up resource," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(5), pages 377-389, August.
    13. Allahverdi, Ali, 2016. "A survey of scheduling problems with no-wait in process," European Journal of Operational Research, Elsevier, vol. 255(3), pages 665-686.
    14. Kellerer, H. & Strusevich, V. A., 2003. "Scheduling parallel dedicated machines under a single non-shared resource," European Journal of Operational Research, Elsevier, vol. 147(2), pages 345-364, June.
    15. Lushchakova, Irina N. & Strusevich, Vitaly A., 2010. "Scheduling incompatible tasks on two machines," European Journal of Operational Research, Elsevier, vol. 200(2), pages 334-346, January.
    16. Dolgui, Alexandre & Kovalev, Sergey & Kovalyov, Mikhail Y. & Malyutin, Sergey & Soukhal, Ameur, 2018. "Optimal workforce assignment to operations of a paced assembly line," European Journal of Operational Research, Elsevier, vol. 264(1), pages 200-211.
    17. Van den Bergh, Jorne & Beliën, Jeroen & De Bruecker, Philippe & Demeulemeester, Erik & De Boeck, Liesje, 2013. "Personnel scheduling: A literature review," European Journal of Operational Research, Elsevier, vol. 226(3), pages 367-385.
    18. Chen, Jiang Hang & Lee, Der-Horng & Cao, Jin Xin, 2012. "A combinatorial benders’ cuts algorithm for the quayside operation problem at container terminals," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 266-275.
    19. J. N. Hooker, 2007. "Planning and Scheduling by Logic-Based Benders Decomposition," Operations Research, INFORMS, vol. 55(3), pages 588-602, June.
    20. Braekers, Kris & Hartl, Richard F. & Parragh, Sophie N. & Tricoire, Fabien, 2016. "A bi-objective home care scheduling problem: Analyzing the trade-off between costs and client inconvenience," European Journal of Operational Research, Elsevier, vol. 248(2), pages 428-443.
    21. Edis, Emrah B. & Oguz, Ceyda & Ozkarahan, Irem, 2013. "Parallel machine scheduling with additional resources: Notation, classification, models and solution methods," European Journal of Operational Research, Elsevier, vol. 230(3), pages 449-463.
    22. Rodrigues, Maikol M. & de Souza, Cid C. & Moura, Arnaldo V., 2006. "Vehicle and crew scheduling for urban bus lines," European Journal of Operational Research, Elsevier, vol. 170(3), pages 844-862, May.
    23. Akpinar, Sener & Elmi, Atabak & Bektaş, Tolga, 2017. "Combinatorial Benders cuts for assembly line balancing problems with setups," European Journal of Operational Research, Elsevier, vol. 259(2), pages 527-537.
    24. Canto, Salvador Perez, 2008. "Application of Benders' decomposition to power plant preventive maintenance scheduling," European Journal of Operational Research, Elsevier, vol. 184(2), pages 759-777, January.
    25. Guyon, O. & Lemaire, P. & Pinson, É. & Rivreau, D., 2010. "Cut generation for an integrated employee timetabling and production scheduling problem," European Journal of Operational Research, Elsevier, vol. 201(2), pages 557-567, March.
    26. Valls, Vicente & Pérez, Ángeles & Quintanilla, Sacramento, 2009. "Skilled workforce scheduling in Service Centres," European Journal of Operational Research, Elsevier, vol. 193(3), pages 791-804, March.
    27. Huq, Faizul & Cutright, Kenneth & Martin, Clarence, 2004. "Employee scheduling and makespan minimization in a flow shop with multi-processor work stations: a case study," Omega, Elsevier, vol. 32(2), pages 121-129, April.
    28. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    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. Miloš Milenković & Susana Val & Nebojša Bojović, 2023. "Simultaneous lot sizing and scheduling in the animal feed premix industry," Operational Research, Springer, vol. 23(2), pages 1-40, June.
    2. Heiko Diefenbach & Simon Emde & Christoph H. Glock & Eric H. Grosse, 2022. "New solution procedures for the order picker routing problem in U-shaped pick areas with a movable depot," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(2), pages 535-573, June.

    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. Volland, Jonas & Fügener, Andreas & Brunner, Jens O., 2017. "A column generation approach for the integrated shift and task scheduling problem of logistics assistants in hospitals," European Journal of Operational Research, Elsevier, vol. 260(1), pages 316-334.
    2. Zhang, Zizhen & Qin, Hu & Wang, Kai & He, Huang & Liu, Tian, 2017. "Manpower allocation and vehicle routing problem in non-emergency ambulance transfer service," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 106(C), pages 45-59.
    3. De Bruecker, Philippe & Van den Bergh, Jorne & Beliën, Jeroen & Demeulemeester, Erik, 2015. "Workforce planning incorporating skills: State of the art," European Journal of Operational Research, Elsevier, vol. 243(1), pages 1-16.
    4. Giorgi Tadumadze & Simon Emde & Heiko Diefenbach, 2020. "Exact and heuristic algorithms for scheduling jobs with time windows on unrelated parallel machines," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(2), pages 461-497, June.
    5. Van den Bergh, Jorne & Beliën, Jeroen & De Bruecker, Philippe & Demeulemeester, Erik & De Boeck, Liesje, 2013. "Personnel scheduling: A literature review," European Journal of Operational Research, Elsevier, vol. 226(3), pages 367-385.
    6. Andrew Lim & Zhenzhen Zhang & Hu Qin, 2017. "Pickup and Delivery Service with Manpower Planning in Hong Kong Public Hospitals," Transportation Science, INFORMS, vol. 51(2), pages 688-705, May.
    7. Lai, David S.W. & Leung, Janny M.Y. & Dullaert, Wout & Marques, Inês, 2020. "A graph-based formulation for the shift rostering problem," European Journal of Operational Research, Elsevier, vol. 284(1), pages 285-300.
    8. Young-Chae Hong & Amy Cohn & Stephen Gorga & Edmond O’Brien & William Pozehl & Jennifer Zank, 2019. "Using Optimization Techniques and Multidisciplinary Collaboration to Solve a Challenging Real-World Residency Scheduling Problem," Interfaces, INFORMS, vol. 49(3), pages 201-212, May.
    9. Lotfi Hidri & Achraf Gazdar & Mohammed M. Mabkhot, 2020. "Optimized Procedure to Schedule Physicians in an Intensive Care Unit: A Case Study," Mathematics, MDPI, vol. 8(11), pages 1-24, November.
    10. Doi, Tsubasa & Nishi, Tatsushi & Voß, Stefan, 2018. "Two-level decomposition-based matheuristic for airline crew rostering problems with fair working time," European Journal of Operational Research, Elsevier, vol. 267(2), pages 428-438.
    11. Smirnov, Dmitry & Huchzermeier, Arnd, 2020. "Analytics for labor planning in systems with load-dependent service times," European Journal of Operational Research, Elsevier, vol. 287(2), pages 668-681.
    12. Xiang Li & Haoyue Fan & Jiaming Liu & Qifeng Xun, 2022. "Staff scheduling in blood collection problems," Annals of Operations Research, Springer, vol. 316(1), pages 365-400, September.
    13. Mancini, Simona & Ciavotta, Michele & Meloni, Carlo, 2021. "The Multiple Multidimensional Knapsack with Family-Split Penalties," European Journal of Operational Research, Elsevier, vol. 289(3), pages 987-998.
    14. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    15. Michels, Adalberto Sato & Lopes, Thiago Cantos & Magatão, Leandro, 2020. "An exact method with decomposition techniques and combinatorial Benders’ cuts for the type-2 multi-manned assembly line balancing problem," Operations Research Perspectives, Elsevier, vol. 7(C).
    16. Rodríguez, Jesús A. & Anjos, Miguel F. & Côté, Pascal & Desaulniers, Guy, 2021. "Accelerating Benders decomposition for short-term hydropower maintenance scheduling," European Journal of Operational Research, Elsevier, vol. 289(1), pages 240-253.
    17. Pieter Smet & Annelies Lejon & Greet Vanden Berghe, 2021. "Demand smoothing in shift design," Flexible Services and Manufacturing Journal, Springer, vol. 33(2), pages 457-484, June.
    18. Guo, Penghui & Zhu, Jianjun, 2023. "Capacity reservation for humanitarian relief: A logic-based Benders decomposition method with subgradient cut," European Journal of Operational Research, Elsevier, vol. 311(3), pages 942-970.
    19. Tristan Becker, 2020. "A decomposition heuristic for rotational workforce scheduling," Journal of Scheduling, Springer, vol. 23(5), pages 539-554, October.
    20. Tom Rihm & Philipp Baumann, 2018. "Staff assignment with lexicographically ordered acceptance levels," Journal of Scheduling, Springer, vol. 21(2), pages 167-189, April.

    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:291:y:2021:i:1:p:128-146. 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.