TY - JOUR
T1 - A meta-heuristic to solve the just-in-time job-shop scheduling problem
AU - Ahmadian, Mohammad Mahdi
AU - Salehipour, Amir
AU - Cheng, T. C.E.
N1 - Funding Information:
We thank the editor and three anonymous referees for their many helpful comments on earlier versions of our paper. Mohammad Mahdi Ahmadian is the recipient of the UTS International Research Scholarship (IRS) and UTS Faculty of Science Scholarship. Amir Salehipour is the recipient of an Australian Research Council Discovery Early Career Researcher Award (project number DE170100234) funded by the Australian Government. T.C.E. Cheng was supported in part by The Hong Kong Polytechnic University under the Fung Yiu King - Wing Hang Bank Endowed Professorship in Business Administration.
Funding Information:
We thank the editor and three anonymous referees for their many helpful comments on earlier versions of our paper. Mohammad Mahdi Ahmadian is the recipient of the UTS International Research Scholarship (IRS) and UTS Faculty of Science Scholarship. Amir Salehipour is the recipient of an Australian Research Council Discovery Early Career Researcher Award (project number DE170100234 ) funded by the Australian Government. T.C.E. Cheng was supported in part by The Hong Kong Polytechnic University under the Fung Yiu King - Wing Hang Bank Endowed Professorship in Business Administration.
Publisher Copyright:
© 2020 Elsevier B.V.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2021/1/1
Y1 - 2021/1/1
N2 - Just-in-time job-shop scheduling (JIT-JSS) is a variant of the job-shop scheduling problem, in which each operation has a distinct due-date and any deviation of the operation completion time from its due-date incurs an earliness or tardiness penalty. We develop a variable neighbourhood search (VNS) algorithm to solve JIT-JSS. The algorithm operates by decomposing JIT-JSS into smaller problems, obtaining optimal or near-optimal sequences of performing the operations for those smaller problems, and generating a schedule, i.e., determining the completion time of the operations, for JIT-JSS. The algorithm uses several neighbourhood structures, including the new relaxation neighbourhoods developed in this study, to obtain a quality sequence. The relaxation neighbourhoods partially destruct (relax) the sequence and then re-construct (sequence) certain operations. Differing from the classical neighbourhoods, in which manipulations are performed either randomly or myopically, the moves in the new neighbourhoods are made with reference to other operations, so their impacts on the whole sequence are well considered. By solving a set of 72 benchmark instances, ranging from 10 to 20 jobs and 20 to 200 operations, and comparing the outcomes of the proposed algorithm with the state-of-the-art solution methods in the literature, we obtain new best solutions for nearly 57% of the instances, including new best solutions for 80% of the instances with 20 jobs. The computational results demonstrate the efficacy of the proposed VNS algorithm.
AB - Just-in-time job-shop scheduling (JIT-JSS) is a variant of the job-shop scheduling problem, in which each operation has a distinct due-date and any deviation of the operation completion time from its due-date incurs an earliness or tardiness penalty. We develop a variable neighbourhood search (VNS) algorithm to solve JIT-JSS. The algorithm operates by decomposing JIT-JSS into smaller problems, obtaining optimal or near-optimal sequences of performing the operations for those smaller problems, and generating a schedule, i.e., determining the completion time of the operations, for JIT-JSS. The algorithm uses several neighbourhood structures, including the new relaxation neighbourhoods developed in this study, to obtain a quality sequence. The relaxation neighbourhoods partially destruct (relax) the sequence and then re-construct (sequence) certain operations. Differing from the classical neighbourhoods, in which manipulations are performed either randomly or myopically, the moves in the new neighbourhoods are made with reference to other operations, so their impacts on the whole sequence are well considered. By solving a set of 72 benchmark instances, ranging from 10 to 20 jobs and 20 to 200 operations, and comparing the outcomes of the proposed algorithm with the state-of-the-art solution methods in the literature, we obtain new best solutions for nearly 57% of the instances, including new best solutions for 80% of the instances with 20 jobs. The computational results demonstrate the efficacy of the proposed VNS algorithm.
KW - Heuristic
KW - Just-in-time
KW - Relax-and-solve
KW - Relaxation neighbourhood
KW - Scheduling
KW - Weighted earliness-tardiness
UR - http://www.scopus.com/inward/record.url?scp=85089250322&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2020.04.017
DO - 10.1016/j.ejor.2020.04.017
M3 - Journal article
AN - SCOPUS:85089250322
SN - 0377-2217
VL - 288
SP - 14
EP - 29
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 1
ER -