Ortak sunuculu ve proses kaynak kısıtlı ilişkisiz paralel makine çizelgeleme problemi için bir matematiksel model

Year 2024, Volume: 39 Issue: 1, 607 - 620, 21.08.2023

Özgür Şaştım Servet Hasgül

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

Abstract

İlişkisiz paralel makinelerin ilave kaynaklar ile birlikte çizelgelenmesi için bütünleşik bir problem bu çalışmada ele alınmıştır. Üretim ortamında kullanılan makine veya tezgâh gibi kaynaklarla birlikte ilave kaynakların da kullanımı söz konusudur. İlave kaynakların kullanımı hem hazırlık hem de proses aşamasında olabilir. Hazırlık aşamasında ilave kaynak olarak ortak sunucunun kullanımıyla, ortak sunuculu makine çizelgeleme problemi ortaya çıkmaktadır. Proses aşamasında ilave kaynak kullanımıyla ise, kaynak kısıtlı makine çizelgeleme problemi oluşmaktadır. Bu iki ayrı problem bütünleştirilerek, tek bir problem olarak tanımlanmış ve matematiksel model geliştirilmiştir. Problemin karmaşık yapısından dolayı büyük boyutlu problemlerin çözümü için metasezgisel yöntemler önerilmiştir. Önerilen yöntemler, rassal türetilen problemlerde test edilmiştir. Hesaplama sonuçları, küçük boyutlu problemlerde matematiksel modelin, orta ve büyük boyutlu problemlerde tavlama benzetimi algoritmasının daha başarılı sonuçlar elde ettiğini göstermiştir.

Keywords

İlişkisiz paralel makine, çizelgeleme, ilave kaynak, kaynak kısıtları, ortak sunucu

A mathematical model for the unrelated parallel machine scheduling problem with common server and process resource constraints

Abstract

An integrated problem for unrelated parallel machine scheduling with additional resources is considered in this study. In addition to resources such as machines or workbenches used in the production environment, there is also the use of additional resources. Additional resources can be used both in the setup and process stage. With the use of a common server as an additional resource in the setup stage, machine scheduling problem with common server arises. With the use of additional resources in the process phase, resource-constrained machine scheduling problem occurs. By integrating these two separate problems, a single problem is defined, and a mathematical model is developed. Due to the complexity of the problem, metaheuristic methods are proposed for solving large-scale problems. The proposed methods are tested in randomly derived problems. The computation results show that the mathematical model for small-sized problems and simulation annealing algorithm for medium and large-sized problems achieved better results.

Keywords

Unrelated parallel machine, scheduling, additional resource, resource constraints, common server

References

