İlişkisiz paralel makine çizelgeleme probleminde eniyi makine sayısının belirlenmesi içinbir doğrusal tamsayılı matematiksel model ve çözüm yaklaşımları

Saraç, Tugba; Tutumlu, Büşra

doi:10.17341/gazimmfd.686683

İlişkisiz paralel makine çizelgeleme probleminde eniyi makine sayısının belirlenmesi içinbir doğrusal tamsayılı matematiksel model ve çözüm yaklaşımları

Tuğba SARAÇ, (Eskişehir Osmangazi Üniversitesi, Mühendislik Mimarlık Fakültesi, Endüstri Mühendisliği Bölümü, Eskişehir, Türkiye)

Büşra TUTUMLU (Kütahya Dumlupınar Üniversitesi, Mühendislik Fakültesi, Endüstri Mühendisliği Bölümü, Kütahya, Türkiye)

Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi

8 2

Yıl: 2022 Cilt: 37 Sayı: 1 Sayfa Aralığı: 329 - 345 Metin Dili: Türkçe DOI: 10.17341/gazimmfd.686683 İndeks Tarihi: 29-07-2022

İlişkisiz paralel makine çizelgeleme probleminde eniyi makine sayısının belirlenmesi içinbir doğrusal tamsayılı matematiksel model ve çözüm yaklaşımları

Öz:

Paralel makine çizelgeleme problemlerini ele alan çalışmalarda genellikle tüm makinelerin kullanılacağı varsayılmaktadır. Ancak devreye alınması sırasında çok yoğun enerji tüketilen büyük fırınların yer aldığı özel süreçlere sahip bazı işletmeler için işlerin en az sayıda fırın kullanılarak tamamlanması çok kritik olabilmektedir. Ayrıca pek çok işletme için de işlerini daha az makine ile gerçekleştirmek, üretimde kullanılmayan makinelerin başka bir işletmeye kiralanabilmesi veya boş kalan makinelerin kapasitesi kadar ek iş kabul edebilmesi fırsatlarını yaratmaktadır. Bu nedenle bu çalışmada, tüm makinelarin kullanılacağı varsayımı kaldırılmıştır, sıra ve makine bağımlı hazırlık sürelerinin ve makine uygunluklarının dikkate alındığı ilişkisiz paralel makine çizelgeleme probleminde hem hangi makinelarin kullanılacağına hem de kullanılacak makinelerde hangi işlerin hangi sırada üretileceğine karar verecek bir matematiksel model önerilmiştir. Ele alınan problemin amaçları, kullanılacak makine sayısının ve son işin tamamlanma zamanının enküçüklenmesidir. Önerilen çok amaçlı matematiksel modelin amaç fonksiyonları, ağırlıklı toplam yöntemi kullanılarak birleştirilmiştir. Matematiksel modelin çözüm performansının gösterilebilmesi için rassal türetilen test problemleri, GAMS/CPLEX ile çözülmüştür. Büyük boyutlu problemlerin çözümünde GAMS/CPLEX ile çözüm elde edilememesi nedeniyle bir yerel arama algoritması ve bir genetik algoritma önerilmiştir. Büyük boyutlu problem için tüm ağırlık çiftleri dikkate alındığında, genetik algoritma, yerel arama algoritmasından çözüm kalitesi açısından ortalama %25,64, süre açısından ise ortalama %50,31 daha başarılı olmuştur.

Anahtar Kelime: Çok Amaçlı Programlama Yerel Arama Algoritması Genetik Algoritma İlişkisiz Paralel Makine Çizelgeleme Problemi

A mix integer programming model and solution approach to determine the optimum machine number in the unrelated parallel machine scheduling problem

Öz:

