A lagrange relaxation based algorithm for parallel injection machine scheduling problem

Year 2025, Volume: 40 Issue: 1, 277 - 286, 16.08.2024

Oğuzhan Ahmet Arık

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

Abstract

Plastic injection machines produce semi-finished products and products required for many sectors. The workshops where these machines come together and produce customer orders in parallel are called parallel injection machine workshops. The problem of parallel injection machine scheduling is how the orders will be produced in which order and on which machine. Connecting injection molds to machines in the production of orders and modeling whether these molds are suitable for the machines are highly addressed in parallel injection machine scheduling problems. Again, sequence-dependent preparation or mold change time is also examined extensively in the literature. This study was inspired by a parallel injection machine workshop where plastic products for the healthcare industry are produced. The problem addressed is strikingly different from the problems examined in the literature in many aspects. A parallel process that includes differences such as dividing the order into machines, processing the batch of different orders, labor costs required for production, penalty costs for products produced after the delivery time, injection machines with different production speeds, energy costs and consideration of order-mould-machine compatibility. A mathematical model is proposed for the injection machine scheduling problem. In addition, the proposed mathematical model was ensured to be linear with all its constraints and objective function. A tool has been developed to solve real-life problems by solving the mathematical model proposed for the problem under consideration with Lagrange relaxation. Test problems of different sizes were created to test the validity of the established mathematical model and the Lagrange relaxation-based algorithm. It has been observed that the Lagrange relaxation-based algorithm converges better to the optimum solution, and the performance of the proposed algorithm has been determined to be better than the mathematical model.

Keywords

Plastic injection, parallel machine, job splitting, batch processing, energy cost, scheduling.

Supporting Institution

Nuh Naci Yazgan University

Project Number

2022-F-BP-2

Thanks

This study was conducted by researcher Assoc. Dr. While Oğuzhan Ahmet ARIK was working at Kayseri Nuh Naci Yazgan University, he received partial support within the scope of the scientific research project coded 2022-F-BP-2. Before the project period ended, many faculty members of the relevant university were dismissed for unfair reasons. This study is attributed to faculty members who were dismissed from their jobs during the winter months and had to leave their students, friends and homes.

Paralel enjeksiyon makine çizelgeleme problemi için lagrange gevşetme temelli bir algoritma

Abstract

Plastik enjeksiyon makineleri bir çok sektör için gerekli olan yarı mamul ve mamulleri üretmektedir. Bu makinelerin bir araya gelerek paralel bir şekilde müşteri siparişlerini ürettikleri atölyelere paralel enjeksiyon makine atölyesi olarak adlandırılmaktadır. Siparişlerin hangi sıra ile hangi makinede üretileceği ise paralel enjeksiyon makinesi çizelgeleme problemidir. Siparişlerin üretilmesinde enjeksiyon kalıplarının makinelere bağlanması ve bu kalıpların makineler için uygun olup olmadığının modellenmesi paralel enjeksiyon makine çizelgeleme problemlerinde oldukça ele alınmaktadır. Yine sıra bağımlı hazırlık veya kalıp değişim süresi de literatürde oldukça fazla incelenmektedir. Bu çalışmaya sağlık sektörü için plastik ürünlerin üretimin gerçekleştiği bir paralel enjeksiyon makinesi atölyesinden esinlenmiştir. Ele alınan problem bir çok yönü ile literatürdeki incelenen problemlerden dikkat çekici oranda farklıdır. Siparişin makinelere bölünmesi, farklı siparişlerin oluşturduğu yığının işlenmesi, üretim için gerekli işgücü maliyetleri, teslim zamanından sonra üretilen ürünlere ait olan ceza maliyetleri, farklı üretim hızlarına sahip enjeksiyon makinaları, enerji maliyetleri ve sipariş-kalıp-makine uygunluğunun göz önünde bulundurulması gibi farklılıkları içeren bir paralel enjeksiyon makine çizelgeleme problemi için matematiksel model önerilmiştir. Ayrıca önerilen matematiksel modelin tüm kısıtları ve amaç fonksiyonu ile beraber doğrusal olması sağlanmıştır. Ele alınan problem için önerilen matematiksel modelin Lagrange gevşetme ile çözülmesini sağlayarak gerçek hayat problemlerin çözülebilmesi için bir araç geliştirilmiştir. Kurulan matematiksel modelin ve Lagrange gevşetme temelli algoritmanın geçerliliklerini test etmek için farklı büyüklüklerde test problemleri oluşturulmuştur. Lagrange gevşetme temelli algoritmanın optimum çözüme daha iyi yakınsadığı gözlemlenmiş ve önerilen algoritmanın performansının matematiksel modelden daha iyi olduğu belirlenmiştir.

