An improved genetic algorithm is proposed for the Job Shop Scheduling Problem with Minimum Total Weight Tardiness (JSSP/TWT). In the proposed improved genetic algorithm, a decoding method based on the Minimum Local Tardiness (MLT) rule of the job is proposed by using the commonly used chromosome coding method of job numbering, and a chromosome recombination operator based on the decoding of the MLT rule is added to the basic genetic algorithm flow. As a way to enhance the quality of the initialized population, a non-delay scheduling combined with heuristic rules for population initialization. and a PiMX (Precedence in Machine crossover) crossover operator based on the priority of processing on the machine is designed. Comparison experiments of simulation scheduling under different algorithm configurations are conducted for randomly generated larger scale JSSP/TWT. Statistical analysis of the experimental evidence indicates that the genetic algorithm based on the above three improvements exhibits significantly superior performance for JSSP/TWT solving: faster convergence and better scheduling solutions can be obtained.
VepsalainenA.P. and MortonT.E., Priority rules for job shops with weighted tardiness costs, Management Science33(8) (1987), 1035–1047.
2.
TutumluB. and SaraçT., A MIP model and a hybrid genetic algorithm for flexible job-shop scheduling problem with job-splitting, Computers & Operations Research155 (2023), 106222.
3.
BierwirthC. and KuhpfahlJ., Extended GRASP for the job shop scheduling problem with total weighted tardiness objective, European Journal of Operational Research261(3) (2017), 835–848.
4.
KoulamasC., The total tardiness problem: Review and extensions, Operations Research42(6) (1994), 1025–1041.
5.
ZhangC., RaoY. and LiP., An effective hybrid genetic algorithm for the job shop scheduling problem, The International Journal of Advanced Manufacturing Technology39 (2008), 965–974.
6.
MattfeldD.C. and BierwirthC., An efficient genetic algorithm for job shop scheduling with tardiness objectives, European Journal of Operational Research155(3) (2004), 616–630.
7.
KutanogluE., An analysis of heuristics in a dynamic job shop with weighted tardiness objectives, International Journal of Production Research37(1) (1999), 165–187.
8.
CuiH., LiX. and GaoL., An improved multi-population genetic algorithm with a greedy job insertion inter-factory neighborhood structure for distributed heterogeneous hybrid flow shop scheduling problem, Expert Systems with Applications222 (2023), 119805.
9.
WeiH., LiS. and QuanH., Unified multi-objective genetic algorithm for energy efficient job shop scheduling, IEEE Access9 (2021), 54542–54557.
10.
ZhouH., CheungW. and LeungL.C., Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm, European Journal of Operational Research194(3) (2009), 637–649.
11.
EssafiI. and MatiY., A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem, Computers & Operations Research35(8) (2008), 2599–2616.
12.
HollandJ.H., Genetic algorithms and the optimal allocation of trials, SIAM Journal on Computing2(2) (1973), 88–105.
13.
KuhpfahlJ. and BierwirthC., A study on local search neighborhoods for the job shop scheduling problem with total weighted tardiness objective, Computers & Operations Research66 (2016), 44–57.
14.
AsanoM. and OhtaH., A heuristic for job shop scheduling to minimize total weighted tardiness, Computers & Industrial Engineering42(2-4) (2002), 137–147.
15.
GonzálezM.A., González-RodríguezI., VelaC.R., et alAn efficient hybrid evolutionary algorithm for scheduling with setup times and weighted tardiness minimization, Soft Computing16 (2012), 2097–2113.
16.
PinedoM. and SingerM., A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop, Naval Research Logistics (NRL)46(1) (1999), 1–17.
17.
SingerM. and PinedoM., A computational study of branch and bound techniques for minimizing the total weighted tardiness in job shops, IIE Transactions30(2) (1998), 109–118.
18.
ChenN., XieN. and WangY., An elite genetic algorithm for flexible job shop scheduling problem with extracted grey processing time, Applied Soft Computing131 (2022), 109783.
19.
TellacheN.E.H. and KerbacheL., A genetic algorithm for scheduling open shops with conflict graphs to minimize the makespan, Computers & Operations Research156 (2023), 106247.
20.
BruckerP., Scheduling algorithms, Journal-Operational Research Society50 (1999), 774–774.
21.
LiuQ.H., WangN.J., LiJ.,et alResearch on flexible job shop scheduling optimization based on segmented AGV, CMES-Computer Modeling in Engineering & Sciences134 (2023), 2073–2091.
22.
ZhangR. and WuC., A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardinessobjective, Computers & Operations Research38(5) (2011), 854–864.
23.
ZhangR. and ChiongR., Solving the energy-efficient job shop scheduling problem: A multi-objective genetic algorithm with enhanced local search for minimizing the total weighted tardiness and total energy consumption, Journal of Cleaner Production112 (2016), 3361–3375.
24.
ZhangR., SongS. and WuC., A hybrid artificial bee colony algorithm for the job shop scheduling problem, International Journal of Production Economics141(1) (2013), 167–178.
25.
WuS.D., ByeonE.S. and StorerR.H., A graph-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness, Operations Research47(1) (1999), 113–124.
26.
ZhaoS.K. and FangS.L., Operation-based encoding and neighborhood search genetic algorithm for job shop scheduling optimization, Journal of Mechanical Engineering49(16) (2013), 160–169.
27.
LiuZ., ZhaJ., YanJ., ZhangY., ZhaoT., ChengQ. and ChengC., An improved genetic algorithm with an overlapping strategy for solving a combination of order batching and flexible job shop scheduling problem, Engineering Applications of Artificial Intelligence127 (2024), 107321.
28.
LiangZ., ZhongP., LiuM. and ZhangC., A Generic Enhanced Search Framework Based on Genetic Algorithm: Case Study on Job Shop Scheduling Problem, Journal of Intelligent & Fuzzy Systems (2023), 1–17.
29.
YuguangZ., FanY. and FengL., Solving multi-objective fuzzy flexible job shop scheduling problem using MABC algorithm, Journal of Intelligent & Fuzzy Systems36(2) (2019), 1455–1473.
