This paper proposes exact algorithms to generate optimal timing schedules for a given sequence of operations in job shops to minimize the total weighted earliness and tardiness. The algorithms are proposed for two job shop scheduling scenarios, one involving due dates only for the last operation of each job and the other involving due dates for all operations on all the jobs. Computational experiments on benchmark problem instances reveal that, in the case of the scheduling scenario involving due dates only for the last operation of each job, the proposed exact algorithms generate schedules faster than those generated using a popular optimization solver. In the case of the scheduling scenario involving due dates for all operations on all the jobs, the exact algorithms are competitive with the optimization solver in terms of computation time for small and medium size problems.
Keywords: Job shop scheduling, total weighted earliness-tardiness, optimal timing schedule, just-in-time manufacturing
@article{RO_2022__56_4_2621_0,
author = {Girish, Baby Sivanandan and Habibullah and Dileeplal, Jessamma},
title = {Minimizing the total weighted earliness and tardiness for a sequence of operations in job shops},
journal = {RAIRO. Operations Research},
pages = {2621--2649},
year = {2022},
publisher = {EDP-Sciences},
volume = {56},
number = {4},
doi = {10.1051/ro/2022124},
mrnumber = {4469508},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2022124/}
}
TY - JOUR AU - Girish, Baby Sivanandan AU - Habibullah AU - Dileeplal, Jessamma TI - Minimizing the total weighted earliness and tardiness for a sequence of operations in job shops JO - RAIRO. Operations Research PY - 2022 SP - 2621 EP - 2649 VL - 56 IS - 4 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2022124/ DO - 10.1051/ro/2022124 LA - en ID - RO_2022__56_4_2621_0 ER -
%0 Journal Article %A Girish, Baby Sivanandan %A Habibullah %A Dileeplal, Jessamma %T Minimizing the total weighted earliness and tardiness for a sequence of operations in job shops %J RAIRO. Operations Research %D 2022 %P 2621-2649 %V 56 %N 4 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2022124/ %R 10.1051/ro/2022124 %G en %F RO_2022__56_4_2621_0
Girish, Baby Sivanandan; Habibullah; Dileeplal, Jessamma. Minimizing the total weighted earliness and tardiness for a sequence of operations in job shops. RAIRO. Operations Research, Tome 56 (2022) no. 4, pp. 2621-2649. doi: 10.1051/ro/2022124
[1] and , Priority update intervals and anomalies in dynamic ratio type job shop scheduling rules. Manage. Sci. 26 (1980) 1227–1237. | DOI
[2] and , The just-in-time job shop scheduling problem with distinct due-dates for operations. J. Heuristics 27 (2021) 175–204. | DOI
[3] , and , A meta-heuristic to solve the just-in-time job-shop scheduling problem. Eur. J. Oper. Res. 288 (2021) 14–29. | MR | DOI
[4] , and , Genetic Algorithm and Local Search for Just-in-Time Job-Shop Scheduling. In: Proceedings of the 2009 IEEE Congress on Evolutionary Computation (CEC 2009) (2009) 955–961. | DOI
[5] , and , Lagrangian bounds for just-in-time job-shop scheduling. Comput. Oper. Res. 35 (2008) 906–915. | MR | DOI
[6] and , Minimizing the earliness–tardiness costs on a single machine. Comput. Oper. Res. 33 (2006) 3219–3230. | DOI
[7] and , A hybrid approach to scheduling with earliness and tardiness costs. Ann. Oper. Res. 118 (2003) 49–71. | MR | DOI
[8] , and , A state-of-the-art survey of dispatching rules for manufacturing job shop operations. Int. J. Prod. Res. 20 (1982) 27–45. | DOI
[9] and , Optimal idle time insertion in early-tardy parallel machines scheduling with precedence constraints. Prod. Plan. Control. 13 (2002) 133–142. | DOI
[10] , Minimizing the earliness and tardiness cost of a sequence of tasks on a single machine. RAIRO-Oper. Res. 35 (2001) 165–187. | MR | Zbl | Numdam | DOI
[11] and , PERT scheduling with convex cost functions. Theor. Comput. Sci. 292 (2003) 145–164. | MR | DOI
[12] , Number Theory. Ed-Tech Press (2020).
[13] , and , Integrating mixed integer programming and local search: A case on Job-shop scheduling problems. In: Proceedings of the Fifth International Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation Problems (CPAIOR’03) (2003) 65–79.
[14] , and , A combination of evolutionary algorithm, mathematical programming, and a new local search procedure for the just-in-time job-shop scheduling problem. In: Vol. 6073 of Learning and Intelligent Optimization (LION 2010), edited by and , Lecture Notes in Computer Science, Springer-Verlag, Berlin- Heidelberg (2010) 10–24. | DOI
[15] and , Efficient algorithms for machine scheduling problems with earliness and tardiness penalties. Ann. Oper. Res. 159 (2008) 83–95. | MR | DOI
[16] , and , One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties. Math. Oper. Res. 13 (1988) 330–348. | MR | DOI
[17] and , Algorithms for solving production-scheduling problems. Oper. Res. 8 (1960) 487–503. | MR | DOI
[18] , An efficient hybrid particle swarm optimization algorithm in a rolling horizon framework for the aircraft landing problem. Appl. Soft Comput. 44 (2016) 200–221. | DOI
[19] and , An improved earliness–tardiness timing algorithm. Comput. Oper. Res. 34 (2007) 2931–2938. | DOI
[20] IBM software, IBM ILOG CPLEX Optimization Studio CPLEX User’s Manual version 12 Release 8, IBM, 2017. Available online: https://www.ibm.com/support/pages/introduction-concert-technology.
[21] and , Deterministic job-shop scheduling: Past, present and future. Eur. J. Oper. Res. 113 (1999) 390–434. | DOI
[22] , Just-in-time concept in manufacturing and computer systems, In: Just-In-Time Scheduling: Models and Algorithms for Computer and Manufacturing Systems, Vol. 106 of International Series In Operations Research,Springer, Boston (2007) 1–23. | MR
[23] and , Solving production scheduling with earliness/tardiness penalties by constraint programming. J. Intell. Manuf. 22 (2011) 553–562. | DOI
[24] and , A genetic algorithm for job sequencing problems with distinct due dates and general early-tardy penalty weights. Comput. Oper. Res. 22 (1995) 857–869. | DOI
[25] , and , Just-in-time scheduling with constraint programming. In: Proceedings of the Nineteenth International Conference on Automated Planning and Scheduling (ICAPS 2009) (2009) 241–248.
[26] , and , Giffler and Thompson procedure based genetic algorithms for scheduling job shops, In: Computational intelligence of flow shop and job shop scheduling, In Vol. 230 of Studies in Computational Intelligence, Springer-Verlag, Berlin-Heidelberg (2010) 229–259.
[27] and , Optimal timing schedules in earliness-tardiness single machine sequencing. Nav. Res. Logist. 42 (1995) 1109–1114. | DOI
[28] , and , An exact procedure for the resource-constrained weighted earliness–Tardiness project scheduling problem. Ann. Oper. Res. 102 (2001) 179–196. | MR | DOI
[29] and , Tabu search for single machine scheduling with distinct due windows and weighted earliness/tardiness penalties. Eur. J. Oper. Res. 142 (2002) 271–281. | MR | DOI
[30] and , Variable neighbourhood search and mathematical programming for just-in-time job-shop scheduling problem. Math. Probl. Eng. 2014 (2014) 1–9. | MR
[31] , and , An Improved Genetic Algorithm For Just-In-Time Job-Shop Scheduling Problem. Adv. Mat. Res. 472–475 (2012) 2462–2467.
[32] , , and , Job shop scheduling based on earliness and tardiness penalties with due dates and deadlines: an enhanced genetic algorithm. Int. J. Adv. Manuf. Technol. 61 (2012) 657–666. | DOI
[33] , , , and , Review of job shop scheduling research and its new perspectives under industry 4.0. J. Intell. Manuf. 30 (2019) 1809–1830. | DOI
Cité par Sources :
