An Accurate and Robust Genetic Algorithm to Minimize the Total Tardiness in Parallel Machine Scheduling Problems

• Autorzy: Ramadan Saleem Zeyad , Almasarwah Najat , Abdelall Esraa S. , Suer Gursel A. , Albashabsheh Nibal T.

Identyfikatory

DOI

10.24425/mper.2023.147201

• Języki publikacji: EN

Abstrakty

EN

This paper uses a Genetic Algorithm (GA) to reduce total tardiness in an identical parallel machine scheduling problem. The proposed GA is a crossover-free (vegetative reproduction) GA but used for four types of mutations (Two Genes Exchange mutation, Number of Jobs mutation, Flip Ends mutation, and Flip Middle mutation) to make the required balance between the exploration and exploitation functions of the crossover and mutation operators. The results showed that use of these strategies positively affects the accuracy and robustness of the proposed GA in minimizing the total tardiness. The results of the proposed GA are compared to the mathematical model in terms of the time required to tackle the proposed problem. The findings illustrate the ability of the propounded GA to acquire the results in a short time compared to the mathematical model. On the other hand, increasing the number of machines degraded the performance of the proposed GA.

Słowa kluczowe

EN

identical parallel machines; accurate generic algorithm; robust generic algorithm; immigration; surrogate fitness function; vegetative reproduction

• Wydawca: Production Engineering Committee of the Polish Academy of Sciences ; Polish Association for Production Management
• Czasopismo: Management and Production Engineering Review
• Rocznik: 2023
• Tom: Vol. 14, No. 4
• Strony: 28--40
• Opis fizyczny: Bibliogr. 37 poz., rys., tab., wykr.

Twórcy

autor

Ramadan Saleem Zeyad

• Industrial Engineering Department, School of Engineering Technology, Al Hussein Technical University, Jordan

autor

Almasarwah Najat

• Department of Industrial Systems Engineering, Mutah University, 61710, Alkarak, Jordan

autor

Abdelall Esraa S.

• Industrial Engineering Department, Jordan University of Science and Technology, Jordan

autor

Suer Gursel A.

• Industrial and Systems Engineering, Ohio University, United States

autor

Albashabsheh Nibal T.

• Department of Industrial Engineering, The University of Jordan, Jordan

Bibliografia