Keywords

Plastik enjeksiyon, paralel makine, iş bölüştürme, yığın işleme, enerji maliyeti, çizelgeleme

Supporting Institution

Nuh Naci Yazgan Üniversitesi

Project Number

2022-F-BP-2

Thanks

Bu çalışma araştırmacı Doç. Dr. Oğuzhan Ahmet ARIK’ın Kayseri Nuh Naci Yazgan Üniversitesinde görevli olduğu zamanlarda 2022-F-BP-2 kodlu bilimsel araştırma projesi kapsamında kısmı olarak destek almıştır. Proje süresi bitmeden ilgili üniversitenin bir çok öğretim üyesi haksız sebeplerle işten çıkartılmıştır. Bu çalışma kış aylarında görevlerine son verilen, öğrencilerinden, arkadaşlarından ve evlerinden ayrılmak zorunda kalan öğretim üyelerine atfedilmiştir.

References

• 1. Ríos-Solís, Y. Á., Ibarra-Rojas, O. J., Cabo, M., Possani, E., A heuristic based on mathematical programming for a lot-sizing scheduling problem in mold-injection production, Eur. J. Oper. Res., 284 (3), 861–873, 2020.
• 2. Salimifard, K., Li, J., Mohammadi, D., Moghdani, R., A multi objective volleyball premier league algorithm for green scheduling identical parallel machines with splitting jobs, Appl. Intell., 51 (7), 4143–4161, 2021.
• 3. Akyol Ozer, E. Sarac, T., MIP models and a matheuristic algorithm for an identical parallel machine scheduling problem under multiple copies of shared resources constraints, TOP, 27 (1), 94–124, 2019.
• 4. Blazewicz, J., Lenstra, J. K., Kan, A. H. G. R., Scheduling subject to resource constraints: classification and complexity, Discret. Appl. Math., 5 (1), 11–24, 1983.
• 5. Song, Y., Xue, M., Hua, C., Wang, W., A Column Generation Algorithm for the Resource-Constrained Order Acceptance and Scheduling on Unrelated Parallel Machines, Math. Probl. Eng., 5566002, 2021.
• 6. Soares, L. C. R. and Carvalho, M. A. M., Application of a hybrid evolutionary algorithm to resource-constrained parallel machine scheduling with setup times, Comput. Oper. Res., 139, 2022.
• 7. Avgerinos, I., Mourtos, I., Vatikiotis, S., Zois, G., Weighted tardiness minimisation for unrelated machines with sequence-dependent and resource-constrained setups, Int. J. Prod. Res., 62 (1–2), 359–379, 2024.
• 8. Geurtsen, M., Adan, J., Akçay, A., Integrated maintenance and production scheduling for unrelated parallel machines with setup times, Flex. Serv. Manuf. J., 2023.
• 9. Şaştım, Ö. and Hasgül, S., A mathematical model for the unrelated parallel machine scheduling problem with common server and process resource constraints, Journal of the Faculty of Engineering and Architecture of Gazi University, 39 (1), 607–619, 2023.
• 10. Jemmali, M., Ben Hmida, A., Quick dispatching-rules-based solution for the two parallel machines problem under mold constraints, Flex. Serv. Manuf. J., 2023.
• 11. Takan, A., Saraç, T., New representation schemes for identical parallel machine scheduling problems with sequence dependent setup times, Journal of the Faculty of Engineering and Architecture of Gazi University, 38 (2), 1041–1054, 2023.
• 12. 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–2307, 2022.
• 13. Saraç, T., Özçelik, F., A matheuristic algorithm for multi-objective unrelated parallel machine scheduling problem, Journal of the Faculty of Engineering and Architecture of Gazi University, 38 (3), 1953–1966, 2023.
• 14. Arık, O.A., Toksarı, M.D., Multi-objective fuzzy parallel machine scheduling problems under fuzzy job deterioration and learning effects, Int. J. Prod. Res., 56 (7), 2488–2505, 2018.
• 15. Arık, O. A., Comparisons of metaheuristic algorithms for unrelated parallel machine weighted earliness/tardiness scheduling problems, Evol. Intell., 13, 415–425, 2020.
• 16. Arık, O. A., Schutten, M., Topan, E., Weighted earliness/tardiness parallel machine scheduling problem with a common due date, Expert Syst. Appl., 187, 115916, 2022.
• 17. Fisher, M. L., Jaikumar, R., A generalized assignment heuristic for vehicle routing, Networks, 11 (2), 109–124, 1981.
• 18. Edis, E. B., Araz, C., Ozkarahan, I., Lagrangian-Based Solution Approaches for a Resource-Constrained Parallel Machine Scheduling Problem with Machine Eligibility Restrictions, New Frontiers in Applied Artificial Intelligence, Vol 1, Editör: Nguyen, N.T., Borzemski, L., Grzech, A., Ali, M., Springer, Berlin, Heidelberg, 337-346, 2008.
• 19. Emami, S., Sabbagh, M., Moslehi, G., A Lagrangian relaxation algorithm for order acceptance and scheduling problem: A globalised robust optimisation approach, Int. J. Comput. Integr. Manuf., 29 (5), 535–560, 2016.
• 20. Kayish, B., Dy Cheng Beng, G., A pc-based production scheduling system using a mixed integer programming approach, Int. J. Prod. Res., 32 (6), 1331–1346, 1994.
• 21. Terano, K., Yao, Y., Okamoto, K., Hashimoto, Y., Nishikawa, I., Watanabe, T., Tokumaru, H., Application of simulated annealing method and genetic algorithm to scheduling problems in plastic injection molding, Proc. Japan/USA Symp. Flex. Autom., 1225–1228, 1996.
• 22. Tanev, I. T., Uozumi, T., Morotome, Y., Hybrid evolutionary algorithm-based real-world flexible job shop scheduling problem: Application service provider approach, Appl. Soft Comput. J., 5 (1), 87–100, 2004.
• 23. Huiyuan, R., Lili, J., Xiaoying, X., Muzhi, L., Heuristic optimization for dual-resource constrained job shop scheduling, Proc. - 2009 Int. Asia Conf. Informatics Control. Autom. Robot. CAR 2009, 485–488, 2009.
• 24. Gong, G., Lu, N., Lu, J., Yang, Y., A single machine scheduling strategy for energy saving in injection molding process, Annu. Tech. Conf. - ANTEC, Conf. Proc., 2209–2213, 2012.
• 25. Wong, C. S., Chan, F. T. S., Chung, S. H., A joint production scheduling approach considering multiple resources and preventive maintenance tasks, Int. J. Prod. Res., 51 (3), 883–896, 2013.
• 26. Wong, C. S., Chan, F. T. S., Chung, S. H., Injection Mold Maintenance Scheduling with Mold-Lifting Crane Consideration, Lect. Notes Mech. Eng., 7, 1117–1128, 2013.
• 27. Paolucci, M., Anghinolfi, D., Tonelli, F., Facing energy-aware scheduling: a multi-objective extension of a scheduling support system for improving energy efficiency in a moulding industry, Soft Comput., 21 (13), 3687–3698, 2017.
• 28. Şafak, C. U., Yilmaz, G., Albey, E., A hierarchical approach for solving simultaneous lot sizing and scheduling problem with secondary resources, IFAC-PapersOnLine, 1931–1936, 2019.
• 29. Ishihara, M., Hibino, H., Harada, T., Simulated annealing based simulation method for minimizing electricity cost considering production line scheduling including injection molding machines, J. Adv. Mech. Des. Syst. Manuf., 14 (4), 2020.
• 30. Wulung, R. B. S.,Wibowo, M. D., Parallel injection molding machine scheduling by considering parameter process conservation, AIP Conf. Proc., 2217 (1), 030116, 2020.
• 31. Ayad, G. and Fahim, I. S., A Practical Scheduling Optimizer for Plastic Injection Molding Facilities, 2020 Int. Conf. Decis. Aid Sci. Appl. DASA 2020, 943–947, 2020.
• 32. Cervantes-Sanmiguel, K. I., Vargas-Flores, M. J., Ibarra-Rojas, O. J., A two-stage sequential approach for scheduling with lot-sizing decisions in the context of plastic injection systems, Comput. Ind. Eng., 151, 2021.
• 33. Aslaner, A. A., Coşkun, A., Tülemiş, N. İ., Özboyacı, E., Ergün, N., Bulut, B., Gülbent, G., Paldrak, M., Staiou, E., A Parallel Machine Scheduling Problem for a Plastic Injection Company, ISPR 2020: Digital Conversion on the Way to Industry 4.0, Editors: Durakbasa, N.M., Gençyılmaz, M.G., Springer, Cham, 790-903, 2021.
• 34. Andres, B., Guzman, E., Poler, R., A Novel MILP Model for the Production, Lot Sizing, and Scheduling of Automotive Plastic Components on Parallel Flexible Injection Machines with Setup Common Operators, Complexity, 6667516, 2021.
• 35. Ozcelik, F., Ertem, M., Saraç, T., A stochastic approach for the single-machine scheduling problem to minimize total expected cost with client-dependent tardiness costs, Eng. Optim., 54 (7), 1178–1192, 2022.
• 36. Sadeghi, P., Guardão, L., Rebelo, R. D., Ferreira, J. S., Scheduling footwear moulding injection machines for a long time horizon, Proc. Int. Conf. Ind. Eng. Oper. Manag., 5281–5292, 2021.
• 37. Ghaleb, M., Namoura, H. A., Taghipour, S., Reinforcement Learning-based Real-time Scheduling under Random Machine Breakdowns and Other Disturbances: A Case Study, Proc.-Annu. Reliab. Maintainab. Symp., Orlando, FL, USA, 1-8, 2021.
• 38. Klement, N., Abdeljaouad, M. A., Porto, L., Silva, C., Lot-sizing and scheduling for the plastic injection molding industry-A hybrid optimization approach, Appl. Sci., 11 (3), 1–13, 2021.
• 39. Sarac, T., Sipahioglu, A., Ozer, E. A., A Two-stage solution approach for plastic injection machines scheduling problem, J. Ind. Manag. Optim., 17 (3), 1289–1314, 2021.
• 40. Mula, J., Díaz-Madroñero, M., Andres, B., Poler, R., Sanchis, R., A capacitated lot-sizing model with sequence-dependent setups, parallel machines and bi-part injection moulding, Appl. Math. Model., 100, 805–820, 2021.
• 41. Bazargan-Lari, M. R., Taghipour, S., Zaretalab, A., Sharifi, M., Production scheduling optimization for parallel machines subject to physical distancing due to COVID-19 pandemic, Oper. Manag. Res., 15 (1–2), 503–527, 2022.
• 42. Fisher, M. L., Applications oriented guide to lagrangian relaxation., Interfaces (Providence)., 15 (2), 10–21, 1985.
• 43. Held, M., Wolfe, P., Crowder, H. P., Validation of subgradient optimization, Math. Program., 6 (1), 62–88, 1974.