IDEAS home Printed from https://ideas.repec.org/a/spr/jsched/v23y2020i4d10.1007_s10951-020-00637-8.html
   My bibliography  Save this article

Benders decomposition for the mixed no-idle permutation flowshop scheduling problem

Author

Listed:
  • Tolga Bektaş

    (University of Liverpool)

  • Alper Hamzadayı

    (Van Yuzuncu Yil University)

  • Rubén Ruiz

    (Universitat Politècnica de València)

Abstract

The mixed no-idle flowshop scheduling problem arises in modern industries including integrated circuits, ceramic frit and steel production, among others, and where some machines are not allowed to remain idle between jobs. This paper describes an exact algorithm that uses Benders decomposition with a simple yet effective enhancement mechanism that entails the generation of additional cuts by using a referenced local search to help speed up convergence. Using only a single additional optimality cut at each iteration, and combined with combinatorial cuts, the algorithm can optimally solve instances with up to 500 jobs and 15 machines that are otherwise not within the reach of off-the-shelf optimization software, and can easily surpass ad-hoc existing metaheuristics. To the best of the authors’ knowledge, the algorithm described here is the only exact method for solving the mixed no-idle permutation flowshop scheduling problem.

Suggested Citation

  • Tolga Bektaş & Alper Hamzadayı & Rubén Ruiz, 2020. "Benders decomposition for the mixed no-idle permutation flowshop scheduling problem," Journal of Scheduling, Springer, vol. 23(4), pages 513-523, August.
    • Handle: RePEc:spr:jsched:v:23:y:2020:i:4:d:10.1007_s10951-020-00637-8
    DOI: 10.1007/s10951-020-00637-8
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10951-020-00637-8
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10951-020-00637-8?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. Jean-François Cordeau & Federico Pasin & Marius Solomon, 2006. "An integrated model for logistics network design," Annals of Operations Research, Springer, vol. 144(1), pages 59-82, April.
    2. Ruiz, Ruben & Maroto, Concepcion, 2005. "A comprehensive review and evaluation of permutation flowshop heuristics," European Journal of Operational Research, Elsevier, vol. 165(2), pages 479-494, September.
    3. Georgios Saharidis & Marianthi Ierapetritou, 2013. "Speed-up Benders decomposition using maximum density cut (MDC) generation," Annals of Operations Research, Springer, vol. 210(1), pages 101-123, November.
    4. Quan-Ke Pan & Ling Wang, 2008. "A novel differential evolution algorithm for no-idle permutation flow-shop scheduling problems," European Journal of Industrial Engineering, Inderscience Enterprises Ltd, vol. 2(3), pages 279-297.
    5. Goncharov, Yaroslav & Sevastyanov, Sergey, 2009. "The flow shop problem with no-idle constraints: A review and approximation," European Journal of Operational Research, Elsevier, vol. 196(2), pages 450-456, July.
    6. T. L. Magnanti & R. T. Wong, 1981. "Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria," Operations Research, INFORMS, vol. 29(3), pages 464-484, June.
    7. I. Adiri & D. Pohoryles, 1982. "Flowshop/no‐idle or no‐wait scheduling to minimize the sum of completion times," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 29(3), pages 495-504, September.
    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. Chen-Yang Cheng & Shih-Wei Lin & Pourya Pourhejazy & Kuo-Ching Ying & Yu-Zhe Lin, 2021. "No-Idle Flowshop Scheduling for Energy-Efficient Production: An Improved Optimization Framework," Mathematics, MDPI, vol. 9(12), pages 1-18, 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. 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.
    2. M. Jenabi & S. Fatemi Ghomi & S. Torabi & S. Hosseinian, 2015. "Acceleration strategies of Benders decomposition for the security constraints power system expansion planning," Annals of Operations Research, Springer, vol. 235(1), pages 337-369, December.
    3. Azad, Nader & Hassini, Elkafi, 2019. "Recovery strategies from major supply disruptions in single and multiple sourcing networks," European Journal of Operational Research, Elsevier, vol. 275(2), pages 481-501.
    4. Ragheb Rahmaniani & Shabbir Ahmed & Teodor Gabriel Crainic & Michel Gendreau & Walter Rei, 2020. "The Benders Dual Decomposition Method," Operations Research, INFORMS, vol. 68(3), pages 878-895, May.
    5. Georgios Saharidis & Marianthi Ierapetritou, 2013. "Speed-up Benders decomposition using maximum density cut (MDC) generation," Annals of Operations Research, Springer, vol. 210(1), pages 101-123, November.
    6. Camilo Ortiz-Astorquiza & Ivan Contreras & Gilbert Laporte, 2019. "An Exact Algorithm for Multilevel Uncapacitated Facility Location," Transportation Science, INFORMS, vol. 53(4), pages 1085-1106, July.
    7. Fausto Errico & Teodor Gabriel Crainic & Federico Malucelli & Maddalena Nonato, 2017. "A Benders Decomposition Approach for the Symmetric TSP with Generalized Latency Arising in the Design of Semiflexible Transit Systems," Transportation Science, INFORMS, vol. 51(2), pages 706-722, May.
    8. Belieres, Simon & Hewitt, Mike & Jozefowiez, Nicolas & Semet, Frédéric & Van Woensel, Tom, 2020. "A Benders decomposition-based approach for logistics service network design," European Journal of Operational Research, Elsevier, vol. 286(2), pages 523-537.
    9. Lixin Tang & Wei Jiang & Georgios Saharidis, 2013. "An improved Benders decomposition algorithm for the logistics facility location problem with capacity expansions," Annals of Operations Research, Springer, vol. 210(1), pages 165-190, November.
    10. Zewen Sun & Xingsheng Gu, 2017. "Hybrid Algorithm Based on an Estimation of Distribution Algorithm and Cuckoo Search for the No Idle Permutation Flow Shop Scheduling Problem with the Total Tardiness Criterion Minimization," Sustainability, MDPI, vol. 9(6), pages 1-16, June.
    11. Pan, Quan-Ke & Ruiz, Rubén, 2014. "An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem," Omega, Elsevier, vol. 44(C), pages 41-50.
    12. Nader Azad & Georgios Saharidis & Hamid Davoudpour & Hooman Malekly & Seyed Yektamaram, 2013. "Strategies for protecting supply chain networks against facility and transportation disruptions: an improved Benders decomposition approach," Annals of Operations Research, Springer, vol. 210(1), pages 125-163, November.
    13. J.-C. Billaut & F. Della Croce & F. Salassa & V. T’kindt, 2019. "No-idle, no-wait: when shop scheduling meets dominoes, Eulerian paths and Hamiltonian paths," Journal of Scheduling, Springer, vol. 22(1), pages 59-68, February.
    14. N. Beheshti Asl & S. A. MirHassani, 2019. "Accelerating benders decomposition: multiple cuts via multiple solutions," Journal of Combinatorial Optimization, Springer, vol. 37(3), pages 806-826, April.
    15. Pan, Quan-Ke & Ruiz, Rubén, 2012. "An estimation of distribution algorithm for lot-streaming flow shop problems with setup times," Omega, Elsevier, vol. 40(2), pages 166-180, April.
    16. Vallada, Eva & Ruiz, Rubén, 2010. "Genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem," Omega, Elsevier, vol. 38(1-2), pages 57-67, February.
    17. S. S. Panwalkar & Christos Koulamas, 2019. "The evolution of schematic representations of flow shop scheduling problems," Journal of Scheduling, Springer, vol. 22(4), pages 379-391, August.
    18. Belieres, Simon & Hewitt, Mike & Jozefowiez, Nicolas & Semet, Frédéric, 2022. "Meta partial benders decomposition for the logistics service network design problem," European Journal of Operational Research, Elsevier, vol. 300(2), pages 473-489.
    19. Walter Rei & Jean-François Cordeau & Michel Gendreau & Patrick Soriano, 2009. "Accelerating Benders Decomposition by Local Branching," INFORMS Journal on Computing, INFORMS, vol. 21(2), pages 333-345, May.
    20. Hanif Sherali & Ki-Hwan Bae & Mohamed Haouari, 2013. "A benders decomposition approach for an integrated airline schedule design and fleet assignment problem with flight retiming, schedule balance, and demand recapture," Annals of Operations Research, Springer, vol. 210(1), pages 213-244, November.

    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:spr:jsched:v:23:y:2020:i:4:d:10.1007_s10951-020-00637-8. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.