Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/34383
Title: Iterated local search for single-machine scheduling with sequence-dependent setup times to minimize total weighted tardiness
Authors: Xu, H
L?, Z
Cheng, TCE 
Keywords: Block Move
Iterated Local Search
Sequence dependent setup
Single-machine scheduling
Total weighted tardiness
Issue Date: 2014
Publisher: Springer
Source: Journal of scheduling, 2014, v. 17, no. 3, p. 271-287 How to cite?
Journal: Journal of scheduling 
Abstract: We present an Iterated Local Search (ILS) algorithm for solving the single-machine scheduling problem with sequence-dependent setup times to minimize the total weighted tardiness. The proposed ILS algorithm exhibits several distinguishing features, including a new neighborhood structure called Block Move and a fast incremental evaluation technique, for evaluating neighborhood solutions. Applying the proposed algorithm to solve 120 public benchmark instances widely used in the literature, we achieve highly competitive results compared with a recently proposed exact algorithm and five sets of best solutions of state-of-the-art metaheuristic algorithms in the literature. Specifically, ILS obtains the optimal solutions for 113 instances within a reasonable time, and it outperforms the previous best-known results obtained by metaheuristic algorithms for 34 instances and matches the best results for 82 instances. In addition, ILS is able to obtain the optimal solutions for the remaining seven instances under a relaxed time limit, and its computational efficiency is comparable with the state-of-the-art exact algorithm by Tanaka and Araki (Comput Oper Res 40:344-352, 2013). Finally, on analyzing some important features that affect the performance of ILS, we ascertain the significance of the proposed Block Move neighborhood and the fast incremental evaluation technique.
URI: http://hdl.handle.net/10397/34383
ISSN: 1094-6136
EISSN: 1099-1425
DOI: 10.1007/s10951-013-0351-z
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

17
Last Week
1
Last month
1
Citations as of Apr 7, 2018

WEB OF SCIENCETM
Citations

14
Last Week
0
Last month
0
Citations as of Apr 14, 2018

Page view(s)

80
Last Week
0
Last month
Citations as of Apr 16, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.