Optimal job scheduling to minimize total tardiness by dispatching rules and community evaluation chromosomes

Prasad Bari; Prasad Karande

doi:10.31181/dmame622023700

Authors

Prasad Bari Department of Mechanical Engineering, Veermata Jijabai Technological Institute, Mumbai, India https://orcid.org/0000-0002-6257-8196
Prasad Karande Department of Mechanical Engineering, Veermata Jijabai Technological Institute, Mumbai, India

DOI:

https://doi.org/10.31181/dmame622023700

Keywords:

Scheduling, sequencing, tardiness, genetic algorithm, dispatching rules

Abstract

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

Download data is not yet available.

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