An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem

被引:153
作者
Congram, RK [1 ]
Potts, CN
van de Velde, SL
机构
[1] Univ Southampton, Fac Math Studies, Southampton SO17 1BJ, Hants, England
[2] Erasmus Univ, Rotterdam Sch Management, Dept Informat & Decis Sci, NL-3000 DR Rotterdam, Netherlands
关键词
production scheduling; single machine; sequencing; analysis of algorithms; dynamic programming;
D O I
10.1287/ijoc.14.1.52.7712
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
This paper introduces a new neighborhood search technique, called dynasearch, that uses dynamic programming to search an exponential size neighborhood in polynomial time. While traditional local search algorithms make a single move at each iteration, dynasearch allows a series of moves to be performed. The aim is for the lookahead capabilities of dynasearch to prevent the search from being attracted to poor local optima. We evaluate dynasearch by applying it to the problem of scheduling jobs on a single machine to minimize the total weighted tardiness of the jobs. Dynasearch is more effective than traditional first-improve or best-improve descent in our computational tests. Furthermore, this superiority is much greater for starting solutions close to previous local minima. Computational results also show that an iterated dynasearch algorithm in which descents are performed a few random moves away from previous local minima is superior to other known local search procedures for the total weighted tardiness scheduling problem.
引用
收藏
页码:52 / 67
页数:16
相关论文
共 35 条
[1]  
AHUJA R, 1999, SURVEY VERY LARGE SC
[2]  
[Anonymous], 1997, LOCAL SEARCH COMBINA
[3]  
[Anonymous], 1996, META HEURISTICS THEO, DOI DOI 10.1007/978-1-4613-1361-8_14
[4]  
[Anonymous], 99885 U BONN FORSCH
[5]   Linear time dynamic-programming algorithms for new classes of restricted TSPs: A computational study [J].
Balas, E ;
Simonetti, N .
INFORMS JOURNAL ON COMPUTING, 2001, 13 (01) :56-75
[6]   New classes of efficiently solvable generalized Traveling Salesman Problems [J].
Balas, E .
ANNALS OF OPERATIONS RESEARCH, 1999, 86 (0) :529-558
[7]  
BAUM E, 1986, P AIP C, V151, P53
[8]  
Baum E.B., 1986, ITERATED DESCENT BET
[9]  
BAXTER J, 1981, J OPER RES SOC, V32, P815, DOI 10.1057/jors.1981.159
[10]   OR-LIBRARY - DISTRIBUTING TEST PROBLEMS BY ELECTRONIC MAIL [J].
BEASLEY, JE .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1990, 41 (11) :1069-1072