Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 288, Issue 1, Pages 14-29Publisher
ELSEVIER
DOI: 10.1016/j.ejor.2020.04.017
Keywords
Scheduling; Just-in-time; Weighted earliness-tardiness; Heuristic; Relaxation neighbourhood; Relax-and-solve
Funding
- UTS International Research Scholarship (IRS)
- UTS Faculty of Science Scholarship
- Australian Research Council - Australian Government [DE170100234]
- The Hong Kong Polytechnic University under the Fung Yiu King -Wing Hang Bank Endowed Professorship in Business Administration
- Australian Research Council [DE170100234] Funding Source: Australian Research Council
Ask authors/readers for more resources
JIT-JSS is a variant of the job-shop scheduling problem with distinct due-dates for each operation. A VNS algorithm is developed to solve JIT-JSS by decomposing the problem, obtaining optimal operation sequences, and generating schedules. The algorithm shows efficacy by obtaining new best solutions for a significant number of instances.
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 in-stances with 20 jobs. The computational results demonstrate the efficacy of the proposed VNS algorithm. (C) 2020 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available