SavedAdd your journal

Journals / Avrupa Bilim ve Teknoloji Dergisi / 2026 / Sayı: 23

A Hybrid Benders Decomposition Algorithm and New Models for the Distributed Permutation Flowshop Scheduling Problem

Dağıtılmış Permütasyon Akış Tipi Atölye Çizelgeleme Problemi için Hibrit Benders Ayrıştırma Algoritması ve Yeni Modeller

Hanifi İşgüder(DOKUZ EYLUL UNIVERSITY)0000-0002-5188-856X
Alper Hamzadayı(VAN YÜZÜNCÜ YIL ÜNİVERSİTESİ)0000-0003-4035-2775
Pages
126–148
Publication Date
2021-04-30
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

In this paper, 4 new best solutions are identified for the DPFSP.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:The distributed permutation flowshop scheduling problem (DPFSP) is a generalization of the regular flowshop scheduling problem where several factories are accessible for processing the jobs.
📊
Key Findings & Data:Nine newly developed exact methods are compared in detail with each other, the best mathematical models given by Naderi and Ruiz (2010) and an automatic Benders decomposition algorithm by using the 84 problem instances available in the literature.
💡
Conclusion & Impact:In this paper, 4 new best solutions are identified for the DPFSP.
🔬Design:Modeling & Simulation
📍Scope:2010 Verileri
⚙️Variables:Dağıtılmış akış tipi problem · Karışık tamsayı doğrusal programlama · Benders ayrıştırma algoritması

Abstract

The distributed permutation flowshop scheduling problem (DPFSP) is a generalization of the regular flowshop scheduling problem where several factories are accessible for processing the jobs. In this paper, two new mathematical models are developed by deriving inspiration from the formulations developed for the multiple-traveling salesman problem (mTSP), and six different pure Benders decomposition algorithms are developed based on different mathematical model formulations. In addition, a hybrid Benders decomposition algorithm is developed through the best performed mathematical. Nine newly developed exact methods are compared in detail with each other, the best mathematical models given by Naderi and Ruiz (2010) and an automatic Benders decomposition algorithm by using the 84 problem instances available in the literature. The consequences of the experiment performed for the comparison of all existing and new exact algorithms have revealed that the proposed hybrid Benders decomposition algorithm has outperformed considerably when compared to the other methods. In this paper, 4 new best solutions are identified for the DPFSP.

Özet

Dağıtılmış permütasyon akış tipi çizelgeleme problemi (DPATÇP), işleri işlemek için birkaç fabrikanın mevcut olduğu akış tipi çizelgeleme probleminin bir genellemesidir. Bu çalışmada, çoklu gezgin satıcı problemi (ÇGSP) için geliştirilen modellerden esinlenilerek iki yeni matematiksel model ve farklı matematiksel modellere dayalı olarak altı farklı saf Benders ayrıştırma algoritmaları geliştirilmiştir. Ayrıca, en iyi performansı sağlayan matematiksel model aracılığıyla hibrit bir Benders ayrıştırma algoritması geliştirilmiştir. Yeni geliştirilen dokuz kesin çözüm yöntemi, Naderi ve Ruiz (2010) tarafından önerilen en iyi matematiksel modeller ve otomatik Benders ayrıştırma algoritması ile literatürde mevcut olan 84 problem seti kullanılarak karşılaştırılmıştır. Tüm mevcut ve yeni kesin çözüm algoritmaların karşılaştırılması için gerçekleştirilen deneyin sonuçları, önerilen hibrit Benders ayrıştırma algoritmasının diğer yöntemlere kıyasla önemli ölçüde daha iyi performans gösterdiğini ortaya koymuştur. Bu makalede, DPATÇP için 4 yeni en iyi çözüm saptanmıştır.

🔖

Cite This Article