• Pinedo, M., Scheduling: Theory, Algorithms and Systems, Springer, New York, A.B.D., 2012.
• Hall, N.G., Potts, C.N., Sriskandarajah, C., Parallel machine scheduling with a common server, Discrete Applied Mathematics, 102(3), 223-243, 2000.
• Akyol, E., Saraç, T., A mix integer programming model for parallel machine scheduling problem: Using shared resource, Journal of Science Part C: Design and Technology of Gazi University, 5(3), 109-126, 2017.
• Blazewicz, J., Lenstra, J.K., Rinnoy Kan, A.H.G., Scheduling subject to resource constraints: Classificiation and complexity, Discrete Applied Mathematics, 5, 11-24, 1983.
• Edis, E.B., Oguz, C., Ozkarahan, I., Parallel machine scheduling with additional resources: Notation, classification, models and solution methods, European Journal of Operational Research, 230(3), 449-463, 2013.
• 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.
• Edis, E.B., Oguz, C., Ozkarahan, I., Solution approaches for simultaneous scheduling of jobs and operators on parallel machines, Journal of the Faculty of Engineering and Architecture of Gazi University, 27(3), 527-535, 2012.
• Ayaz, H.I., Ozturk, Z., A mathematical model and a heuristic approach for train seat scheduling to minimize dwell time, Computers & Industrial Engineering, 160, 107590, 2021.
• Graham, R., Lawler, L.E.L., Lenstra, J.K.L., Rinnooy Kan, A.H.G., Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 5, 287–326, 1979.
• Lenstra, J.K., Rinnooy Kan, A.H.G., Brucker, P., Complexity of machine scheduling problems, Annals of Discrete Mathematics, 1, 343–362, 1977.
• Garey, M., Johnson, D., Complexity results for multiprocessor scheduling under resource constraints, SIAM Journal on Computing, 4, 397–411, 1975.
• Abdekhodaee, A.H., Wirth, A., Scheduling parallel machines with a single server: Some solvable cases and heuristics, Computers & Operations Research, 29(3), 295-315, 2002.
• Afzalirad, M., Shafipour, M., Design of an efficient genetic algorithm for resource-constrained unrelated parallel machine scheduling problem with machine eligibility restrictions, Journal of Intelligent Manufacturing, 29(2), 423-437, 2018.
• 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.
• Al-Harkan, I.M., Qamhan, A.A., Optimize unrelated parallel machines scheduling problems with multiple limited additional resources, sequence-dependent setup times and release date constraints, IEEE Access, 7, 171533-171547, 2019.
• Al-Harkan, I.M., Qamhan, A.A., Badwelan, A., Alsamhan, A., Hidri, L., Modified harmony search algorithm for resource-constrained parallel machine scheduling problem with release dates and sequence-dependent setup times, Processes, 9(4), 654, 2021.
• Tamaki, H., Hasegawa, Y., Kozasa, J., Araki, M., Application of search methods to scheduling problem in plastics forming plant: A binary representation approach, 32nd IEEE Conference on Decision and Control, San Antonio-A.B.D., 3845-3850, 15-17 December, 1993.
• Chen, J.F., Unrelated parallel machine scheduling with secondary resource constraints, The International Journal of Advanced Manufacturing Technology, 26(3), 285-292, 2005.
• Dastidar, S.G., Nagi, R., Scheduling injection molding operations with multiple resource constraints and sequence dependent setup times and costs, Computers & Operations Research, 32(11), 2987-3005, 2005.
• Chen, J.F., Minimization of maximum tardiness on unrelated parallel machines with process restrictions and setups, The International Journal of Advanced Manufacturing Technology, 29(5), 557-563, 2006.
• Chen, J.F., Wu, T.H., Total tardiness minimization on unrelated parallel machine scheduling with auxiliary equipment constraints, Omega, 34(1), 81-89, 2006.
• Zhang, Z., Zheng, L., Hou, F., Li, N., Semiconductor final test scheduling with Sarsa (λ,k) algorithm, European Journal of Operational Research, 215(2), 446-458, 2011.
• Lozano, A.J., Medaglia, A.L., Scheduling of parallel machines with sequence-dependent batches and product incompatibilities in an automotive glass facility, Journal of Scheduling, 17(6), 521-540, 2014.
• Özpeynirci, S., Gökgür, B., Hnich, B., Parallel machine scheduling with tool loading, Applied Mathematical Modelling, 40(9), 5660-5671, 2016.
• Zhu, W., Tianyu, L., A novel multi-objective scheduling method for energy based unrelated parallel machines with auxiliary resource constraints, IEEE Access, 7, 168688-168699, 2019.
• Ruiz, R., Fanjul, L., Perea, F., A bin packing reformulation and matheuristics for the unrelated parallel machines scheduling problem with resources, Actas de la XVI Conferencia de la Asociación Española para la Inteligencia Artificial, Albacete- Spain, 1183-1192, 9-12 November, 2015.
• Fanjul, L., Perea, F., Ruiz, R., Algorithms for the unspecified unrelated parallel machine scheduling problem with additional resources, 2015 International Conference on Industrial Engineering and Systems Management (IESM), Seville-Spain, 69-73, 21-23 October, 2015.
• Fanjul-Peyro, L., Perea, F., Ruiz, R., Models and matheuristics for the unrelated parallel machine scheduling problem with additional resources, European Journal of Operational Research, 260(2), 482-493, 2017.
• Villa, F., Vallada, E., Fanjul-Peyro, L., Heuristic algorithms for the unrelated parallel machine scheduling problem with one scarce additional resource, Expert Systems with Applications, 93, 28-38, 2018.
• Fleszar, K., Hindi, K.S., Algorithms for the unrelated parallel machine scheduling problem with a resource constraint, European Journal of Operational Research, 271(3), 839-848, 2018.
• Vallada, E., Villa, F., Fanjul-Peyro, L., Enriched metaheuristics for the resource constrained unrelated parallel machine scheduling problem, Computers & Operations Research, 111, 415-424, 2019.
• Fanjul-Peyro, L., Models and an exact method for the unrelated parallel machine scheduling problem with setups and resources, Expert Systems with Applications: X, 5, 100022, 2020.
• Su, B., Xie, N., Yang, Y., Hybrid genetic algorithm based on bin packing strategy for the unrelated parallel workgroup scheduling problem, Journal of Intelligent Manufacturing, 32, 957-969, 2021.
• Zheng, X. L., Wang, L., A two-stage adaptive fruit fly optimization algorithm for unrelated parallel machine scheduling problem with additional resource constraints, Expert Systems with Applications, 65, 28-39, 2016.
• Qamhan, A.A., Alharkan, I.M., Note on A two-stage adaptive fruit fly optimization algorithm for unrelated parallel machine scheduling problem with additional resource constraints, Expert Systems with Applications, 128, 81-83, 2019.
• Torabi, S. A., Sahebjamnia, N., Mansouri, S. A., Bajestani, M. A., A particle swarm optimization for a fuzzy multi-objective unrelated parallel machines scheduling problem, Applied Soft Computing, 13(12), 4750-4762, 2013.
• Bitar, A., Dauzère-Pérès, S., Yugma, C., Roussel, R., A memetic algorithm to solve an unrelated parallel machine scheduling problem with auxiliary resources in semiconductor manufacturing, Journal of Scheduling, 19(4), 367-376, 2016.
• Manupati, V.K., Rajyalakshmi, G., Chan, F.T., Thakkar, J.J., A hybrid multi-objective evolutionary algorithm approach for handling sequence-and machine-dependent set-up times in unrelated parallel machine scheduling problem, Sādhanā, 42(3), 391-403, 2017.
• Ruiz, R., Andrés, C., Unrelated parallel machines scheduling with resource-assignable sequence dependent setup times, 3rd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA), Paris-France, 439-446, 28-31 August, 2007.
• Pessan, C., Neron, E., Setup tasks scheduling during production resettings, International Journal of Production Research, 49(22), 6787-6811, 2011.
• Kerkhove, L.P., Vanhoucke, M., Scheduling of unrelated parallel machines with limited server availability on multiple production locations: a case study in knitted fabrics, International Journal of Production Research, 52(9), 2630-2653, 2014.
• 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.
• Yepes-Borrero, J.C., Villa, F., Perea, F., Caballero-Villalobos, J.P., GRASP algorithm for the unrelated parallel machine scheduling problem with setup times and additional resources, Expert Systems with Applications, 141, 112959, 2020.
• Kirkpatrick, S., Gelatt, S., Vecchi, M., Optimization by simulated annealing, Science, 220 (4598), 671- 680, 1983.