The high performing backtracking algorithm and heuristic for the sequence-dependent setup times flowshop problem with total weighted tardiness. Issue 9 (1st September 2016)

• Record Type: Journal Article
• Authors: Zheng, Jun-Xi; Zhang, Ping; Li, Fang; Du, Guang-Long
• Is Part Of: Engineering optimization. Volume 48:Issue 9(2016)
• Page Start: 1571
• Page End: 1592
• Publication Date: 2016-09-01
• Subjects: flowshop scheduling -- heuristic -- backtracking algorithm -- setup times -- total weighted tardiness; Engineering design -- Periodicals; Mathematical optimization -- Periodicals; 620.0042
• DOI: 10.1080/0305215X.2015.1124870
• Languages: English
• ISSNs: 0305-215X

Abstract

Abstract : Although the sequence-dependent setup times flowshop problem with the total weighted tardiness minimization objective exists widely in industry, work on the problem has been scant in the existing literature. To the authors' best knowledge, the NEH EWDD heuristic and the Iterated Greedy (IG) algorithm with descent local search have been regarded as the high performing heuristic and the state-of-the-art algorithm for the problem, which are both based on insertion search. In this article firstly, an efficient backtracking algorithm and a novel heuristic (HPIS) are presented for insertion search. Accordingly, two heuristics are introduced, one is NEH EWDD with HPIS for insertion search, and the other is the combination of NEH EWDD and both the two methods. Furthermore, the authors improve the IG algorithm with the proposed methods. Finally, experimental results show that both the proposed heuristics and the improved IG (IG*) significantly outperform the original ones.