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

Year 2021, Issue: 23, 126 - 148, 30.04.2021

Hanifi İşgüder , Alper Hamzadayı

https://doi.org/10.31590/ejosat.814129

Abstract

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.

Keywords

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

• Naderi, B., Ruiz, R.: The distributed permutation flowshop scheduling problem, Comput. Oper. Res. (2010). https://doi.org/10.1016/j.cor.2009.06.019
• 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
• Framinan, J.M., Leisten, R., Ruiz, R.: Manufacturing Scheduling Systems: An Integrated View on Models, Methods and Tools. Springer, New York (2014)
• 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
• Pinedo, M.: Scheduling: Theory, Algorithms and Systems. Springer, New York (2016)
• 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
• 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
• 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
• Hejazi, S.R., Saghafian, S.: Flowshop-scheduling problems with makespan criterion: a review, Int. J. Prod. Res. (2005). https://doi.org/10.1080/0020754050056417
• 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)
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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)
• Gao, J., Chen, R.: A hybrid genetic algorithm for the distributed permutation flowshop scheduling problem, Int. J. Comput. Intel. Syst. 4, 497–508 (2011a)
• Gao, J., Chen, R.: An NEH-based Heuristic Algorithm for Distributed Permutation Flowshop Scheduling Problems, Sci. Res. and Essays 6, 3094–3100 (2011b)
• 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)
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• Benders, J.F.: Partitioning procedures for solving mixed-variables programming problems, Numerische Math. 4, 238–252 (1962)
• 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)
• 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
• 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
• 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