Yıl: 2023 Cilt: 38 Sayı: 3 Sayfa Aralığı: 1953 - 1966 Metin Dili: Türkçe DOI: 10.17341/gazimmfd.873295 İndeks Tarihi: 23-03-2023

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

Ö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ş $varepsilon$-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ş $varepsilon$-kısıt yöntemi ile elde edilemeyen baskın çözümlere ulaşılmıştır.
Anahtar Kelime: İ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

A matheuristic algorithm for multi-objective unrelated parallel machine scheduling problem

Öz:
Machine scheduling problems are one of the basic manufacturing problems. Thus, there are a lot of study in the literature. In most of these studies, the problem is considered as single objective. Although the single objective approach makes it easier to solve problems theoretically, it is often not possible to provide realistic solutions because almost all real-life problems have multi-objective properties. It is aimed to close this gap in the literature by using the multi-objective programming method that emerged as a powerful solution approach. The objectives are minimizing the makespan and minimizing the total tardiness. A matheuristic algorithm is developed for solving the considered problem. The performance of the algorithm is compared with the results of the augmented $varepsilon$-constraint method. With the proposed matheuristic algorithm, both a solution time advantage is obtained and dominant solutions that could not be obtained with the augmented $varepsilon$-constraint method are reached.
Anahtar Kelime: Unrelated parallel machine scheduling problem sequence dependent setup times augmented -constraint method matheuristic algorithm

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık
  • 1. 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.
  • 2. 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.
  • 3. 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.
  • 4. 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.
  • 5. 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.
  • 6. 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.
  • 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. Ezugwu A.E., Enhanced symbiotic organisms search algorithm for unrelated parallel machines manufacturing scheduling with setup times, Knowledge-Based Systems, 172, 15-32, 2019.
  • 9. 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.
  • 10. 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.
  • 11. 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.
  • 12. 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.
  • 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., 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.
  • 15. 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.
  • 16. 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.
  • 17. 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.
  • 18. 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.
  • 19. 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.
  • 20. 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.
  • 21. 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.
  • 22. 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.
  • 23. 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.
  • 24. 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.
  • 25. 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.
  • 26. 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.
  • 27. 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.
  • 28. 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.
  • 29. 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.
  • 30. 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.
  • 31. 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.
  • 32. 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.
  • 33. 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.
  • 34. 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.
  • 35. 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.
  • 36. 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.
  • 37. Jeong B., Kim S.W., Lee Y.J., An assembly scheduler for TFT LCD manufacturing, Computers & Industrial engineering, 41, 37- 58, 2001.
  • 38. Li Q., Milne R.J., A production scheduling problem with sequence dependent changeover cost, International Journal of Production Research, 52 (13), 4093-4102, 2014.
  • 39. 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.
  • 40. 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.
  • 41. 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.
  • 42. 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.
  • 43. 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.
  • 44. 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.
  • 45. 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.
  • 46. 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.
  • 47. Bozorgirad, M.A., Logendran R., Sequence dependent group scheduling problem on unrelated parallel machines, Expert Systems with Applications, 39, 9021- 9030, 2012.
  • 48. 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.
  • 49. 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.
  • 50. 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.
  • 51. 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.
  • 52. Saraç T., Tutumlu B., A bi-objective mathematical model for an unrelated parallel machine scheduling problem with job-splitting, Journal of the Faculty of Engineering and Architecture of Gazi University, 37 (4), 2293-2308, 2022.
  • 53. Saraç T., Tutumlu B., A mix integer programming model and solution approaches to determine the optimum machine number in the unrelated parallel machine scheduling problem, Journal of the Faculty of Engineering and Architecture of Gazi University, 37 (1), 329-345, 2022.
  • 54. Mavrotas G., Effective implementation of the -constraint method in Multi-Objective Mathematical Programming problems, Applied Mathematics and Computation, 213, 455–465, 2009.
  • 55. Logendran R., McDonell B., Smucker B., Scheduling unrelated parallel machines with sequence-dependent setups, Computers & Operations Research, 34 (11), 3420-3438, 2007.
  • 56. Saraç T., Sipahioglu A., Akyol Ozer E., A two-stage solution approach for plastic injection machines scheduling problem, Journal of Industrial and Management Optimization, 17 (3), 1289-1314, 2021.
APA Saraç T, Ozcelik F (2023). Çok amaçlı ilişkisiz paralel makine çizelgeleme problemi için bir matsezgisel algoritma. , 1953 - 1966. 10.17341/gazimmfd.873295
Chicago Saraç Tugba,Ozcelik Feristah Çok amaçlı ilişkisiz paralel makine çizelgeleme problemi için bir matsezgisel algoritma. (2023): 1953 - 1966. 10.17341/gazimmfd.873295
MLA Saraç Tugba,Ozcelik Feristah Çok amaçlı ilişkisiz paralel makine çizelgeleme problemi için bir matsezgisel algoritma. , 2023, ss.1953 - 1966. 10.17341/gazimmfd.873295
AMA Saraç T,Ozcelik F Çok amaçlı ilişkisiz paralel makine çizelgeleme problemi için bir matsezgisel algoritma. . 2023; 1953 - 1966. 10.17341/gazimmfd.873295
Vancouver Saraç T,Ozcelik F Çok amaçlı ilişkisiz paralel makine çizelgeleme problemi için bir matsezgisel algoritma. . 2023; 1953 - 1966. 10.17341/gazimmfd.873295
IEEE Saraç T,Ozcelik F "Çok amaçlı ilişkisiz paralel makine çizelgeleme problemi için bir matsezgisel algoritma." , ss.1953 - 1966, 2023. 10.17341/gazimmfd.873295
ISNAD Saraç, Tugba - Ozcelik, Feristah. "Çok amaçlı ilişkisiz paralel makine çizelgeleme problemi için bir matsezgisel algoritma". (2023), 1953-1966. https://doi.org/10.17341/gazimmfd.873295
APA Saraç T, Ozcelik F (2023). Çok amaçlı ilişkisiz paralel makine çizelgeleme problemi için bir matsezgisel algoritma. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 38(3), 1953 - 1966. 10.17341/gazimmfd.873295
Chicago Saraç Tugba,Ozcelik Feristah Çok amaçlı ilişkisiz paralel makine çizelgeleme problemi için bir matsezgisel algoritma. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 38, no.3 (2023): 1953 - 1966. 10.17341/gazimmfd.873295
MLA Saraç Tugba,Ozcelik Feristah Çok amaçlı ilişkisiz paralel makine çizelgeleme problemi için bir matsezgisel algoritma. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, vol.38, no.3, 2023, ss.1953 - 1966. 10.17341/gazimmfd.873295
AMA Saraç T,Ozcelik F Çok amaçlı ilişkisiz paralel makine çizelgeleme problemi için bir matsezgisel algoritma. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2023; 38(3): 1953 - 1966. 10.17341/gazimmfd.873295
Vancouver Saraç T,Ozcelik F Çok amaçlı ilişkisiz paralel makine çizelgeleme problemi için bir matsezgisel algoritma. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2023; 38(3): 1953 - 1966. 10.17341/gazimmfd.873295
IEEE Saraç T,Ozcelik F "Çok amaçlı ilişkisiz paralel makine çizelgeleme problemi için bir matsezgisel algoritma." Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 38, ss.1953 - 1966, 2023. 10.17341/gazimmfd.873295
ISNAD Saraç, Tugba - Ozcelik, Feristah. "Çok amaçlı ilişkisiz paralel makine çizelgeleme problemi için bir matsezgisel algoritma". Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 38/3 (2023), 1953-1966. https://doi.org/10.17341/gazimmfd.873295