A meta-heuristic to solve the just-in-time job-shop scheduling problem

Mohammad Mahdi Ahmadian, Amir Salehipour and T.C.E. Cheng

European Journal of Operational Research, 2021, vol. 288, issue 1, 14-29

Abstract: 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.

Keywords: Scheduling; Just-in-time; Weighted earliness-tardiness; Heuristic; Relaxation neighbourhood; Relax-and-solve (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720303519
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:288:y:2021:i:1:p:14-29

DOI: 10.1016/j.ejor.2020.04.017

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().