Fast local neighborhood search algorithm for the no-wait flow shop scheduling with total flow time minimization

Xuemei Qi, Hongtao Wang, Haihong Zhu, Ji Zhang, Fulong Chen and Jie Yang

International Journal of Production Research, 2016, vol. 54, issue 16, 4957-4972

Abstract: A fast local neighbourhood search (FLNS) algorithm is proposed in this paper to minimise the total flow time in the no-wait flow shop scheduling problem, which is known to be NP-hard for more than two machines. In this work, an unscheduled job sequence is constructed firstly according to the total processing time and standard deviation of jobs on the machines. This job sequence is undergone an initial optimisation using basic neighbourhood search algorithm. Then, an innovative local neighbourhood search scheme is designed to search for the partial neighbourhood in each iterative processing and calculate the neighbourhood solution with an objective increment method. This not only improves the solution quality significantly, but also speeds up the convergence of the solution of the algorithm. Moreover, a probabilistic acceptance criterion is adopted to help our method escape from the local optima. Based on Taillard’s benchmarks, the experimental results show that the proposed FLNS algorithm is superior to major existing algorithms (IHA, IBH LS , GA-VNS and DHS) in terms of both quality and robustness, and can provide best upper bounds. The in-depth statistical analysis demonstrates that the promising performance of our proposed algorithm is also statistically significant.

Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2016.1150615 (text/html)
Access to full text is restricted to subscribers.

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:taf:tprsxx:v:54:y:2016:i:16:p:4957-4972

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TPRS20

DOI: 10.1080/00207543.2016.1150615

Access Statistics for this article

International Journal of Production Research is currently edited by Professor A. Dolgui

More articles in International Journal of Production Research from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().