İşgüder, H., Hamzadayı, A. (2021). A Hybrid Benders Decomposition Algorithm and New Models for the Distributed Permutation Flowshop Scheduling Problem. Avrupa Bilim ve Teknoloji Dergisi, Sayı: 23, 126–148. https://doi.org/10.31590/ejosat.814129

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (35)

  1. Naderi, B., Ruiz, R.: The distributed permutation flowshop scheduling problem, Comput. Oper. Res. (2010). https://doi.org/10.1016/j.cor.2009.06.019
  2. Johnson, S.M.: Optimal two- and three-stage production schedules with setup times included, Naval Res. Logistics Quarterly (1954). https://doi.org/10.1002/nav.3800010110
  3. Framinan, J.M., Leisten, R., Ruiz, R.: Manufacturing Scheduling Systems: An Integrated View on Models, Methods and Tools. Springer, New York (2014)
  4. McKay, K.N.,Pinedo, M., Webster, S.: Practice-focused research issues for scheduling systems, Prod. Oper. Manage. (2002). https://doi.org/10.1111/j.1937-5956.2002.tb00494.x
  5. Pinedo, M.: Scheduling: Theory, Algorithms and Systems. Springer, New York (2016)
  6. Fernandez-Viagas, V., Ruiz, E., Framinan, J.M.: A new vision of approximate methods for the permutation flowshop to minimise makespan: state-of-the-art and computational evaluation, Eur. J. Oper. Res. (2017). https://doi.org/10.1016/j.ejor.2016.09.055
  7. Framinan, J.M., Gupta, J.N.D., Leisten, R.: A review and classification of heuristics for permutation flow-shop scheduling with makespan objective, J. Oper. Res. Soc. (2004). https://doi.org/10.1057/palgrave.jors.2601784
  8. Gupta, J.N.D., Stafford Jr, E. F.: Flowshop scheduling research after five decades, Eur. J. Oper. Res. (2006). https://doi.org/10.1016/j.ejor.2005.02.001
  9. Hejazi, S.R., Saghafian, S.: Flowshop-scheduling problems with makespan criterion: a review, Int. J. Prod. Res. (2005). https://doi.org/10.1080/0020754050056417
  10. Reisman, A., Kumar, A., Motwani, J.: Flowshop scheduling/sequencing research: a statistical review of the literature 1952-1994. IEEE Trans. Eng. Manage. 44, 316–329 (1997)
  11. Ruiz, R., Maroto, C.: A comprehensive review and evaluation of permutation flowshop heuristics, Eur. J. Oper. Res. (2005). https://doi.org/10.1016/j.ejor.2004.04.017
  12. Garey, M.R., Johnson, D.S., Sethi, R.: The complexity of flowshop and jobshop scheduling, Math. Oper. Res. (1976). https://doi.org/10.1287/moor.1.2.117
  13. Chan, F.T.S., Chung, S.H., Chan, L.Y., Finke, G., Tiwari, M.K.: Solving distributed FMS scheduling problems subject to maintenance: genetic algorithms approach, Robotics and Comput. Integrated Manufac. (2006). https://doi.org/10.1016/j.rcim.2005.11.005
  14. Deng, J., Wang, L.: A competitive memetic algorithm for multi-objective distributed permutation flow shop scheduling problem, Swarm and Evolutionary Comput. (2017). https://doi.org/10.1016/j.swevo.2016.06.002
  15. Jia, H.Z., Fuh, J.Y.H., Nee, A.Y.C., Zhang, Y.F.: Integration of genetic algorithm and Gantt chart for job shop scheduling in distributed manufacturing systems, Comput. Indust. Eng. (2007). https://doi.org/10.1016/j.cie.2007.06.024
  16. Giovanni, L.D., Pezzella, F.: An improved genetic algorithm for the distributed and flexible job-shop scheduling problem, Eur. J. Oper. Res. (2010). https://doi.org/10.1016/j.ejor.2009.01.008
  17. Ying, K.C., Lin, S.W., Cheng, C.Y., He, C.D.: Iterated reference greedy algorithm for solving distributed no-idle permutation flowshop scheduling problems, Comput. Indust. Eng. (2017). https://doi.org/10.1016/j.cie.2017.06.025
  18. Nawaz, M., Enscore, E.E., Ham, J.I.: A heuristic algorithm for the m -machine, n -job flow-shop sequencing problem, Omega (1983). https://doi.org/10.1016/0305-0483(83)90088-9
  19. Liu, H., Gao, L.: A Discrete Electromagnetism-like Mechanism Algorithm for Solving Distributed Permutation Flowshop Scheduling Problem. International Conference on Manufacturing Automation https://ieeexplore.ieee.org/document/5695172 (2010)
  20. Gao, J., Chen, R.: A hybrid genetic algorithm for the distributed permutation flowshop scheduling problem, Int. J. Comput. Intel. Syst. 4, 497–508 (2011a)
  21. Gao, J., Chen, R.: An NEH-based Heuristic Algorithm for Distributed Permutation Flowshop Scheduling Problems, Sci. Res. and Essays 6, 3094–3100 (2011b)
  22. Gao, J., Chen, R., Deng, W., Liu, Y.: Solving multi-factory flowshop problems with a novel variable neighbourhood descent algorithm. J. Comput. Inf. Syst. 8, 2025–2032 (2012)
  23. Gao, J., Chen, R., Deng, W.: An efficient tabu search algorithm for the distributed permutation flowshop scheduling problem, Int. J. Prod. Res. (2013). https://doi.org/10.1080/00207543.2011.644819
  24. Lin, S.W., Ying, K.C., Huang, C.Y.: Minimising makespan in distributed permutation flowshops using a modified iterated greedy algorithm, Int. J. Prod. Res. (2013). https://doi.org/10.1080/00207543.2013.790571
  25. Wang, S.Y., Wang, L., Liu, M., Xu, Y.: An effective estimation of distribution algorithm for solving the distributed permutation flow-shop scheduling problem, Int. J. Prod. Eco. (2013). https://doi.org/10.1016/j.ijpe.2013.05.004
  26. Naderi, B., Ruiz, R.: A scatter search algorithm for the distributed permutation flowshop scheduling problem, Eur. J. Oper. Res. (2014). https://doi.org/10.1016/j.ejor.2014.05.024
  27. Xu, Y., Wang, L., Wang, S., Liu, M.: An effective hybrid immune algorithm for solving the distributed permutation flow-shop scheduling problem, Eng. Optimization (2014). https://doi.org/10.1080/0305215X.2013.827673
  28. Fernandez-Viagas, V., Framinan, J.M.: A bounded-search iterated greedy algorithm for the distributed permutation flowshop scheduling problem, Int. J. of Prod. Res. (2015). https://doi.org/10.1080/00207543.2014.948578
  29. Ruiz, R., Pan, Q.K., Naderi, B.: Iterated Greedy methods for the distributed permutation flowshop scheduling problem, Omega (2019). https://doi.org/10.1016/j.omega.2018.03.004
  30. Bektas, T.: The multiple traveling salesman problem: an overview of formulations and solution procedures, Omega (2006). https://doi.org/10.1016/j.omega.2004.10.004
  31. Benders, J.F.: Partitioning procedures for solving mixed-variables programming problems, Numerische Math. 4, 238–252 (1962)
  32. Sherali, H.D., Fraticelli, B.M.P.: A modification of Benders’ decomposition algorithm for discrete subproblems: An approach for stochastic programs with integer recourse, J. Global Optimization. 22, 319–342 (2002)
  33. Costa, A.M., Cordeau, J. F., Gendron, B., Laporte, G.: Accelerating Benders decomposition with heuristic master problem solutions, Pesquisa Operacional (2012). http://dx.doi.org/10.1590/S0101-74382012005000005
  34. Rahmaniani, R., Crainic, T.G., Gendreau, M., Rei, W.: The Benders decomposition algorithm: A literature review, Eur. J. Oper. Res. (2017). https://doi.org/10.1016/j.ejor.2016.12.005
  35. Onwubolu, G., Davendra, D.: Scheduling flow shops using differential evolution algorithm, Eur. J. Oper. Res. (2006) https://doi.org/10.1016/j.ejor.2004.08.043