Çok amaçlı ilişkisiz paralel makine çizelgeleme problemi için bir matsezgisel algoritma

Yıl 2023, Cilt: 38 Sayı: 3, 1953 - 1966, 06.01.2023

Tuğba Saraç , Feriştah Özçelik

https://doi.org/10.17341/gazimmfd.873295

Cited By: 1

Öz

Makine çizelgeleme problemleri temel üretim problemlerinden birisidir. Bu nedenle literatürde çok sayıda çalışma mevcuttur. Bu çalışmaların önemli bir bölümünde problemin tek amaçlı olarak ele alındığı görülmektedir. Tek amaçlı yaklaşım teorik anlamda problemlerin daha kolay çözülebilmesini sağlasa da gerçek hayat problemlerinin hemen hepsinin çok amaçlı özellik göstermesinden dolayı çoğu zaman gerçekçi çözümler sunamamaktadır. Bu çalışmada, ilişkisiz paralel makine çizelgeleme problemi çok amaçlı olarak ele alınmıştır. Amaçlar son işin tamamlanma zamanının ve toplam gecikmenin enküçüklenmesidir. Ele alınan problemin çözümü için bir matsezgisel algoritma geliştirilmiştir. Geliştirilen algoritma ile elde edilen sonuçlar, genişletilmiş -kısıt yönteminin sonuçları ile karşılaştırılmıştır. Önerilen matsezgisel algoritma ile hem ciddi bir çözüm süresi avantajı elde edilmiş hem de genişletilmiş -kısıt yöntemi ile elde edilemeyen baskın çözümlere ulaşılmıştır.

Anahtar Kelimeler

İlişkisiz paralel makine çizelgeleme problemi, Sıra bağımlı hazırlık süreleri, Genişletilmiş E-kısıt yöntemi, Matsezgisel algoritma

Kaynakça

