The Unrelated Parallel Machines Scheduling Problem with Machine and Job Dependent Setup Times, Availability Constraints, Time Windows and Maintenance Times

• Autorzy: Agárdi Anita , Nehéz Károly

Identyfikatory

DOI

10.24425/mper.2021.138527

• Języki publikacji: EN

Abstrakty

EN

Unrelated Parallel Machines Scheduling Problem (U-PMSP) is a category of discrete optimization problems in which various manufacturing jobs are assigned to identical parallel machines at particular times. In this paper, a specific production scheduling task the U-PMSP with Machine and Job Dependent Setup Times, Availability Constraint, Time Windows and Maintenance Times is introduced. Machines with different capacity limits and maintenance times are available to perform the tasks. After that our problem, the U-PMSP with Machine and Job Dependent Setup Times, Availability Constraints, Time Windows and Maintenance Times is detailed. After that, the applied optimization algorithm and their operators are introduced. The proposed algorithm is the genetic algorithm (GA), and proposed operators are the order crossover, partially matched crossover, cycle crossover and the 2-opt as a mutation operator. Then we prove the efficiency of our algorithm with test results. We also prove the efficiency of the algorithm on our own data set and benchmark data set. The authors conclude that this GA is effective for solving high complexity parallel machine problems.

Słowa kluczowe

EN

production scheduling; parallel machine; setup time; time windows; genetic algorithm

• Wydawca: Production Engineering Committee of the Polish Academy of Sciences ; Polish Association for Production Management
• Czasopismo: Management and Production Engineering Review
• Rocznik: 2021
• Tom: Vol. 13, No. 3
• Strony: 15--24
• Opis fizyczny: Bibliogr. 26 poz., rys., tab.

Twórcy

autor

Agárdi Anita

• Institute of Information Science, University of Miskolc, Miskolc, Hungary, 3515

• https://orcid.org/0000-0001-9148-1214

autor

Nehéz Károly

• Institute of Information Science, University of Miskolc, Hungary

• https://orcid.org/0000-0002-6953-3898

Bibliografia

