Optimal job scheduling to minimize total tardiness by dispatching rules and community evaluation chromosomes
DOI:
https://doi.org/10.31181/dmame622023700Keywords:
Scheduling, sequencing, tardiness, genetic algorithm, dispatching rulesAbstract
In traditional scheduling, job processing times are assumed to be fixed. However, this assumption may not be applicable in many realistic industrial processes. Using the job processing time of real industrial processes instead of a fixed value converts the deterministic model to a stochastic one. This study provides three approaches to solving the problem of stochastic scheduling: stochastic linguistic, stochastic scenarios, and stochastic probabilistic. A combinatorial algorithm, dispatching rules and community evaluation chromosomes (DRCEC) is developed to generate an optimal sequence to minimize the tardiness performance measure in the scheduling problem. Thirty-five datasets of scheduling problems are generated and tested with the model. The DRCEC is compared to the Genetic Algorithm (GA) in terms of total tardiness, the tendency of convergence, execution time, and accuracy. The DRCEC has been discovered to outperform the GA. The computational results show that the DRCEC approach gives the optimal response in 63 per cent of cases and the near-optimal solution in the remaining 37 per cent of cases. Finally, a manufacturing company case study demonstrates DRCEC's acceptable performance.
Downloads
References
Ahmadian, M. M., Salehipour, A., & Cheng, T. C. E. (2021). A meta-heuristic to solve the just-in-time job-shop scheduling problem. European Journal of Operational Research, 288(1), 14–29. https://doi.org/10.1016/j.ejor.2020.04.017
Anjana, V., Sridharan, R., & Ram Kumar, P. N. (2020). Metaheuristics for solving a multi-objective flow shop scheduling problem with sequence-dependent setup times. Journal of Scheduling, 23(1), 49–69. https://doi.org/10.1007/s10951-019-00610-0
Ardakani, A., Fei, J., & Beldar, P. (2020). Truck-to-door sequencing in multi-door cross-docking system with dock repeat truck holding pattern. International Journal of Industrial Engineering Computations, 11(2), 201–220. https://doi.org/10.5267/j.ijiec.2019.10.001
Baker, K. R., & Trietsch, D. (2009). Principles of Sequencing and Scheduling. In Principles of Sequencing and Scheduling. https://doi.org/10.1002/9780470451793
Bank, M., Fatemi Ghomi, S. M. T., Jolai, F., & Behnamian, J. (2012). Two-machine flow shop total tardiness scheduling problem with deteriorating jobs. Applied Mathematical Modelling, 36(11), 5418–5426. https://doi.org/10.1016/j.apm.2011.12.010
Bari, P., & Karande, P. (2021). Application of PROMETHEE-GAIA method to priority sequencing rules in a dynamic job shop for single machine. Materials Today: Proceedings, 46(17), 7258–7264. https://doi.org/10.1016/j.matpr.2020.12.854
Bari, P., Karande, P., & Menezes, J. (2022). Simulation of job sequencing for stochastic scheduling with a genetic algorithm. Operational Research in Engineering Sciences: Theory and Applications, 5(3), 17–39. https://doi.org/10.31181/oresta060722075b
Carlier, J., & Pinson, E. (1989). An algorithm for solving the job-shop problem. Management Science, 35(2), 164–176. https://doi.org/10.1287/mnsc.35.2.164
Cayo, P., & Onal, S. (2020). A shifting bottleneck procedure with multiple objectives in a complex manufacturing environment. Production Engineering, 14(2), 177–190. https://doi.org/10.1007/s11740-019-00947-7
Czibula, O. G., Gu, H., Hwang, F. J., Kovalyov, M. Y., & Zinder, Y. (2016). Bi-criteria sequencing of courses and formation of classes for a bottleneck classroom. Computers and Operations Research, 65, 53–63. https://doi.org/10.1016/j.cor.2015.06.010
Dao, T. K., Pan, T. S., Nguyen, T. T., & Pan, J. S. (2018). Parallel bat algorithm for optimizing makespan in job shop scheduling problems. Journal of Intelligent Manufacturing, 29(2), 451–462. https://doi.org/10.1007/s10845-015-1121-x
Defersha, F. M., & Rooyani, D. (2020). An efficient two-stage genetic algorithm for a flexible job-shop scheduling problem with sequence dependent attached/detached setup, machine release date and lag-time. Computers and Industrial Engineering, 147, 106605. https://doi.org/10.1016/j.cie.2020.106605
French, S. (1982). Sequencing and scheduling: An introduction to the mathematics of the job-shop (First). Wiley.
Garey, M. R., Johnson, D. S., & Sethi, R. (1976). Complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2), 117–129. https://doi.org/10.1287/moor.1.2.117
Gil-Gala, F. J., Đurasević, M., Varela, R., & Jakobović, D. (2023). Ensembles of priority rules to solve one machine scheduling problem in real-time. Information Sciences, 634, 340–358. https://doi.org/10.1016/j.ins.2023.03.114
Gong, G., Deng, Q., Chiong, R., Gong, X., & Huang, H. (2019). An effective memetic algorithm for multi-objective job-shop scheduling. Knowledge-Based Systems, 182, 104840. https://doi.org/10.1016/j.knosys.2019.07.011
Gupta, A., & Chauhan, S. R. (2015). A heuristic algorithm for scheduling in a flow shop environment to minimize makespan. International Journal of Industrial Engineering Computations, 6(2), 173–184. https://doi.org/10.5267/j.ijiec.2014.12.002
Habib Zahmani, M., & Atmani, B. (2021). Multiple dispatching rules allocation in real time using data mining, genetic algorithms, and simulation. Journal of Scheduling, 24(2), 175–196. https://doi.org/10.1007/s10951-020-00664-5
Hasan, S. M. K., Sarker, R., Essam, D., & Cornforth, D. (2009). Memetic algorithms for solving job-shop scheduling problems. Memetic Computing, 1(1), 69–83. https://doi.org/10.1007/s12293-008-0004-5
He, L., Li, W., Chiong, R., Abedi, M., Cao, Y., & Zhang, Y. (2021). Optimising the job-shop scheduling problem using a multi-objective Jaya algorithm. Applied Soft Computing, 111, 107654. https://doi.org/10.1016/j.asoc.2021.107654
Kumar, A., Garg, P., Pant, S., Ram, M., & Kumar, A. (2022). Multi-criteria decision-making techniques for complex decision making problems. Mathematics in Engineering, Science & Aerospace, 13(2), 791–803.
Kumar, K. K., Nagaraju, D., Gayathri, S., & Narayanan, S. (2017). Evaluation and Selection of Best Priority Sequencing Rule in Job Shop Scheduling using Hybrid MCDM Technique. IOP Conference Series: Materials Science and Engineering, 197(1). https://doi.org/10.1088/1757-899X/197/1/012059
Lee, W. C., Yeh, W. C., & Chung, Y. H. (2014). Total tardiness minimization in permutation flowshop with deterioration consideration. Applied Mathematical Modelling, 38(13), 3081–3092. https://doi.org/10.1016/j.apm.2013.11.031
Li, X., Chen, L., Xu, H., & Gupta, J. N. D. (2015). Trajectory scheduling methods for minimizing total tardiness in a flowshop. Operations Research Perspectives, 2, 13–23. https://doi.org/10.1016/j.orp.2014.12.001
M’Hallah, R. (2014). Minimizing total earliness and tardiness on a permutation flow shop using VNS and MIP. In Computers and Industrial Engineering 75(1). Elsevier Ltd. https://doi.org/10.1016/j.cie.2014.06.011
Martínez, K. P., Adulyasak, Y., Jans, R., Morabito, R., & Toso, E. A. V. (2019). An exact optimization approach for an integrated process configuration, lot-sizing, and scheduling problem. Computers and Operations Research, 103, 310–323. https://doi.org/10.1016/j.cor.2018.10.005
Meloni, C., Pacciarelli, D., & Pranzo, M. (2004). A rollout metaheuristic for job shop scheduling problems. Annals of Operations Research, 131(1–4), 215–235. https://doi.org/10.1023/B:ANOR.0000039520.24932.4b
Negi, G., Kumar, A., Pant, S., & Ram, M. (2021). GWO: A review and applications. International Journal of System Assurance Engineering and Management, 12(1), 1–8. https://doi.org/10.1007/s13198-020-00995-8
Pinedo, M. L. (2004). Planning and scheduling in manufacturing and services. Springer Series in Operations Research and Financial Engineering.
Pranzo, M., & Pacciarelli, D. (2016). An iterated greedy metaheuristic for the blocking job shop scheduling problem. Journal of Heuristics, 22(4), 587–611. https://doi.org/10.1007/s10732-014-9279-5
Raman, N., Rachamadugu, R. V., & Talbot, F. B. (1989). Real-time scheduling of an automated manufacturing center. European Journal of Operational Research, 40(2), 222–242. https://doi.org/10.1016/0377-2217(89)90332-9
Sayadi, M. K., Ramezanian, R., & Ghaffari-Nasab, N. (2010). A discrete firefly meta-heuristic with local search for makespan minimization in permutation flow shop scheduling problems. International Journal of Industrial Engineering Computations, 1(1), 1–10. https://doi.org/10.5267/j.ijiec.2010.01.001
Schaller, J., & Valente, J. M. S. (2013). A comparison of metaheuristic procedures to schedule jobs in a permutation flow shop to minimise total earliness and tardiness. International Journal of Production Research, 51(3), 772–779. https://doi.org/10.1080/00207543.2012.663945
Sergienko, I. V., Hulianytskyi, L. F., & Sirenko, S. I. (2009). Classification of applied methods of combinatorial optimization. Cybernetics and Systems Analysis, 45(5), 732–741. https://doi.org/10.1007/s10559-009-9134-0
T’Kindt, V., & Billaut, J.-C. (2005). Multicriteria Scheduling - Theory, Models and Algorithms. Springer-Verlag.
Uniyal, N., Pant, S., Kumar, A., & Pant, P. (2022). Nature-inspired metaheuristic algorithms for optimization. In: Kumar A, Pant S, Ram M, Yadav O (Ed.) Meta-Heuristic Optimization Techniques: Applications in Engineering. Berlin, Boston: De Gruyter, 1–10. https://doi.org/10.1515/9783110716214-001
Valledor, P., Gomez, A., Puente, J., & Fernandez, I. (2022). Solving rescheduling problems in dynamic permutation flow shop environments with multiple objectives using the hybrid dynamic non-dominated sorting genetic II algorithm. Mathematics, 10(14). https://doi.org/10.3390/math10142395
Vinod, V., & Sridharan, R. (2011). Simulation modeling and analysis of due-date assignment methods and scheduling decision rules in a dynamic job shop production system. International Journal of Production Economics, 129(1), 127–146. https://doi.org/10.1016/j.ijpe.2010.08.017
Volgenant, A., & Teerhuis, E. (1999). Improved heuristics for the n-job single-machine weighted tardiness problem. Computers and Operations Research, 26(1), 35–44. https://doi.org/10.1016/S0305-0548(98)00048-3
Yu, J. M., & Lee, D. H. (2018). Solution algorithms to minimise the total family tardiness for job shop scheduling with job families. European Journal of Industrial Engineering, 12(1), 1–23. https://doi.org/10.1504/EJIE.2018.089876
Zammori, F., Braglia, M., & Castellano, D. (2014). Harmony search algorithm for single-machine scheduling problem with planned maintenance. Computers and Industrial Engineering, 76, 333–346. https://doi.org/10.1016/j.cie.2014.08.001
Zhao, Z., Chen, X., An, Y., Li, Y., & Gao, K. (2023). A property-based hybrid genetic algorithm and tabu search for solving order acceptance and scheduling problem with trapezoidal penalty membership function. Expert Systems with Applications, 218. https://doi.org/10.1016/j.eswa.2023.119598
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Decision Making: Applications in Management and Engineering
This work is licensed under a Creative Commons Attribution 4.0 International License.
