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

Öz

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.

Anahtar Kelimeler

• Dağıtılmış akış tipi problem
• Karışık tamsayı doğrusal programlama
• Benders ayrıştırma algoritması
• LS3 yerel arama prosedürü

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

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.

Keywords

• Distributed flowshop problem
• Mixed integer linear programming
• Benders decomposition algorithm
• LS3 local search procedure

References

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