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

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

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,

PDF

___

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