It is assumed that all machines will be used in studies dealing with parallel machine scheduling problems. However, for some businesses having special processes, where large furnaces with very intense energy consumption are used during commissioning, it can be very critical to complete jobs using the least number of furnaces. In addition, for many businesses, doing their jobs with fewer machines creates opportunities for unused machines to be rented to another company or to accept additional jobs as much as the capacity of idle machines. For this reason, in this study, the assumption that all machines will be used has been removed and a mathematical model has been proposed that will decide both which machines will be used and which jobs will be produced in which order on these machines, for the unrelated parallel machine scheduling problem with sequence and machine dependent setup times and machine eligibility restriction. The objectives of the considered problem are minimizing the number of machines to be used and the completion time of the last job. The objective functions of the proposed multi-objective mathematical model are scalarized using the weighted sum method. In order to show the solution performance of the mathematical model, randomly generated test problems were solved with GAMS / CPLEX. To solve the large problems, a local search algorithm and a genetic algorithm have been proposed due to the lack of feasible solutions with GAMS / CPLEX. In the large-scale problem, when all weight pairs are taken into account, genetic algorithm is more successful than local search algorithm an average of 25.64% in terms of solution quality and 50.31% in terms of time.

Anahtar Kelime:

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık

1. Pinedo, M., Scheduling: Theory, Algorithms and Systems, Springer Science Business Media, New York, 665, 2008.
2. Akyol, E., Saraç, T., Paralel makine çizelgeleme problemi için bir karma tamsayılı programlama modeli: ortak kaynak kullanımı, Gazi Üniversitesi Fen Bilimler Dergisi, 5 (3), 109-126, 2017.
3. Pei, Z., Wan, M., Wang, Z., A new approximation algorithm for unrelated parallel machine scheduling with release dates, Annals of Operations Research, 285, 397-425, 2019.
4. Cota, L.P., Coelho, V.N., Guimaraes, F. G., Bi criteria formulation for green scheduling with unrelated parallel machines with sequence dependent setup times, International Transactions in Operational Research, 28 (2), 996-1017, 2021.
5. Kim, Y.H., Kim, R.S., Insertion of new idle time for unrelated parallel machine scheduling with job splitting and machine breakdowns, Computers & Industrial Engineering, 147, 2020.
6. Lei, D., Yuan, Y., Cai, J., An improved artificial bee colony for multi-objective distributed unrelatedparallel machine scheduling, International Journal of Production Research, 2020.
7. Sarıçiçek, İ., Multi-objective scheduling by maximizing machine preferences for unrelated parallel machines, Sigma Journal of Engineering and Natural SciencesSigma Muhendislik ve Fen Bilimleri Dergisi, 38 (1), 405-420, 2020.
8. Lei, D.M., Liu, M.Y., An artificial bee colony with division for distributed unrelated parallel machine scheduling with preventive maintenance, Computers & Industrial Engineering, 141, 2020.
9. Yepes-Borrero, J.C., Villa, F., Perea, F., GRASP Algorithm for the unrelated parallel machine scheduling problem with setup times and additional resources, Expert Systems With Applications, 141, 2020.
10. Cota, L.P., Guimaraes, F.G., Ribeiro, R.G., Meneghini, I.R., de Oliveira, F.D., Souza, M.J. F., Siarry, P., An adaptive multi-objective algorithm based on decomposition and large neighborhood search for a green machine scheduling problem, Swarm and Evolutionary Computation, 51, 2019.
11. Jouhari, H., Lei, D.M, Al-qaness, M.A.A., Abd Elaziz, M., Ewees, A.A., Farouk, O., Sine-Cosine algorithm to enhance simulated annealing for unrelated parallel machine scheduling with setup times, Mathematics, 7 (11), 2019.
12. Ekici, A., Elyasi, M., Ozener, O.O., Sarıkaya, M. B., An application of unrelated parallel machine scheduling with sequence-dependent setups at vestel electronics, Computers & Operations Research, 111, 130-140, 2019.
13. Ezugwu, A.E., Enhanced symbiotic organisms search algorithm for unrelated parallel machines manufacturing scheduling with setup times, Knowledge-Based Systems, 172, 15-32, 2019.
14. Bektur, G., Saraç, 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.
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. Ezugwu, A.E., Akutdah, F., An improved firefly algorithm for the unrelated parallel machines scheduling problem with sequence-dependent setup times, IEEE Access, 6, 54459-54478, 2018.
17. Tozzo, E., Cotrim, S.L., Galdamez, E.V.C., Leal, G.C.L., A genetic algorithm and variable neighborhood search for the unrelated parallel machine scheduling problem with sequence dependent setup time, Acta Scientiarum-Technology, 40, 2018.
18. Afzalirad, M., Rezaeian, J., A realistic variant of biobjective unrelated parallel machine scheduling problem: NSGA II and MOACO approaches, Applied Soft Computing, 50, 109-123, 2017.
19. 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.
20. 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.
21. 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.
22. 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.
23. 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.
24. 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.
25. Rosales, O.A., Bello, F.A., Alvarez, A., Efficient metaheuristic algorithm and re-formulations for the unrelated parallel machine scheduling problem with sequence and machine dependent setup times, International Journal of Advanced Manufacturing Technology, 76, 1705-1718, 2015.
26. 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.
27. 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.
28. 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.
29. 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.
30. Li, Q., Milne, R.J., A production scheduling problem with sequence dependent changeover cost, International Journal of Production Research, 52, 13, 4093-4102, 2014.
31. 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.
32. 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.
33. 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.
34. Rambod, M., Rezaeian, J., Robust meta- heuristic implementation for unrelated parallel machines scheduling problem with rework processes and machine eligibility restrictions, Computers & Industrial Engineering 77, 15-28, 2014.
35. 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.
36. 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.
37. Bozorgirad, M.A., Logendran, R., Sequence dependent group scheduling problem on unrelated parallel machines, Expert Systems with Applications, 39, 9021- 9030, 2012.
38. 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.
39. Coelho, I.M., Haddad, M.N., Ochi, L.S., Farias, R., Souza, M.J.F., A hybrid CPU- GPU local search heuristic fort he unrelated parallel machine scheduling problem, 2012 Third Workshop on Applications for Multi-Core Architecture, IEEE, 19-23, 2012.
40. 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.
41. 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.
42. Wang, I., Wang, Y. C., Chen, C.W., Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics, Flexible Services and Manufacturing Journal, 25, 343-366, 2012.
43. 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.
44. 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.
45. 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.
46. Hsu, C.J., Kuo, W.H., Yang, D.L., Unrelated parallel machine scheduling with past sequence dependent setup times and learning effects, Applied Mathematical Modelling, 35, 1492-1496, 2011.
47. Kuo, W.H., Hsu, C.J., Yang, D.L., Some unrelated parallel machine scheduling problems with past sequence dependent setup time and learning effects, Computers & Industrial Engineering, 61, 179-183, 2011.
48. 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.
49. 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.
50. Ruiz, R., Andres- Romano, C., Scheduling unrelated parallel machines with resource- assignable sequencedependent setup times, International Journal of Advanced Manufacturing Technology, 57, 777-794, 2011.
51. Vallada, E., Ruben, 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.
52. 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.
53. 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.
54. 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.
55. Paula, M.R., Mateus, G.R., Ravetti, M.G., A nondelayed relax and cut algorithm for scheduling problems with parallel machines, due dates and sequence dependent setup times, Computers & Operations Research, 37, 938-949, 2010.
56. Bektur G., Saraç T., Two parallel injection machine scheduling under crane constraint, Journal of the Faculty of Engineering and Architecture of Gazi University, 31 (4), 903-911, 2016.
57. Furugi A., A tabu search algorithm for the unrelated parallel machine scheduling problem with machine availability constraint and sequence-dependent setup time, Journal of the Faculty of Engineering and Architecture of Gazi University, 36 (3), 1539-1550, 2021.
58. Talbi, E.G., Metaheuristics from design to implementation, John Wiley and Sons, 2009.
59. Çalışkan, F., Yüksel, H., Dayık, M., Genetik algoritmaların tasarım sürecinde kullanılması, SDU Teknik Bilimler Dergisi, 6 (2), 21-27, 2016.
60. Goldberg, D.E., Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, USA, 1989.
61. Deb, K., Genetic algorithms for function optimization, Genetic Algorithms and Soft Computing, 3-19, Eds. Herrera, F. & Verdegay, J L., Physica - Verlag, Heidelberg, 1996.

