Optimization of makespan for no-wait flowshop scheduling problems using efficient matheuristics

Shih-Wei Lin and Kuo-Ching Ying

Omega, 2016, vol. 64, issue C, 115-125

Abstract: The no-wait flowshop scheduling problem (NWFSP) with makespan minimization is a well-known strongly NP-hard problem with applications in various industries. This study formulates this problem as an asymmetric traveling salesman problem, and proposes two matheuristics to solve it. The performance of each of the proposed matheuristics is compared with those of the best existing algorithms on 21 benchmark instances of Reeves and 120 benchmark instances of Taillard. Computational results show that the presented matheuristics outperform all existing algorithms. In particular, all tested instances of the problem, including a subset of 500-job and 20-machine test instances, are solved to optimality in an acceptable computational time. Moreover, the proposed matheuristics can solve very hard and large NWFSPs to optimality, including the benchmark instances of Vallada et al. and a set of 2000-job and 20-machine problems. Accordingly, this study provides a feasible means of solving the NP-hard NWFSP completely and effectively.

Keywords: Scheduling; No-wait flowshop; Makespan; Matheuristics (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (16)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305048315002480
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:jomega:v:64:y:2016:i:c:p:115-125

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.omega.2015.12.002

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().