Efficient primal heuristic updates for the blocking job shop problem

Jayanth Krishna Mogali, Laura Barbulescu and Stephen F. Smith

European Journal of Operational Research, 2021, vol. 295, issue 1, 82-101

Abstract: The blocking job shop problem is a variant of the classical job shop problem, where a job continues to block a machine after being serviced, until the downstream machine needed by the job becomes available. Many real world problems have been modeled as blocking job shop problems, and local search heuristics have been shown to produce good quality solutions. Existing literature shows that the computational complexity of these local search algorithms is very high, severely limiting their practical performance. In this work, we present new theoretical results for blocking job shop and show how these results can be used to significantly improve the computational efficiency of existing local search procedures. We empirically evaluate the proposed algorithm updates on existing benchmarks. The results demonstrate that our approach outperforms the current state-of-the-art, by consistently matching or improving previous best known results, usually within a fraction of the time reported for blocking job shop benchmarks. Due to the efficiency in neighborhood computations, our approach scales up to larger size problems than have been considered in prior studies. In particular, for the first time for blocking job shop, we show results for the 100 x 20 instances in Taillard’s benchmark.

Keywords: Heuristics; Blocking job shop problem; Job insertion; Makespan minimization; Job insertion polytope (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/S0377221721001648
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:295:y:2021:i:1:p:82-101

DOI: 10.1016/j.ejor.2021.02.051

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 ().