APA	Saraç T, Tutumlu B (2022). İlişkisiz paralel makine çizelgeleme probleminde eniyi makine sayısının belirlenmesi içinbir doğrusal tamsayılı matematiksel model ve çözüm yaklaşımları. , 329 - 345. 10.17341/gazimmfd.686683
Chicago	Saraç Tugba,Tutumlu Büşra İlişkisiz paralel makine çizelgeleme probleminde eniyi makine sayısının belirlenmesi içinbir doğrusal tamsayılı matematiksel model ve çözüm yaklaşımları. (2022): 329 - 345. 10.17341/gazimmfd.686683
MLA	Saraç Tugba,Tutumlu Büşra İlişkisiz paralel makine çizelgeleme probleminde eniyi makine sayısının belirlenmesi içinbir doğrusal tamsayılı matematiksel model ve çözüm yaklaşımları. , 2022, ss.329 - 345. 10.17341/gazimmfd.686683
AMA	Saraç T,Tutumlu B İlişkisiz paralel makine çizelgeleme probleminde eniyi makine sayısının belirlenmesi içinbir doğrusal tamsayılı matematiksel model ve çözüm yaklaşımları. . 2022; 329 - 345. 10.17341/gazimmfd.686683
Vancouver	Saraç T,Tutumlu B İlişkisiz paralel makine çizelgeleme probleminde eniyi makine sayısının belirlenmesi içinbir doğrusal tamsayılı matematiksel model ve çözüm yaklaşımları. . 2022; 329 - 345. 10.17341/gazimmfd.686683
IEEE	Saraç T,Tutumlu B "İlişkisiz paralel makine çizelgeleme probleminde eniyi makine sayısının belirlenmesi içinbir doğrusal tamsayılı matematiksel model ve çözüm yaklaşımları." , ss.329 - 345, 2022. 10.17341/gazimmfd.686683
ISNAD	Saraç, Tugba - Tutumlu, Büşra. "İlişkisiz paralel makine çizelgeleme probleminde eniyi makine sayısının belirlenmesi içinbir doğrusal tamsayılı matematiksel model ve çözüm yaklaşımları". (2022), 329-345. https://doi.org/10.17341/gazimmfd.686683

