DOE-based enhanced genetic algorithm for unrelated parallel machine scheduling to minimize earliness/tardiness costs

Subject Areas :

Parsa Kianpour ¹ , Deepak Gupta ² , Krishna Krishnan ³ , Bhaskaran Gopalakrishnan ⁴

1 -
2 -
3 -
4 -

Received: 2022-09-17 Accepted : 2023-08-01 Published : 2024-09-01

Keywords: Heuristic, GA, earliness, Tardiness, DOE, Unrelated Parallel Machine,

Abstract :

This study presents an enhanced genetic algorithm (E-GA) to minimize earliness/tardiness costs in the job shop environment. It considers an unrelated parallel machine scheduling problem with a limit on maximum tardiness levels. This problem is motivated by the experience of one of the authors in a job shop supporting the local aircraft industry that requires strict control on delivery times. Current literature does not consider this critical restriction and unsuccessfully tries to deal with them using higher penalty costs. The proposed method uses the design of experiment (DOE) concept while optimizing the GA operators. Furthermore, it improves the initial solution using a hybrid dispatch rule through a strategic combination of construction and improvement heuristics. The model was applied to a local job shop. The results indicate that E-GA provides a schedule with lower cost and reduced computational time compared to existing dispatch rules in the literature and existing algorithms (OptQuest).

References:

Adan, J. (2022). A hybrid genetic algorithm for parallel machine scheduling with setup times. Journal of Intelligent Manufacturing, 33, 2059–2073.

Allahverdi, A. (2022). A survey of scheduling problems with uncertain interval/bounded processing/setup times. Journal of Project Management, 7, 255-264.

Athmani, M. E., Arbaoui, T., Mimene, Y., & Yalaoui, F. (2022). Efficient heuristics and metaheuristics for the unrelated parallel machine scheduling problem with release dates and setup times. GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference, 177-185.

Campo, E. A., Cano, J. A., Gómez-Montoya, R., Rodríguez-Velásquez, E., & Cortés, P. (2022). Flexible Job Shop Scheduling Problem with Fuzzy Times and Due-Windows: Minimizing Weighted Tardiness and Earliness Using Genetic Algorithms. algorithms, 15(10), 334.

Cao, Z., Lin, C., Zhou, M., Zhou, C., & Sedraoui, K. (2023). Two-Stage Genetic Algorithm for Scheduling Stochastic Unrelated Parallel Machines in a Just-in-Time Manufacturing Context. IEEE Transactions on Automation Science and Engineering, 20(2), 936-949.

Cheng, R., Gen, M., & Tsujimura, Y. (1999). A tutorial survey of job-shop scheduling problems using genetic algorithms, part II: hybrid genetic search strategies. Computers & Industrial Engineering, 36(2), 343-364.

Daniel, C. (1994). Factorial One-Factor-at-a-Time Experiments. The American Statistician, 48(2), 132-135.

De-Alba, H. G., Nucamendi-Guillén, S., & Avalos-Rosales, O. (2022). A mixed integer formulation and an efficient metaheuristic for the unrelated parallel machine scheduling problem: Total tardiness minimization. EURO Journal on Computational Optimization, 10, 100034.

Ɖurasević, M., & Jakobović , D. (2023). Heuristic and metaheuristic methods for the parallel unrelated machines scheduling problem: a survey. Artificial Intelligence Review, 56, 3181–3289.

Eiben, A. E., Hinterding, R., & Michalewicz, Z. (1999). Parameter control in evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 3(2), 124 - 141.

Eiben, A. E., Michalewicz, Z., Schoenauer, M., & Smith, J. E. (2007). Parameter Control in Evolutionary Algorithms. In: Lobo F.G., Lima C.F., Michalewicz Z. (eds) Parameter Setting in Evolutionary Algorithms. Studies in Computational Intelligence. Berlin: Springer.

Fang, W., Zhu, H., & Mei, Y. (2022). Hybrid meta-heuristics for the unrelated parallel machine scheduling problem with setup times. Knowledge-Based Systems, 241, 108193.

Fanjul-Peyro, L. (2020). Models and an exact method for the Unrelated Parallel Machine scheduling problem with setups and resources. Expert Systems with Applications: X, 5, 100022

Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and. Addison-Wesley Longman Publishing Co.

Goupy, J., & Creighton, L. (2007). Introduction to Design of Experiments with JMP Examples, Third Edition. SAS Press.

Holland, J. H. (1975). Adaptation in Natural And Artificial Systems. Ann Arbor, Mich, USA: University of Michigan Press.

