A hybrid genetic algorithm for the resource-constrained project scheduling problem

被引:160
作者
Valls, Vicente
Ballestin, Francisco
Quintanilla, Sacramento
机构
[1] Univ Valencia, Fac Econ & Empresariales, Dept Econ Financiera & Matemat, Valencia 46071, Spain
[2] Univ Navarra, Fac Econ & Empresariales, Dept Estadist & Invest Operat, Pamplona 31006, Spain
[3] Univ Valencia, Fac Matemat, Dept Estadist & Invest Operat, E-46100 Valencia, Spain
关键词
project management; scheduling; heuristics;
D O I
10.1016/j.ejor.2006.12.033
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
In this paper we propose a Hybrid Genetic Algorithm (HGA) for the Resource-Con strained Project Scheduling Problem (RCPSP). HGA introduces several changes in the GA paradigm: a crossover operator specific for the RCPSP; a local improvement operator that is applied to all generated schedules; a new way to select the parents to be combined; and a two-phase strategy by which the second phase re-starts the evolution from a neighbour's population of the best schedule found in the first phase. The computational results show that HGA is a fast and high quality algorithm that outperforms all state-of-the-art algorithms for the RCPSP known by the authors of this paper for the instance sets j60 and j120. And that it is competitive with other state-of-the-art heuristics for the instance set j30. (C) 2007 Elsevier B.V. All rights reserved.
引用
收藏
页码:495 / 508
页数:14
相关论文
共 42 条
[1]   A robust genetic algorithm for resource allocation in project scheduling [J].
Alcaraz, J ;
Maroto, C .
ANNALS OF OPERATIONS RESEARCH, 2001, 102 (1-4) :83-109
[2]   Insertion techniques for static and dynamic resource-constrained project scheduling [J].
Artigues, C ;
Michelon, P ;
Reusser, S .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2003, 149 (02) :249-267
[3]   SCHEDULING SUBJECT TO RESOURCE CONSTRAINTS - CLASSIFICATION AND COMPLEXITY [J].
BLAZEWICZ, J ;
LENSTRA, JK ;
KAN, AHGR .
DISCRETE APPLIED MATHEMATICS, 1983, 5 (01) :11-24
[4]   A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version [J].
Bouleimen, K ;
Lecocq, H .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2003, 149 (02) :268-281
[5]   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
[6]   A hybrid scatter search/electromagnetism meta-heuristic for project scheduling [J].
Debels, D ;
De Reyck, B ;
Leus, R ;
Vanhoucke, M .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2006, 169 (02) :638-653
[7]  
Demeulemeester E, 2002, INT SERIES OPERATION, V49
[8]   A branch-and-bound algorithm for the resource-constrained project scheduling problem [J].
Dorndorf, U ;
Pesch, E ;
Phan-Huy, T .
MATHEMATICAL METHODS OF OPERATIONS RESEARCH, 2000, 52 (03) :413-439
[9]   SCHEDULING OF PROJECT NETWORKS BY JOB ASSIGNMENT [J].
DREXL, A .
MANAGEMENT SCIENCE, 1991, 37 (12) :1590-1602
[10]   Solving the resource-constrained project problem by a variable neighbourhood scheduling search [J].
Fleszar, K ;
Hindi, KS .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2004, 155 (02) :402-413