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

Yıl 2022, Cilt: 37 Sayı: 1, 329 - 346, 10.11.2021

Tuğba Saraç , Büşra Tutumlu

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

Cited By: 2

Öz

Paralel makine çizelgeleme problemlerini ele alan çalışmalarda 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 makinaların kullanılacağı varsayımı kaldırılmıştır, sıra ve makina bağımlı hazırlık sürelerinin ve makine uygunluklarının dikkate alındığı ilişkisiz paralel makine çizelgeleme probleminde hem hangi makinaların kullanılacağına hem de kullanılacak makinalarda 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 geliştirilmiştir. Elde edilen deneysel sonuçlar, genetik algoritmanın yerel arama algoritmasına göre daha başarılı olduğunu göstermiştir.

Anahtar Kelimeler

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

Kaynakça

• 1. Pinedo, M., Scheduling: Theory, Algorithms and Systems, Springer Science Business Media, New York, 665, 2008.
• 2. Akyol, E. ve Saraç, T., Paralel makina ç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. Yepes-Borrero, J. C., Villa, F. ve Perea, F., GRASP Algorithm for The Unrelated Parallel Machine Scheduling Problem with Setup Times and Additional Resources, Expert Systems With Applications, 141, 2020.
• 4. Cota, L. P., Guimaraes, F. G., Ribeiro, R. G., Meneghini, I. R., de Oliveira, F. D., Souza, M., J., F. ve 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.
• 5. Jouhari, H., Lei, D. M, Al-qaness, M., A., A., Abd Elaziz, M., Ewees, A. A. ve Farouk, O., Sine-Cosine Algorithm to Enhance Simulated Annealing for Unrelated Parallel Machine Scheduling with Setup Times, Mathematics, 7(11) , 2019.
• 6. Ekici, A., Elyasi, M., Ozener, O. O. ve 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.
• 7. Ezugwu, A. E., Enhanced symbiotic organisms search algorithm for unrelated parallel machines manufacturing scheduling with setup times, Knowledge-Based Systems, 172, 15-32, 2019.
• 8. Bektur, G. ve 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.
• 9. Fanjul-Peyro, L., Ruiz, R. ve Perea, F., Reformulations and an exact algorithm for unrelated parallel machine scheduling problems with setup times, Computers & Operations Research, 101, 173-182, 2019.
• 10. Ezugwu, A. E. ve Akutdah, F., An improved firefly algorithm for the unrelated parallel machines scheduling problem with sequence-dependent setup times, IEEE Access, 6, 54459-54478, 2018.
• 11. Tozzo, E., Cotrim, S. L., Galdamez, E. V. C. ve 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.
• 12. 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.
• 13. 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.
• 14. 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.
• 15. 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.
• 16. 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.
• 17. 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.
• 18. 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.
• 19. 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, Int. J. Adv. Manuf. Technol., 76, 1705- 1718, 2015.
• 20. 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, J. Intell. Manuf., 21, 693- 701, 2010.
• 21. 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.
• 22. 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.
• 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. Li, Q., Milne, R. J., A production scheduling problem with sequence dependent changeover cost, International Journal of Production Research, 52, 13, 4093- 4102, 2014.
• 25. 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.
• 26. 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.
• 27. 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.
• 28. 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.
• 29. 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, Int. J. Adv. Manuf. Technol, 69, 2081- 2089, 2013.
• 30. 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.
• 31. Bozorgirad, M. A., Logendran, R., Sequence dependent group scheduling problem on unrelated parallel machines, Expert Systems With Applications, 39, 9021- 9030, 2012.
• 32. 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.
• 33. 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.
• 34. 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, J. Intell. Manuf., 23, 1949- 1958, 2012.
• 35. 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.
• 36. Wang, I., Wang, Y. C., Chen, C. W., Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics, Flex Serv. Manuf. J., 25, 343- 366, 2012.
• 37. Ying, K. C., Lee, Z. J., Lin, S. W., Makespan minimization for scheduling unrelated parallel machines with setup times, J. Intell. Manuf,. 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. 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.
• 40. 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.
• 41. 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.
• 42. 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, Int. J. Adv. Manuf. Technol., 53, 353- 361, 2011.
• 43. 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.
• 44. Ruiz, R., Andres- Romano, C., Scheduling unrelated parallel machines with resource- assignable sequence- dependent setup times, Int. J. Adv. Manuf. Techn., 57, 777- 794, 2011.
• 45. 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.
• 46. 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, J Intell manuf, 21, 693- 701, 2010.
• 47. 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.
• 48. 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.
• 49. 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.
• 50. Talbi, E. G., Metaheuristics From Design To Implementation, John Wiley and Sons, 2009.
• 51. Çalışkan, F., Yüksel, H. Ve Dayık, M., Genetik algoritmaların tasarım sürecinde kullanılması, SDU Teknik Bilimler Dergisi, 6(2), 21-27, 2016.
• 52. Goldberg, D. E., Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, USA, 1989.
• 53. Deb, K., Genetic algorithms for function optimization, Genetic Algorithms and Soft Computing, pp. 3-19, Eds. Herrera, F. & Verdegay, J L., Physica – Verlag, Heidelberg, 1996.