An exact algorithm for project scheduling with multiple modes

被引：132

作者：

Sprecher A. ^{[1
]}

Hartmann S. ^{[1
]}

Drexl A. ^{[1
]}

机构：

[1] Institut für Betriebswirtschaftslehre, Christian-Albrechts-Universität zu Kiel, D-24118 Kiel

来源：

Operations-Research-Spektrum | 1997年 / 19卷 / 3期

关键词：

Branch-and-bound; Computational results; Discrete resource-resource and time-resource tradeoffs; Dominance rules; Mode and delay alternatives; Project management/scheduling;

D O I：

10.1007/BF01545587

中图分类号：

学科分类号：

摘要：

We consider an extension of the classical resource-constrained project scheduling problem (RCPSP), which covers discrete resource-resource and time-resource tradeoffs. As a result a project scheduler is permitted to identify several alternatives or modes of accomplishment for each activity of the project. The solution procedure to be presented is a considerable generalization of the branch-and-bound algorithm proposed by Demeulemeester and Herroelen, which is currently the most powerful method for optimally solving the RCPSP. More precisely, we extend their concept of delay alternatives by introducing mode alternatives. The basic enumeration scheme is enhanced by dominance rules which increase the performance of the algorithm. We then report on our computational results obtained from the comparison with the most rapid procedure reported in the literature. © Springer-Verlag 1997.

引用

页码：195 / 203

页数：8

共 23 条

[1]

Bartusch M., Mohring R.H., Radermacher F.J., Scheduling project networks with resource constraints and time windows, Ann Oper Res, 16, pp. 201-240, (1988)

[2]

Boctor F.F., Heuristics for scheduling projects with resource restrictions and several resource-duration modes, Int J Prod Res, 31, pp. 2547-2558, (1993)

[3]

Brucker P., Schoo A., Thiele O., A Branch-and-bound Algorithm for the Resource-constrained Project Scheduling Problem, 178, (1996)

[4]

Christofides N., Alvarez-Valdes R., Tamarit J.M., Project scheduling with resource constraints: A branch and bound approach, Eur J Oper Res, 29, pp. 262-273, (1987)

[5]

Demeulemeester E., Optimal Algorithms for Various Classes of Multiple Resource-constrained Project Scheduling Problems, (1992)

[6]

Demeulemeester E., Herroelen W., A branch-and-bound procedure for the multiple resource-constrained project scheduling problem, Manag Sci, 38, pp. 1803-1818, (1992)

[7]

Drexl A., Scheduling of project networks by job assignment, Manag Sci, 37, pp. 1590-1602, (1991)

[8]

French S., Sequencing and Scheduling: An Introduction to the Mathematics of the Job-shop, (1982)

[9]

Garey M.R., Johnson D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness, (1979)

[10]

Hartmann S., Sprecher A., A note on "Hierarchical models for multi-project planning and scheduling, Europ J Oper Res, 94, pp. 377-383, (1996)

← 1 2 3 →