• Al-Shayea, A.M., Saleh, M., Alatefi, M., and Ghaleb, M. (2020). Scheduling Two Identical Parallel Machines Subjected to Release Times, Delivery Times and Unavailability Constraints. Processes, 8, 9, 1025. DOI: 10.3390/pr8091025.
• Chan, K.C. and Tansri, H. (1994). A study of genetic crossover operations on the facilities layout problem. Computers & Industrial Engineering, 26, 3, 537–550. DOI: 10.1016/0360-8352(94)90049-3.
• Chaudhry, I.A. and Khan, A.A. (2016). A research survey: review of flexible job shop scheduling techniques. International Transactions in Operational Research, 23, 3, 551–591. DOI: 10.1111/itor.12199.
• Chung, B.D. and Kim, B.S. (2016). A hybrid genetic algorithm with two-stage dispatching heuristic for a machine scheduling problem with step-deteriorating jobs and rate-modifying activities. Computers & Industrial Engineering, 98, 113–124. DOI: 10.1016/j.cie. 2016.05.028.
• Damodaran, P., Hirani, N.S., and Velez-Gallego, M.C. (2009). Scheduling identical parallel batch processing machines to minimise makespan using genetic algorithms. European Journal of Industrial Engineering, 3, 2, 187–206. DOI: 10.1504/ejie.2009.023605.
• Dell’Amico, M. and Trubian, M. (1993). Applying tabu search to the job-shop scheduling problem. Annals of Operations research, 41, 3, 231–252. DOI: 10.1007/bf02023076.
• Englert, M., Röglin, H., and Vöcking, B. (2007). Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, 1295–1304. DOI: 10.1007/s00453-013-9801-4.
• Gharbi, A. and Haouari, M. (2005). Optimal parallel machines scheduling with availability constraints. Discrete Applied Mathematics, 148, 1, 63–87. DOI: 10.1016/j.dam.2004.12.003.
• Graham, R.L., Lawler, E.L., Lenstra, J.K., and Kan, A.R. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. In Annals of discrete mathematics, 5, 287–326. DOI: 10.1016/s0167-5060(08)70356-x.
• Hwang, H.C. and Chang, S.Y. (1998). Parallel machines scheduling with machine shutdowns. Computers & Mathematics with Applications, 36, 3, 21–31. DOI: 10.1016/s0898-1221(98)00126-6.
• Kravchenko, S.A. and Werner, F. (1997). Parallel machine scheduling problems with a single server. Mathematical and Computer Modelling, 26, 12, 1–11. DOI: 10.1016/s0895-7177(97)00236-7.
• Lee, C.Y. and Chen, Z.L. (2000). Scheduling jobs and maintenance activities on parallel machines. Naval Research Logistics (NRL), 47, 2, 145–165. DOI: 10. 1002/(sici)1520-6750(200003)47:2%3C145::aid-nav 5%3E3.0.co;2-3.
• Lee, C.Y. and Liman, S.D. (1993). Capacitated twoparallel machines scheduling to minimize sum of job completion times. Discrete Applied Mathematics, 41, 3, 211–222. DOI: 10.1016/0166-218x(90)90055-h.
• Lenstra, J.K., Shmoys, D.B., and Tardos, E. (1990). Approximation algorithms for scheduling unrelated parallel machines. Mathematical programming, 46, 1–3, 259–271. DOI: 10.1007/bf01585745.
• Li, Z., Yang, H., Zhang, S., and Liu, G. (2015). Unrelated parallel machine scheduling problem with energy and tardiness cost. The International Journal of Advanced Manufacturing Technology, 84, 1–4, 213–226. DOI: 10.1007/s00170-015-7657-2.
• Liaw, C.F., Lin, Y.K., Cheng, C.Y., and Chen, M. (2003). Scheduling unrelated parallel machines to minimize total weighted tardiness. Computers & Operations Research, 30, 12, 1777–1789. DOI: 10.1016/s0305-0548(02)00105-3.
• Lin, Y.K., Pfund, M.E., and Fowler, J.W. (2011). Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems. Computers & Operations Research, 38, 6, 901–916. DOI: 10.1016/j.cor.2010.08.018.
• Pezzella, F., Morganti, G. and Ciaschetti, G. (2008). A genetic algorithm for the flexible job-shop scheduling problem. Computers & Operations Research, 35, 10, 3202–3212. DOI: 10.1016/j.cor.2007.02.014.
• Rajakumar, S., Arunachalam, V.P. and Selladurai, V. (2006). Workflow balancing in parallel machines through genetic algorithm. The International Journal of Advanced Manufacturing Technology, 33, 11–12, 1212–1221. DOI: 10.1007/s00170-006-0553-z.
• Tanaka, S., Total Tardiness Problem on Identical Parallel Machines. https://sites.google.com/site/shunjitanaka/pmtt [Accessed: 2019.12.23.]
• Tavakkoli-Moghaddam, R., Taheri, F., Bazzazi, M., Izadi, M. and Sassani, F. (2009). Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints. Computers & Operations Research, 36, 12, 3224–3230. DOI: 10.1016/j.cor.2009. 02.012.
• Vallada, E. and Ruiz, R. (2011). A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times. European Journal of Operational Research, 211, 3, 612–622. DOI: 10.1016/j.ejor.2011.01.011.
• Whitley, D. (1994). A genetic algorithm tutorial. Statistics and computing, 4, 2, 65–85. DOI: 10.1007/bf00175354.
• Woo, Y.-B., Jung, S., and Kim, B.S. (2017). A rulebased genetic algorithm with an improvement heuristic for unrelated parallel machine scheduling problem with time-dependent deterioration and multiple rate-modifying activities. Computers & Industrial Engineering, 109, 179–190. DOI: 10.1016/j.cie.2017.05.007.
• Yang, D.-L., Cheng, T.C.E., Yang, S.-J., and Hsu, C.-J. (2012). Unrelated parallel-machine scheduling with aging effects and multi-maintenance activities. Computers & Operations Research, 39, 7, 1458–1464. DOI: 10.1016/j.cor.2011.08.017.
• Zhang, A., Jiang, Y., and Tan, Z. (2009). Online parallel machines scheduling with two hierarchies. Theoretical Computer Science, 410, 38–40, 3597–3605. DOI: 10.1016/j.tcs.2009.04.007.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023)