• Almasarwah, N., & Süer, G.A. (2021). Consideration of processing time dissimilarity in batch-cyclic scheduling of flowshop cells. International Journal of Production Research, 59(21), 6544-6563.
• Anghinolfi, D., Paolucci, M., & Ronco, R. (2021). A biobjective heuristic approach for green identical parallel machine scheduling. European Journal of Operational Research, 289(2), 416–434.
• Asadpour, M., Hodaei, Z., Azami, M., Kehtari, E., & Vesal, N. (2022). A green model for identical parallel machines scheduling problem considering tardy jobs and job splitting property. Sustainable Operations and Computers, 3, 149-155.
• Balasubramanian, H., Mönch, L., Fowler, J., & Pfund, M. (2004). Genetic algorithm based scheduling of parallel batch machines with incompatible job families to minimize total weighted tardiness. International Journal of Production Research, 42(8), 1621-1638.
• Baykasoğlu, A., & Ozsoydan, F.B. (2018). Dynamic scheduling of parallel heat treatment furnaces: A case study at a manufacturing system. Journal of manufacturing systems, 46, 152-162.
• Biskup, D., Herrmann, J., & Gupta, J.N. (2008). Scheduling identical parallel machines to minimize total tardiness. International Journal of Production Economics, 115(1), 134-142.
• Chang, P.C., Chen, S.H., & Lin, K.L. (2005). Twophase sub population genetic algorithm for parallel machine-scheduling problem. Expert Systems with Applications, 29(3), 705-712.
• Chaudhry, I.A., & Drake, P.R. (2009). Minimizing total tardiness for the machine scheduling and worker assignment problems in identical parallel machines using genetic algorithms. The International Journal of Advanced Manufacturing Technology, 42(5), 581-594.
• Cheng, R., & Gen, M. (1997). Parallel machine scheduling problems using memetic algorithms. Computers & Industrial Engineering, 33(3-4), 761-764.
• Cheng, C.Y., & Huang, L.W. (2017). Minimizing total earliness and tardiness through unrelated parallel machine scheduling using distributed release time control. Journal of Manufacturing Systems, 42, 1-10.
• Cheng, R., Gen, M., & Tozawa, T. (1995). Minmax earliness/tardiness scheduling in identical parallel machine system using genetic algorithms. Computers & Industrial Engineering, 29(1-4), 513-517.
• Cochran, J.K., Horng, S.M., & Fowler, J.W. (2003). A multi-population genetic algorithm to solve multiobjective scheduling problems for parallel machines. Computers & Operations Research, 30(7), 1087-1102.
• Guo, P., Wang, X., & Han, Y. (2010, October). The enhanced genetic algorithms for the optimization design. In: 2010 3rd International Conference on Biomedical Engineering and Informatics (BMEI), IEEE, 7, 2990-2994.
• Ho, J.C., & Chang, Y.L. (1995). Minimizing the number of tardy jobs for m parallel machines. European Journal of Operational Research, 84(2), 343-355.
• Juybari, J.K., Juybari, S.K., & Hasanzadeh, R. (2021). Parallel machines scheduling with time-dependent deterioration, using meta-heuristic algorithms. SN Applied Sciences, 3(3), 1-13.
• Kashan, A.H., Karimi, B., & Jenabi, M. (2008). A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes. Computers & Operations Research, 35(4), 1084-1098.
• Kim, J.G., Song, S., & Jeong, B. (2020). Minimising total tardiness for the identical parallel machine scheduling problem with splitting jobs and sequence-dependent setup times. International Journal of Production Research, 58(6), 1628-1643.
• Kim, J., & Kim, H.J. (2021). Parallel machine scheduling with multiple processing alternatives and sequencedependent setup times. International Journal of Production Research, 59(18), 5438-5453.
• Larranaga, P., Kuijpers, C.M., Murga, R.H., Inza, I., & Dizdarevic, S. (1999). Genetic algorithms for the travelling salesman problem: A review of representations and operators. Artificial Intelligence Review, 13(2), 129-170.
• Mahjoob, M., Fazeli, S.S., Milanlouei, S., Tavassoli, L.S., & Mirmozaffari, M. (2022). A modified adaptive genetic algorithm for multi-product multi-period inventory routing problem. Sustainable Operations and Computers, 3, 1-9.
• Malve, S., & Uzsoy, R. (2007). A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job families. Computers & Operations Research, 34(10), 3016-3028.
• Mensendiek, A., Gupta, J.N., & Herrmann, J. (2015). Scheduling identical parallel machines with fixed delivery dates to minimize total tardiness. European Journal of Operational Research, 243(2), 514-522.
• Min, L., & Cheng, W. (1999). A genetic algorithm for minimizing the makespan in the case of scheduling identical parallel machines. Artificial Intelligence in Engineering, 13(4), 399-403.
• Mir, M.S.S., & Rezaeian, J. (2016). 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.
• Mokotoff, E. (2004). An exact algorithm for the identical parallel machine scheduling problem. European Journal of Operational Research, 152(3), 758-769.
• Muñoz-Villamizar, A., Santos, J., Montoya-Torres, J., & Alvaréz, M. (2019). Improving effectiveness of parallel machine scheduling with earliness and tardiness costs: A case study. International Journal of Industrial Engineering Computations, 10(3), 375-392.
• Najat, A., Yuan, C., Gursel, S., & Tao, Y. (2019). Minimizing the number of tardy jobs on identical parallel machines subject to periodic maintenance. Procedia Manufacturing, 38, 1409-1416.
• Oktafiani, A., & Ardiansyah, M.N. (2023). Scheduling Splitable Jobs on Identical Parallel Machines to Minimize Makespan using Mixed Integer Linear Programming. International Journal of Innovation in Enterprise System, 7(01), 41-54.
• Ramadan, S.Z. (2012). Reducing premature convergence problem in genetic algorithm: application on travel salesman problem. Computer and Information Science, 6(1), 47.
• Schaller, J.E. (2014). Minimizing total tardiness for scheduling identical parallel machines with family setups. Computers & Industrial Engineering, 72, 274-281.
• Shim, S.O., & Kim, Y.D. (2007). Scheduling on parallel identical machines to minimize total tardiness. European Journal of Operational Research, 177(1), 135-146.
• and M. Araki (2008). A branch-and-bound algorithm with Lagrangian relaxation to minimize total tardiness on identical parallel machines. International Journal of Production Economics. 113(5), 446-458.
• Tan, M., Yang, H.L., & Su, Y.X. (2019). Genetic algorithms with greedy strategy for green batch scheduling on non-identical parallel machines. Memetic Computing, 11(4), 439-452.
• Vallada, E., & 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.
• Verma, S., Pant, M., & Snasel, V. (2021). A comprehensive review on NSGA-II for multi-objective combinatorial optimization problems. IEEE Access, 9, 57757-57791.
• Wang, S., Wu, R., Chu, F., & Yu, J. (2020). Identical parallel machine scheduling with assurance of maximum waiting time for an emergency job. Computers & Operations Research, 118, 104918.
• YounesSinaki, R., Sadeghi, A., Mosadegh, H., Almasarwah, N., & Suer, G. (2022). Cellular manufacturing design 1996-2021: a review and introduction to applications of Industry 4.0. International Journal of Production Research, 1-52.