Accelerated methods for total tardiness minimisation in no-wait flowshops

Jianya Ding, Shiji Song, Rui Zhang, Jatinder N.D. Gupta and Cheng Wu

International Journal of Production Research, 2015, vol. 53, issue 4, 1002-1018

Abstract: For the minimisation of total tardiness in no-wait flowshops, objective incremental properties are investigated in this paper to speed up the evaluation of candidate solutions. To explore the properties, we introduce a new concept of sensitive jobs and identify through experiments that the proportion of such jobs is very small. Instead of evaluating the tardiness of each job, we focus on the evaluation of sensitive jobs which will help to reduce the computational efforts. With these properties, the time complexity of the NEH-insertion procedure is reduced from O(n2)$ O(n^2) $ to approximately O(n)$ O(n) $ in average. Then, an accelerated NEH algorithm and an accelerated iterated greedy algorithm are designed for the problem. Since the NEH-insertion procedure constitutes the main computational burden for both algorithms, these algorithms will benefit directly from the speedup. Numerical computations show that the accelerated algorithms perform 10–40 times faster than the original algorithms on the middle- and large-sized instances. In addition, comparisons show that the proposed algorithms perform more efficiently and effectively than the existing heuristics and meta-heuristics.

Date: 2015
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2014.932935 (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:53:y:2015:i:4:p:1002-1018

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

DOI: 10.1080/00207543.2014.932935

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