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

Ahmadian, MM; Salehipour, A; Cheng, TCE

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

Ahmadian, MM Salehipour, A Cheng, TCE

Permalink

Publisher:: ELSEVIER
Publication Type:: Journal Article
Citation:: European Journal of Operational Research, 2021, 288, (1), pp. 14-29
Issue Date:: 2021-01-01

Closed Access

	Filename	Description	Size
	1-s2.0-S0377221720303519-main.pdf	Published version	1.37 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Ahmadian, MM
dc.contributor.author	Salehipour, A
dc.contributor.author	Cheng, TCE
dc.date.accessioned	2021-11-28T05:08:55Z
dc.date.available	2021-11-28T05:08:55Z
dc.date.issued	2021-01-01
dc.identifier.citation	European Journal of Operational Research, 2021, 288, (1), pp. 14-29
dc.identifier.issn	0377-2217
dc.identifier.issn	1872-6860
dc.identifier.uri	http://hdl.handle.net/10453/151891
dc.description.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.
dc.language	English
dc.publisher	ELSEVIER
dc.relation	http://purl.org/au-research/grants/arc/DE170100234
dc.relation.ispartof	European Journal of Operational Research
dc.relation.isbasedon	10.1016/j.ejor.2020.04.017
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject.classification	Operations Research
dc.title	A meta-heuristic to solve the just-in-time job-shop scheduling problem
dc.type	Journal Article
utslib.citation.volume	288
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Design, Architecture and Building
pubs.organisational-group	/University of Technology Sydney/Faculty of Design, Architecture and Building/School of Built Environment
pubs.organisational-group	/University of Technology Sydney/Faculty of Science
pubs.organisational-group	/University of Technology Sydney/Faculty of Science/School of Mathematical and Physical Sciences
utslib.copyright.status	closed_access	*
dc.date.updated	2021-11-28T05:08:53Z
pubs.issue	1
pubs.publication-status	Published
pubs.volume	288
utslib.citation.issue	1

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.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/151891