Local search for nonpreemptive multi-mode resource-constrained project scheduling

被引:14
作者
Kolisch, R
Drexl, A
机构
关键词
D O I
暂无
中图分类号
T [工业技术];
学科分类号
08 ;
摘要
This paper addresses a general class of nonpreemptive resource-constrained project scheduling problems in which activity durations are discrete functions of committed renewable and nonrenewable resources. We provide a well known 0-1 problem formulation and stress the importance of the model by giving applications within production and operations management. Furthermore, we prove that the feasibility problem is already NP-complete. Solution procedures proposed so far have the following shortcomings: exact methods can solve only very small instances to optimality; heuristic solution approaches fail to generate feasible solutions when problems become highly resource-constrained. Hence, we propose a new local search method that first tries to rnd a feasible solution and secondly performs a single-neighborhood search on the set of feasible mode assignments. To evaluate the new procedure we perform a rigorous computational study on two benchmark sets. The experiment includes a comparison of our procedure with other heuristics.
引用
收藏
页码:987 / 999
页数:13
相关论文
共 31 条
[1]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[2]   SCHEDULING SUBJECT TO RESOURCE CONSTRAINTS - CLASSIFICATION AND COMPLEXITY [J].
BLAZEWICZ, J ;
LENSTRA, JK ;
KAN, AHGR .
DISCRETE APPLIED MATHEMATICS, 1983, 5 (01) :11-24
[3]   SCHEDULING WITH RESOURCE-MANAGEMENT IN MANUFACTURING SYSTEMS [J].
BLAZEWICZ, J ;
FINKE, G .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1994, 76 (01) :1-14
[4]   HEURISTICS FOR SCHEDULING PROJECTS WITH RESOURCE RESTRICTIONS AND SEVERAL RESOURCE-DURATION MODES [J].
BOCTOR, FF .
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 1993, 31 (11) :2547-2558
[5]   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
[6]   NONPREEMPTIVE MULTIMODE RESOURCE-CONSTRAINED PROJECT SCHEDULING [J].
DREXL, A ;
GRUENEWALD, J .
IIE TRANSACTIONS, 1993, 25 (05) :74-81
[7]   A note on ''hierarchical models for multi-project planning and scheduling'' [J].
Hartmann, S ;
Sprecher, A .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 94 (02) :377-383
[8]  
Kolisch R, 1996, NAV RES LOG, V43, P23, DOI 10.1002/(SICI)1520-6750(199602)43:1<23::AID-NAV2>3.0.CO
[9]  
2-P
[10]   Characterization and generation of a general class of resource-constrained project scheduling problems [J].
Kolisch, R ;
Sprecher, A ;
Drexl, A .
MANAGEMENT SCIENCE, 1995, 41 (10) :1693-1703