A hybrid metaheuristic for the resource-constrained project scheduling problem

被引:69
作者
Tseng, Lin-Yu
Chen, Shih-Chieh
机构
[1] Natl Chung Hsing Univ, Dept Comp Sci, Taichung 402, Taiwan
[2] Natl Chung Hsing Univ, Dept Appl Math, Taichung 402, Taiwan
关键词
project scheduling; ant colony optimization; genetic algorithm; local search; metaheuristics;
D O I
10.1016/j.ejor.2005.06.014
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
This study presents a hybrid metaheuristic ANGEL for the resource-constrained project scheduling problem (RCPSP). ANGEL combines ant colony optimization (ACO), genetic algorithm (GA) and local search strategy. The procedures of ANGEL are as follows. First, ACO searches the solution space and generates activity lists to provide the initial population for GA. Next, GA is executed and the pheromone set in ACO is updated when GA obtains a better solution. When GA terminates, ACO searches again by using a new pheromone set. ACO and GA search alternately and cooperatively in the solution space. This study also proposes an efficient local search procedure which is applied to yield a better solution when ACO or GA obtains a solution. A final search is applied upon the termination of ACO and GA. The experimental results of ANGEL on the standard sets of the project instances show that ANGEL is an effective method for solving the RCPSP. (c) 2005 Elsevier B.V. All rights reserved.
引用
收藏
页码:707 / 721
页数:15
相关论文
共 43 条
[11]   Resource-constrained project scheduling: Notation, classification, models, and methods [J].
Brucker, P ;
Drexl, A ;
Mohring, R ;
Neumann, K ;
Pesch, E .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1999, 112 (01) :3-41
[12]   A simulated annealing algorithm for resource constrained project scheduling problems [J].
Cho, JH ;
Kim, YD .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1997, 48 (07) :736-744
[13]   A BRANCH-AND-BOUND PROCEDURE FOR THE MULTIPLE RESOURCE-CONSTRAINED PROJECT SCHEDULING PROBLEM [J].
DEMEULEMEESTER, E ;
HERROELEN, W .
MANAGEMENT SCIENCE, 1992, 38 (12) :1803-1818
[14]   New benchmark results for the resource - Constrained project scheduling problem [J].
Demeulemeester, EL ;
Herroelen, WS .
MANAGEMENT SCIENCE, 1997, 43 (11) :1485-1492
[15]  
Dorigo M., 1997, IEEE Transactions on Evolutionary Computation, V1, P53, DOI 10.1109/4235.585892
[16]  
Dorigo M., 1992, THESIS DIPARTIMENTO
[17]   A self-adapting genetic algorithm for project scheduling under resource constraints [J].
Hartmann, S .
NAVAL RESEARCH LOGISTICS, 2002, 49 (05) :433-448
[18]  
Hartmann S, 1998, NAV RES LOG, V45, P733, DOI 10.1002/(SICI)1520-6750(199810)45:7<733::AID-NAV5>3.0.CO
[19]  
2-C
[20]   Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem [J].
Hartmann, S ;
Kolisch, R .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 127 (02) :394-407