An efficient optimal solution procedure for the preemptive resource-constrained project scheduling problem. (English) Zbl 0916.90149

Demeulemeester, Erik L.; Herroelen, Willy S.

Eur. J. Oper. Res. 90, No. 2, 334-348 (1996).

Summary: A branch-and-bound procedure is described for scheduling project activities subject to precedence and resource constraints, where activities can be preempted at any discrete time instant and where the objective is to minimize the project duration. The procedure is based on a depth-first solution strategy in which nodes in the solution tree represent resource and precedence feasible partial schedules. Branches emanating from a parent node correspond to exhaustive and minimal combinations of activities, the delay of which resolves resource conflicts at each parent node. A precedence based lower bound and several dominance rules are introduced in order to restrict the growth of the solutions tree. The solution procedure has been programmed in the language C and extensive computational experience is reported.

MSC:

90B35

Deterministic scheduling theory in operations research

Keywords:

project management; preemption; branch-and-bound; precedence and resource constraints

References:

[1]	Davis, E. W., Project scheduling under resource constraints: Historical review and categorisation of procedures, AIIE Transactions, 5/4, 297-313 (1973)
[2]	Davis, E. W.; Heidorn, G. E., An algorithm for optimal project scheduling under multiple resource constraints, Management Science, 17/12, 803-816 (1971) · Zbl 0224.90030
[3]	Demeulemeester, E. L., Optimal algorithms for various classes of multiple resource-constrained project scheduling problems (1992), Katholieke Universiteit Leuven: Katholieke Universiteit Leuven Belgium, Unpublished Phd Dissertation
[4]	Demeulemeester, E. L.; Herroelen, W. S., A branch-and-bound procedure for the multiple resource-constrained project scheduling problem, Management Science, 38/12, 1803-1818 (1992) · Zbl 0761.90059
[5]	Demeulemeester, E. L.; Herroelen, W. S., A branch-and-bound procedure for the generalized resource-constrained project scheduling problem, (Research report nr 9206 (1992), Departement Toegepaste Economische Wetenschappen, Katholieke Universiteit Leuven: Departement Toegepaste Economische Wetenschappen, Katholieke Universiteit Leuven Belgium) · Zbl 0905.00086
[6]	French, S., Sequencing and Scheduling: An Introduction to the Mathematics of the Job-shop (1982), Ellis Horwood · Zbl 0479.90037
[7]	Herroelen, W. S., Resource-constrained project scheduling — The state of the art, Operational Research Quarterly, 23, 261-275 (1972) · Zbl 0238.90031
[8]	Herroelen, W. S.; Demeulemeester, E. L., Recent advances in branch-and-bound procedures for resource-constrained project scheduling problems, (Paper presented at the Summer School on Scheduling Theory and Its Applications. Paper presented at the Summer School on Scheduling Theory and Its Applications, Château de Bonas, France (September 28-October 2, 1992)) · Zbl 0905.00086
[9]	Kaplan, L. A., Resource-constrained project scheduling with preemption of jobs (1988), University of Michigan, Unpublished Phd Dissertation
[10]	Kaplan, L. A., Resource-constrained project scheduling with setup times (1991), Department of Management, University of Tenessee: Department of Management, University of Tenessee Knoxville, Unpublished paper
[11]	Patterson, J. H., A comparison of exact procedures for solving the multiple constrained resource project scheduling problem, Management Science, 30/7, 854-867 (1984)
[12]	Patterson, J. H.; Huber, W. D., A horizon-varying zero-one approach to project scheduling, Management Science, 20/6, 990-998 (1974) · Zbl 0303.90026
[13]	Patterson, J. H.; Roth, G. W., Scheduling a project under multiple resource constraints: A zero-one programming approach, AIIE Transactions, 8/4, 449-456 (1976)
[14]	Pritsker, A. B.; Watters, L. J.; Wolfe, P. M., Multiproject scheduling with limited resources: A zero-one programming approach, Management Science, 16/1, 93-108 (1969)
[15]	Simpson, W. P., A parallel exact solution procedure for the resource-constrained project scheduling problem (1991), Indiana University, Unpublished Phd Dissertation
[16]	Slowinski, R., Two approaches to problems of resource allocation among project activities — A comparative study, Journal of the Operational Research Society, 31/8, 711-723 (1980) · Zbl 0439.90042
[17]	Weglarz, J., Project scheduling with continuously-divisible, doubly constrained resources, Management Science, 27/9, 1040-1053 (1981) · Zbl 0467.90033
[18]	Wiest, J. D., Some properties of schedules for large projects with limited resources, Operations Research, 12/3, 395-418 (1964)