Huang, C., Li, Y., & Yao, X. (2019). A Survey of Automatic Parameter Tuning Methods for Metaheuristics. IEEE Transactions on Evolutionary Computation, 24(2), 201-216.

Kianpour, P., Gupta, D., Krishnan, K., & Gopalakrishnan, B. (2021). Automated job shop scheduling with dynamic processing times and due dates using project management and industry 4.0. Journal of Industrial and Production Engineering, 38(7), 485-498.

Kianpour, P., Gupta, D., Krishnan, K., & Gopalakrishnan, B. (2021). Optimising unrelated parallel machine scheduling in job shops with maximum allowable tardiness limit. International Journal of Industrial and Systems Engineering, 37(3), 359-381.

 

Kianpour, P., Gupta, D., Krishnan, K., & Gopalakrishnan, B. (2022). Investigating total earliness and tardiness costs through unrelated parallel machine scheduling in uncertain job shop environment using robust optimisation and design of experiment. International Journal of Operational Research, 45(4), 511-539.

Kramer, O. (2017). Genetic Algorithm Essentials. Cham: Springer.

Lenstra, J. K., & Kan, A. H. (1979). Computational Complexity of Discrete Optimization Problems. Annals of Discrete Mathematics, 4, 121-140.

Li, G., Li, M., Azarm, S., Al-Hashimi, S., Al-Ameri, T., & Al-Qasas, N. (2009). Improving multi-objective genetic algorithms with adaptive design of experiments and online metamodeling. Structural and Multidisciplinary Optimization, 37(5), 447-461.

Moser, M., Musliu, N., Schaerf, A., & Winter, F. (2022). Exact and metaheuristic approaches for unrelated parallel machine scheduling. Journal of Scheduling, 25, 507-534.

Nasr, S. M., El-Shorbagy, M. A., El-Desoky, I. M., Hendawy, Z. M., & Mousa, A. A. (2015). Hybrid Genetic Algorithm for Constrained Nonlinear Optimization Problems. British Journal of Mathematics & Computer Science, 7(6), 466-480.

Nobile, M. S., Cazzaniga, P., Besozzi, D., Colombo, R., Mauri, G., & Pasi, G. (2018). Fuzzy Self-Tuning PSO: A settings-free algorithm for global optimization. Swarm and Evolutionary Computation, 39, 70-85.

Pavón, R., Díaz, F., Laza, R., & Luzón, V. (2009). Automatic parameter tuning with a Bayesian case-based reasoning system. A case of study. Expert Systems with Applications, 36(2), 3407-3420.

Pezzella, F., Morganti, G., & Ciaschetti, G. (2008). A genetic algorithm for the Flexible Job-shop Scheduling Problem. Computers & Operations Research, 35(10), 3202-3212.

Rohaninejad, M., Sahraeian, R., & Nouri, B. V. (2017). Minimising the total cost of tardiness and overtime in a resumable capacitated job shop scheduling problem by using an efficient hybrid algorithm. International Journal of Industrial and Systems Engineering, 26(3), 318 - 343.

Rolim, G. A., Nagano, M. S., & de Athayde Prata, B. (2023). Formulations and an adaptive large neighborhood search for just-in-time scheduling of unrelated parallel machines with a common due window. Computers & Operations Research, 153, 106159.

Safarzadeh, H., & Niaki, S. T. (2023). Unrelated parallel machine scheduling with machine processing cost. International Journal of Industrial Engineering Computations, 14(1), 33-48.

Shahzad, A., & Mebarki, N. (2016). Learning Dispatching Rules for Scheduling: A Synergistic View Comprising Decision Trees, Tabu Search and Simulation. Computers, 5(1), 3.

Sharma, P., & Jain, A. (2016). A review on job shop scheduling with setup times. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 230(3), 517-533.

Soares, L. C., & Carvalho, M. A. (2022). Application of a hybrid evolutionary algorithm to resource-constrained parallel machine scheduling with setup times. Computers & Operations Research, 139, 105637.

Yaghtin, M., & Javid, Y. (2023). Genetic algorithm based on greedy strategy in unrelated parallel-machine scheduling problem using fuzzy approach with periodic maintenance and process constraints. International Journal of Supply and Operations Management.

Zhu, X., & Wilhelm, W. E. (2007). Scheduling and lot sizing with sequence-dependent setup: A literature review. IIE Transactions, 38(11), 987-1007.

Zimmermann, J., & Neyer, F. J. (2013). Do We Become a Different Person When Hitting the Road?Personality Development of Sojourners. Journal of Personality and Social Psychology, 105(3), 515-530.

Zitzler, E., Deb, K., & Thiele, L. (2000). Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, 8(2), 173-195.