APA	Saraç T, Tutumlu B (2022). İlişkisiz paralel makine çizelgeleme probleminde eniyi makine sayısının belirlenmesi içinbir doğrusal tamsayılı matematiksel model ve çözüm yaklaşımları. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 37(1), 329 - 345. 10.17341/gazimmfd.686683
Chicago	Saraç Tugba,Tutumlu Büşra İlişkisiz paralel makine çizelgeleme probleminde eniyi makine sayısının belirlenmesi içinbir doğrusal tamsayılı matematiksel model ve çözüm yaklaşımları. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 37, no.1 (2022): 329 - 345. 10.17341/gazimmfd.686683
MLA	Saraç Tugba,Tutumlu Büşra İlişkisiz paralel makine çizelgeleme probleminde eniyi makine sayısının belirlenmesi içinbir doğrusal tamsayılı matematiksel model ve çözüm yaklaşımları. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, vol.37, no.1, 2022, ss.329 - 345. 10.17341/gazimmfd.686683
AMA	Saraç T,Tutumlu B İlişkisiz paralel makine çizelgeleme probleminde eniyi makine sayısının belirlenmesi içinbir doğrusal tamsayılı matematiksel model ve çözüm yaklaşımları. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2022; 37(1): 329 - 345. 10.17341/gazimmfd.686683
Vancouver	Saraç T,Tutumlu B İlişkisiz paralel makine çizelgeleme probleminde eniyi makine sayısının belirlenmesi içinbir doğrusal tamsayılı matematiksel model ve çözüm yaklaşımları. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2022; 37(1): 329 - 345. 10.17341/gazimmfd.686683
IEEE	Saraç T,Tutumlu B "İlişkisiz paralel makine çizelgeleme probleminde eniyi makine sayısının belirlenmesi içinbir doğrusal tamsayılı matematiksel model ve çözüm yaklaşımları." Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 37, ss.329 - 345, 2022. 10.17341/gazimmfd.686683
ISNAD	Saraç, Tugba - Tutumlu, Büşra. "İlişkisiz paralel makine çizelgeleme probleminde eniyi makine sayısının belirlenmesi içinbir doğrusal tamsayılı matematiksel model ve çözüm yaklaşımları". Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 37/1 (2022), 329-345. https://doi.org/10.17341/gazimmfd.686683