• [1] Abreu L.R., Prata B.A., A Hybrid Genetic Algorithm for solving the Unrelated Parallel Machine Scheduling problem with Sequence Dependent Setup Times, IEEE Latin America Transactions, 16 (6), 1715-1722, 2018.
• [2] Afzalirad M., Rezaeian J., Resource constrained unrelated parallel machine scheduling problem with sequence dependent setup times, precedence constraints and machine eligibility restrictions, Computers & Industrial Engineering, 98, 40- 52, 2016.
• [3] Arnaout J.P., A worm optimization algorithm to minimize the makespan on unrelated parallel machines with sequence-dependent setup times, Annals of Operations Research, 285 (1-2), 273-293, 2020.
• [4] Arnout J. P., Rabadi G., Musa R., Two stage ant colony optimization algorithm to minimize the makespan on unrelated parallel machines- part II: enhancements and experimentations, Journal of Intelligent Manufacturing, 25, 43-53, 2014.
• [5] Arnout J. P., Rabadi G., Musa R., A two stage ant colony optimization algorithm to minimize the makespan on unrelated parallel machines with sequence dependent setup times, Journal of Intelligent Manufacturing, 21, 693- 701, 2010.
• [6] Bektur G., Sarac T., A mathematical model and heuristic algorithms for an unrelated parallel machine scheduling problem with sequence-dependent setup times, machine eligibility restrictions and a common server, Computers & Operations Research, 103, 46-63, 2019.
• [7] Chang P. C., Chen S. H., Integrating dominance properties with genetic algorithms for parallel machine scheduling problems with setup times, Applied soft computing, 11, 1263- 1274, 2011.
• [8] Chen C. L., Iterated hybrid metaheuristic algorithms for unrelated parallel machines problem with unequal ready times and sequence dependent setup times, International Journal of Advanced Manufacturing Technology, 60, 693-705, 2012.
• [9] Coelho I.M., Haddad M.N., Ochi L.S., Farias R., Souza M.J.F., A hybrid CPU- GPU local search heuristic for the unrelated parallel machine scheduling problem, 2012 Third Workshop on Applications for Multi-Core Architecture, IEEE, 19- 23, 2012.
• [10] Diana R.O.M., Filho M.F., Souza S. R., Victor J. F., An immune- inspired algorithm for an unrelated parallel machines’ scheduling problem with sequence and machine dependent setup-times for makespan minimisation, Neurocomputing, 163, 94-105, 2015.
• [11] Eroğlu D.Y., Özmutlu H.C., Özmutlu S., Genetic algorithm with local search for the unrelated parallel machine scheduling problem with sequence dependent set-up times, International journal of production research, 52(19), 5841-5856, 2014.
• [12] Ezugwu A.E., Adeleke O.J., Viriri S., Symbiotic organisms search algorithm for the unrelated parallel machines scheduling with sequence-dependent setup times, PLOS ONE 13(7) Article Number: e0200030, 2018.
• [13] Ezugwu A.E., Akutsah F., An improved firefly algorithm for the unrelated parallel machines scheduling problem with sequence-dependent setup times, IEEE Access, 6, 54459- 54478, 2018.
• [14] Ezugwu A.E., Enhanced symbiotic organisms search algorithm for unrelated parallel machines manufacturing scheduling with setup times, Knowledge-Based Systems, 172, 15-32, 2019.
• [15] Fanjul-Peyro L., Ruiz R., Perea F., Reformulations and an exact algorithm for unrelated parallel machine scheduling problems with setup times, Computers & Operations Research, 101, 173-182, 2019.
• [16] Fleszar K., Charalambous C., Hindi K. S., A variable neighbourhood descent heuristic for the problem of makespan minimization on unrelated parallel machines with setup times, Journal of Intelligent Manufacturing, 23, 1949- 1958, 2012.
• [17] Gedik R., Kalathia D., Egilmez G., et al., A constraint programming approach for solving unrelated parallel machine scheduling problem, Computers & Industrial Engineering, 121, 139-149, 2018.
• [18] Hsu C.J., Cheng T.C.E., Yang D.L., Unrelated parallel-machine scheduling with rate-modifying activities to minimize the total completion time, Information Sciences, 181, 4799- 4803, 2011.
• [19] Jeong B., Kim S.W., Lee Y.J., An asembly scheduler for TFT LCD manufacturing, Computers & Industrial engineering, 41, 37- 58, 2001.
• [20] Joo C.M., Kim B.S., Hybrid genetic algorithms with dispatching rules for unrelated machine scheduling with setup time and production availability, Computers & Industrial engineering, 85, 102- 109, 2015.
• [21] Joo C.M., Kim B.S., Genetic algorithm with an effective dispatching method for unrelated parallel machine scheduling with sequence dependent and machine dependent setup times, IE interfaces, 25(3), 357-364, 2012.
• [22] Jouhari H., Lei D., Al-qaness M.A.A. et al., Sine-Cosine Algorithm to Enhance Simulated Annealing for Unrelated Parallel Machine Scheduling with Setup Times, Mathematics, 7(11), 1120, 2019.
• [23] Lee C.H., Liao C.J., Chao C.W., Unrelated parallel machine scheduling with dedicated machines and common deadline, Computers & industrial engineering, 74, 161-168, 2014.
• [24] Lee J.H., Yu J.M., Lee, D.H., A tabu search algorithm for unrelated parallel machine scheduling with sequence and machine dependent setups: minimizing total tardiness, International Journal of Advanced Manufacturing Technology, 69, 2081-2089, 2013.
• [25] Li Q., Milne R.J., A production scheduling problem with sequence dependent changeover cost, International Journal of Production Research, 52(13), 4093-4102, 2014.
• [26] Lin S.W., Lu C.C., Ying K.C., Minimization of total tardiness on unrelated parallel machines with sequence and machine dependent setup times under due date constraints, International Journal of Advanced Manufacturing Technology, 53, 353- 361, 2011.
• [27] Lin Y.K., Hsieh F.Y., Unrelated parallel machine scheduling with setup times and ready times, International Journal of Production Research, 52(4), 1200- 1214, 2014.
• [28] Lin S.W., Ying K.C., ABC-Based manufacturing scheduling for unrelated parallel machines with machine dependent and job sequence dependent setup times, Computers & Operations Research, 51, 172- 181, 2014.
• [29] Mir m.S.S., Rezaeian J., A robust hybrid approach based on particle swarm optimization and genetic algorithm to minimize the total machine load on unrelated parallel machines, Applied Soft Computing, 41, 488- 504, 2016.
• [30] Paula M.R., Mateus, G.R., Ravetti, M.G., A non delayed relax and cut algorithm for scheduling problems with parallel machines, due dates and sequence dependent setup times, Computers & Operations Research, 37, 938- 949. 2010.
• [31] Rambod M., Rezaeian J., Robust meta- heuristic implementation for unrelated parallel machines scheduling problem with rework processes and machine eligibility restrictions, 77, 15- 28, 2014.
• [32] Rauchecker G., Schryen G., Using high performance computing for unrelated parallel machine scheduling with sequence-dependent setup times: Development and computational evaluation of a parallel branch-and-price algorithm, Computers & Operations Research, 104, 338-357, 2019.
• [33] Rosales O.A., Bello F.A., Alvarez A., Efficient metaheuristic algorithm and reformulations for the unrelated parallel machine scheduling problem with sequence and machine dependent setup times, International Journal of Advanced Manufacturing Technology, 76, 1705-1718, 2015.
• [34] Santos H.G., Toffolo T.A.M., Silva, C.L.T. F., Berghe G.V., Analysis of stochastic local search methods for the unrelated parallel machine scheduling problem, International Transactions In Operational Research, 26(2), 707-724, 2019.
• [35] Vallada E., Ruiz R., A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times, European Journal of Operational Research, 211, 612- 622, 2011.
• [36] Yepes-Borrero J.C., Villa F., Perea F., et al. GRASP algorithm for the unrelated parallel machine scheduling problem with setup times and additional resources, Expert Systems with Applications, 141, Article Number: 112959, 2020.
• [37] Ying K.C., Lee Z.J., Lin S.W., Makespan minimization for scheduling unrelated parallel machines with setup times, Journal of Intelligent Manufacturing, 23, 1795-1803, 2012.
• [38] Ying K.C., Lin S.W., Unrelated parallel machine scheduling with sequence and machine dependent setup times and due date constraints, International Journal of Innovative Computing, Information and Control, 8, (5A), 3279-3297, 2012.
• [39] Bozorgirad, M.A., Logendran R., Sequence dependent group scheduling problem on unrelated parallel machines, Expert Systems With Applications, 39, 9021- 9030, 2012.
• [40] Canıyılmaz E., Benli B., İlkay M.S., An artificial bee colony algorithm approach for unrelated parallel machine scheduling with processing set restrictions, job sequence dependent setup times and due dates, International Journal of Advanced Manufacturing Technology, 77, 2105-2115, 2015.
• [41] Dolgui A., Eremeev A.V., Kovalyov M.Y., Kuznetsou P.M., Multi-product lot sizing and scheduling on unrelated parallel machines, II E Transactions, 42, 514-524, 2010.
• [42] Ekici A., Elyasi M., Ozener O.O., et al., An application of unrelated parallel machine scheduling with sequence-dependent setups at Vestel Electronics, Computers & Operations Research, 111, 130-140, 2019.
• [43] Kayvanfar V., Teymourian E., Hybrid intelligent water drops algorithm to unrelated parallel machines scheduling problem: a just-in-time approach, International Journal of Production Research, 52 (19), 5857- 5879, 2014.
• [44] Mehravaran Y., Logendran R., Bicriteria supply chain scheduling on unrelated parallel machines, Journal of the Chinese Institute of Industrial Engineers, 28 (2), 91- 101, 2011.
• [45] Nogueira J.P., Arroyo, J.E.C., Villadiego H.M.M., Gonçalves, L.B., Hybrid GRASP Heuristics to Solve an Unrelated Parallel Machine Scheduling Problem with Earliness and Tardiness Penalties, Electronic notes in theoretical computer science, 302, 53-72, 2014.
• [46] Ruiz R., Andres-Romano, C., Scheduling unrelated parallel machines with resource assignable sequence-dependent setup times, International Journal of Advanced Manufacturing Technology, 57, 777- 794, 2011.
• [47] Shahvari O., Logendran R., An enhanced tabu search algorithm to minimize a bi-criteria objective in batching and scheduling problems on unrelated parallel machines with desired lower bounds on batch sizes, Computers & Operations Research, 77, 154-176, 2017.
• [48] Afzalirad M., Rezaeian J., A realistic variant of bi- objective unrelated parallel machine scheduling problem: NSGA II and MOACO approaches, Applied Soft Computing, 50, 109-123, 2017.
• [49] Chyu C.C., Chang W.S., A pareto evolutionary algorithm approach to bi-objective unrelated parallel machine scheduling problems, International Journal of Advanced Manufacturing Technology, 49, 697- 708, 2010.
• [50] Saricicek I., Multi-Objective scheduling by maximizing machine preferences for unrelated parallel machines, Sigma Journal of Engineering and Natural Sciences, 38 (1), 405-420, 2020.
• [51] Torabi S.A., Sahebjamnia N., Mansouri S.A., Bajestani M.A., A particle swarm optimization for a fuzzy multi- objective unrelated parallel machine scheduling problem, Applied Soft Computing, 13, 4750- 4762, 2013.
• [52] Wang M., Pan G., A Novel Imperialist Competitive Algorithm with Multi-Elite Individuals Guidance for Multi-Object Unrelated Parallel Machine Scheduling Problem, IEEE Access, 7, 121223-121235, 2019.
• [53] Mavrotas G., Effective implementation of the -constraint method in Multi-Objective Mathematical Programming problems, Applied Mathematics and Computation, 213, 455–465, 2009.
• [54] Logendran R., McDonell B., Smucker B., Scheduling unrelated parallel machines with sequence-dependent setups, Computers & Operations Research, 34 (11), 3420-3438, 2007.