Iterated Local Search with Path Relinking for Solving Parallel Machines Scheduling Problem with Resource-Assignable Sequence Dependent Setup Times

被引:0
作者
Kampke, Edmar Hell [1 ]
Claudio Arroyo, Jose Elias [1 ]
Santos, Andre Gustavo [1 ]
机构
[1] Univ Fed Vicosa, Dept Informat, BR-36570000 Vicosa, MG, Brazil
来源
EVOLUTIONARY COMPUTATION IN COMBINATORIAL OPTIMIZATION, PROCEEDINGS | 2010年 / 6022卷
关键词
Metaheuristics; Parallel Machine Scheduling; Setup Time; ILS; Path Relinking;
D O I
暂无
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
This paper addresses the unrelated parallel machine problem with machine and job sequence dependent setup. In this problem, the amount of the setup time does not only depend on the machine and job sequence, but also on a number of resources assigned, which can vary between a minimum and a maximum. The goal is to find a schedule that minimizes the linear combination of the total resources assigned and the total completion time. The problem is NP-hard in the strong sense. The NP-hardness of the problem motivates us to develop a new Iterated Local Search (ILS) heuristic to obtain near-optimal solutions. The heuristic uses an intensification strategy based on the Path Relinking technique which generates new solutions by exploring trajectories that connect high-quality solutions. Computational tests are carried out on a set of benchmark instances and the results obtained by the proposed ILS improve the best known results from the literature by a significant margin.
引用
收藏
页码:107 / 118
页数:12
相关论文
共 14 条
[1]   GRASP with path relinking for three-index assignment [J].
Aiex, RM ;
Resende, MGC ;
Pardalos, PM ;
Toraldo, G .
INFORMS JOURNAL ON COMPUTING, 2005, 17 (02) :224-247
[2]  
DOLGUI A, 2009, P 13 IFAC S INF CONT, P832
[3]  
Fowler JW, 2003, INT J IND ENG-THEORY, V10, P232
[4]  
Glover F, 1997, OPERAT RES COMP SCI, P1
[5]   TEXTILE PRODUCTION SYSTEMS - A SUCCESSION OF NONIDENTICAL PARALLEL PROCESSOR SHOPS [J].
GUINET, A .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1991, 42 (08) :655-671
[6]   Scheduling jobs on parallel machines: a restricted tabu search approach [J].
Kim, CO ;
Shin, HJ .
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2003, 22 (3-4) :278-287
[7]   Unrelated parallel machine scheduling with setup times using simulated annealing [J].
Kim, DW ;
Kim, KH ;
Jang, W ;
Chen, FF .
ROBOTICS AND COMPUTER-INTEGRATED MANUFACTURING, 2002, 18 (3-4) :223-231
[8]  
Lourenço HR, 2003, INT SER OPER RES MAN, V57, P321
[9]  
Pinedo M., 1995, Scheduling: Theory, Algorithms, and Systems
[10]   Heuristics for the unrelated parallel machine scheduling problem with setup times [J].
Rabadi, G ;
Moraga, RJ ;
Al-Salem, A .
JOURNAL OF INTELLIGENT MANUFACTURING, 2006, 17 (01) :85-97