×

Resource-constrained project scheduling: A survey of recent developments. (English) Zbl 1040.90525

Summary: We review recent advances in dealing with the resource-constrained project scheduling problem using an efficient depth-first branch-and-bound procedure, elaborating on the branching scheme, bounding calculations and dominance rules, and discuss the potential of using truncated branch-and-bound. We derive conclusions from the research on optimal solution procedures for the basic problem and subsequently illustrate extensions to a rich and realistic variety of related problems involving activity preemption, the use of ready times and deadlines, variable resource requirements and availabilities, generalized precedence relations, time/cost, time/resource and resource/resource trade-offs and non-regular objective functions.

MSC:

90B35 Deterministic scheduling theory in operations research
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Software:

PSPLIB
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Muth, J.F.; Thompson, G.L., Industrial scheduling, (1963), Prentice Hall Englewood Cliffs, N.J
[2] Conway, R.W.; Maxwell, W.L.; Miller, L.W., Theory of scheduling, (1967), Addison-Wesley Publishing Company · Zbl 1058.90500
[3] Ashour, S., Sequencing theory, (1972), Springer-Verlag Berlin · Zbl 0241.90029
[4] Baker, K.R., Introduction to sequencing and scheduling, (1974), John Wiley New York
[5] Rinnooy Kan, A.H.G., Machine scheduling problems—classification, complexity and computations, (1976), M. Nijhoff The Netherlands · Zbl 0366.90092
[6] French, S., Sequencing and scheduling—an introduction to the mathematics of the job shop, (1982), John Wiley New York · Zbl 0479.90037
[7] Bellmann, R.; Esogbue, A.O.; Nabeshima, I., Mathematical aspects of scheduling and applications, (1982), Pergamon Press Oxford, U.K · Zbl 0498.90018
[8] Herroelen, W., Operationele produktieplanning, (1991), Acco Leuven
[9] Blazewicz, J.; Ecker, K.; Schmidt, G.; Weglarz, J., Scheduling in computer and manufacturing systems, (1993), Springer-Verlag Berlin
[10] Morton, Th.E.; Pentico, D.W., Heuristic scheduling systems—with applications to production systems and project management, (1993), Wiley Interscience New York
[11] Tanaev, V.S.; Gordon, V.S.; Shafransky, Y.M., Scheduling theory: single-stage systems, (1994), Kluwer Academic Publishers Dordrecht · Zbl 0827.90079
[12] Tanaev, V.S.; Sotskov, Y.N.; Strusevich, V.A., Scheduling theory: multi-stage systems, (1994), Kluwer Academic Publishers Dordrecht · Zbl 0925.90224
[13] Brucker, P., Scheduling algorithms, (1995), Springer-Verlag Berlin · Zbl 0839.90059
[14] Pinedo, M., Scheduling—theory, algorithms and systems, (1995), Prentice-Hall Englewood Cliffs, New Jersey · Zbl 1145.90393
[15] Gargeya, V.B.; Deane, R.H., Scheduling research in multiple resource constrained job shops: A review and critique, International journal of production research, 34, 2077-2097, (1996) · Zbl 0946.90539
[16] Blazewicz, J.; Lenstra, J.K.; Rinnooy Kan, A.H.G., Scheduling projects to resource constraints: classification and complexity, Discrete applied mathematics, 5, 11-24, (1983) · Zbl 0516.68037
[17] Bowman, E.H., The schedule-sequencing problem, Operations research, 7, 621-624, (1959) · Zbl 1255.90059
[18] Brand, J.D.; Meyer, W.L.; Shaffer, L.R., The resource scheduling problem in construction, ()
[19] Wiest, J.D., Some properties of schedules for large projects with limited resources, Operations research, 12, 395-418, (1964)
[20] Moodie, C.L.; Mandeville, D.E., Project resource balancing by assembly line balancing techniques, Journal of industrial engineering, 17, 377-383, (1966)
[21] Elmaghraby, S.E., The sequencing of n jobs on m parallel processors, (1967), North Carolina State University at Raleigh Raleigh, U.S.A, Unpublished paper
[22] Pritsker, A.B.; Watters, L.J.; Wolfe, P.M., Multiproject scheduling with limited resources: A zero-one programming approach, Management science, 16, 93-108, (1969)
[23] Patterson, J.H.; Huber, W.D., A horizon-varying zero-one approach to project scheduling, Management science, 20, 990-998, (1974) · Zbl 0303.90026
[24] Patterson, J.H.; Roth, G., Scheduling a project under multiple resource constraints: A zero-one programming approach, AIIE transactions, 8, 449-456, (1976)
[25] Deckro, R.F.; Winkofsky, E.P.; Hebert, J.E.; Gagnon, R., A decomposition approach to multi-project scheduling, European journal of operational research, 51, 110-118, (1991) · Zbl 0732.90039
[26] Icmeli, O.; Rom, W.O., Solving the resource-constrained project scheduling problem with optimization subroutine library, Computers and operations research, 23, 801-817, (1996) · Zbl 0854.90079
[27] Carruthers, J.A.; Battersby, A., Advances in critical path methods, Operational research quarterly, 17, 359-380, (1966)
[28] Petroviç, R., Optimisation of resource allocation in project planning, Operations research, 16, 559-586, (1968)
[29] Johnson, T.J.R., An algorithm for the resource constrained project scheduling problem, ()
[30] Balas, E., Project scheduling with resource constraints, (), 187-200
[31] Schrage, L., Solving resource-constrained network problems by implicit enumeration—nonpreemptive case, Operations research, 10, 263-278, (1970) · Zbl 0197.46005
[32] Davis, E.W.; Heidorn, G.E., An algorithm for optimal project scheduling under multiple resource constraints, Management science, 27, B803-B816, (1971) · Zbl 0224.90030
[33] Stinson, J.P.; Davis, E.W.; Khumawala, B.M., Multiple resource-constrained scheduling using branch-and-bound, AIIE transactions, 10, 252-259, (1978)
[34] Talbot, B.; Patterson, J.H., An efficient integer programming algorithm with network cuts for solving resource-constrained scheduling problems, Management science, 24, 1163-1174, (1978) · Zbl 0395.90036
[35] Radermacher, F.J., Scheduling of project networks, Annals of operations research, 4, 227-252, (1985) · Zbl 0693.90046
[36] Christofides, N.; Alvarez-Valdes, R.; Tamarit, J.M., Project scheduling with resource constraints: A branch and bound approach, European journal of operational research, 29, 262-273, (1987) · Zbl 0614.90056
[37] Bartusch, M.; Möhring, R.H.; Radermacher, F.J., Scheduling project networks with resource constraints and time windows, Annals of operations research, 16, 201-240, (1988) · Zbl 0693.90047
[38] Bell, C.A.; Park, K., Solving resource-constrained project scheduling problems by A^{∗} search, Naval research logistics, 37, 61-84, (1990) · Zbl 0684.90054
[39] Carlier, J.; Latapie, B., Une méthode arborescente pour LES problèmes cumulatifs, R.a.i.r.o., 25, 311-340, (1991) · Zbl 0733.90036
[40] Demeulemeester, E.; Herroelen, W., A branch-and-bound procedure for the multiple resource-constrained project scheduling problem, Management science, 38, 1803-1818, (1992) · Zbl 0761.90059
[41] Demeulemeester, E.; Herroelen, W., New benchmark results for the resource-constrained project scheduling problem, Management science, 43, 1485-1492, (1997) · Zbl 0914.90160
[42] Carlier, J.; Neron, E., A new branch and bound method for solving the resource constrained project scheduling problem, (), 61-65
[43] Mingozzi, A.; Maniezzo, V.; Ricciardelli, S.; Bianco, L., An exact algorithm for project scheduling with resource constraints based on a new mathematical formulation, Management science, (1998), to appear · Zbl 1004.90036
[44] Brucker, P.; Schoo, A.; Thiele, O., A branch-and-bound algorithm for the resource-constrained project scheduling problem, European journal of operational research, (1998), to appear · Zbl 0970.90030
[45] Davis, E.W., Resource allocation in project network models—A survey, Journal of industrial engineering, 17, 177-188, (1966)
[46] Davis, E.W., Project scheduling under resource constraints: historical review and categorization of procedures, AIIE transactions, 5, 297-313, (1973)
[47] Herroelen, W., Resource-constrained project scheduling—the state of the art, Operational research quarterly, 23, 261-275, (1972) · Zbl 0238.90031
[48] Patterson, J.H., A comparison of exact procedures for solving the multiple constrained resource project scheduling problem, Management science, 30, 854-867, (1984)
[49] Icmeli, O.; Erengüç, S.S.; Zappe, J.C., Project scheduling problems: A survey, International journal of production and operations management, 13, 80-91, (1993)
[50] Elmaghraby, S.E., Activity nets: A guided tour through some recent developments, European journal of operational research, 82, 383-408, (1995) · Zbl 0910.90175
[51] Herroelen, W.; Demeulemeester, E., Recent advances in branch-and-bound procedures for resource-constrained project scheduling problems, (), 259-276
[52] Özdamar, L.; Ulusoy, G., A survey on the resource-constrained project scheduling problem, IIE transactions, 27, 574-586, (1995)
[53] Kolisch, R.; Sprecher, A.; Drexl, A., Characterization and generation of a general class of resource-constrained project scheduling problems, Management science, 41, 1693-1703, (1995) · Zbl 0870.90070
[54] Demeulemeester, E.; Herroelen, W.; Simpson, W.P.; Baroum, S.; Patterson, J.H.; Yang, K.-K., On a paper by christofides et al. for solving the multiple-resource constrained single project scheduling problem, European journal of operational research, 76, 218-228, (1994) · Zbl 0811.90045
[55] Sprecher, A.; Drexl, A., Solving multi-mode resource-constrained project scheduling problems by a simple, general and powerful sequencing algorithm, European journal of operational research, (1998), to appear · Zbl 0943.90042
[56] Kolisch, R.; Sprecher, A., PSPLIB—A project scheduling problem library, European journal of operational research, 96, 205-216, (1997) · Zbl 0947.90587
[57] De Reyck, B.; Herroelen, W., On the use of the complexity index as a measure of complexity in activity networks, European journal of operational research, 91, 347-366, (1996) · Zbl 0924.90092
[58] Pascoe, T.L., Allocation of resources—CPM, Revue française de recherche opérationelle, 38, 31-38, (1966)
[59] Davis, E.W., Project network summary measures and constrained resource scheduling, IIE transactions, 7, 132-142, (1975)
[60] Talbot, F.B., Resource-constrained project scheduling with time-resource trade-offs: the nonpreemptive case, Management science, 28, 1197-1210, (1982) · Zbl 0493.90042
[61] Kurtulus, I.S.; Narula, S.C., Multi-project scheduling: analysis of project performance, IIE transactions, 17, 58-66, (1985)
[62] Alvarez-Valdes, R.; Tamarit, J.M., Heuristic algorithms for resource-constrained project scheduling: A review and empirical analysis, () · Zbl 0614.90056
[63] Elmaghraby, S.E.; Herroelen, W., On the measurement of complexity in activity networks, European journal of operational research, 5, 223-234, (1980) · Zbl 0444.90049
[64] Bein, W.W.; Kamburowski, J.; Stallmann, M.F.M., Optimal reduction of two-terminal directed acyclic graphs, SIAM journal on computing, 21, 1112-1129, (1992) · Zbl 0768.68119
[65] De Reyck, B., On the use of the restrictiveness as a measure of complexity for resource-constrained project scheduling, ()
[66] De Reyck, B.; Herroelen, W., Assembly line balancing by resource-constrained project scheduling techniques—A critical appraisal, Foundations of computing and decision sciences, 99, 143-167, (1997) · Zbl 0899.68007
[67] Mastor, A.A., An experimental and comparative evaluation of production line balancing techniques, Management science, 16, 728-746, (1970) · Zbl 0217.26903
[68] Kao, E.P.C.; Queyranne, M., On dynamic programming methods for assembly line balancing, Operations research, 30, 375-390, (1992) · Zbl 0481.90043
[69] Dar-El, E.M., MALB—A heuristic technique for balancing large single-model assembly lines, AIIE transactions, 5, 343-356, (1973)
[70] Cooper, D.F., Heuristics for scheduling resource-constrained projects: an experimental comparison, Management science, 22, 1186-1194, (1976) · Zbl 0326.90029
[71] Patterson, J.H., Project scheduling: the effects of problem structure on heuristic performance, Naval research logistics, 23, 95-123, (1976) · Zbl 0325.90027
[72] Demeulemeester, E., Optimal algorithms for various classes of multiple resource-constrained project scheduling problems, ()
[73] Slowinski, R., Two approaches to problems of resource allocation among project activities—A comparative study, Journal of the operational research society, 31, 711-723, (1980) · Zbl 0439.90042
[74] Weglarz, J., Project scheduling with continuously-divisible doubly-constrained resources, Management science, 27, 1040-1053, (1981) · Zbl 0467.90033
[75] Kaplan, L., Resource-constrained project scheduling with preemption of jobs, ()
[76] Kaplan, L., Resource-constrained project scheduling with setup times, (1991), Department of Management, University of Tenessee Knoxville, Unpublished paper
[77] Demeulemeester, E.; Herroelen, W., An efficient optimal solution procedure for the preemptive resource-constrained project scheduling problem, European journal of operational research, 90, 334-348, (1996) · Zbl 0916.90149
[78] Simpson, W.P.; Patterson, J.H., A multiple-tree search procedure for the resource-constrained project scheduling problem, European journal of operational research, 89, 525-542, (1996) · Zbl 0915.90153
[79] Kerbosch, J.A.G.M.; Schell, H.J., Network planning by the extended METRA potential method, ()
[80] Zahn, J., Heuristics for scheduling resource-constrained projects in MPM networks, European journal of operational research, 76, 192-205, (1994) · Zbl 0806.90070
[81] Moder, J.J.; Phillips, C.R.; Davis, E.W., Project management with CPM, PERT and precedence diagramming, (1983), Van Nostrand Reinhold
[82] Brinkmann, K.; Neumann, K., Heuristic procedures for resource-constrained project scheduling with minimal and maximal time lags: the minimum project duration and resource levelling problem, ()
[83] Neumann, K.; Zahn, J., Heuristics for the minimum project-duration problem with minimal and maximal time lags under fixed resource constraints, Journal of intelligent manufacturing, 6, 145-154, (1995)
[84] Neumann, K.; Schwindt, C., Projects with minimal and maximal time lags: construction of activity-on-node networks and applications, ()
[85] Schwindt, C., Generation of resource-constrained project scheduling problems with minimal and maximal time lags, ()
[86] Franck, B.; Neumann, K., Priority-rule methods for the resource-constrained project scheduling problem with minimal and maximal time lags—an empirical analysis, (), 88-91
[87] Schwindt, C.; Neumann, K., A new branch-and-bound-based heuristic for resource-constrained project scheduling with minimal and maximal time lags, (), 212-215
[88] Wikum, E.D.; Donna, C.L.; Nemhauser, G.L., One-machine generalized precedence constrained scheduling problems, Operations research letters, 16, 87-99, (1994) · Zbl 0823.90066
[89] Elmaghraby, S.E.; Kamburowski, J., The analysis of activity networks under generalized precedence relations, Management science, 38, 1245-1263, (1992) · Zbl 0758.90044
[90] Demeulemeester, E.; Herroelen, W., A branch-and-bound procedure for the generalized resource-constrained project scheduling problem, Operations research, 45, 201-212, (1997) · Zbl 0890.90098
[91] Möhring, R. H., Private communication, 1996.
[92] De Reyck, B.; Herroelen, W., A branch-and-bound procedure for the resource-constrained project scheduling problem with generalized precedence constraints, European journal of operational research, (1997), to appear
[93] Herroelen, W.; Van Dommelen, P.; Demeulemeester, E., Project network models with discounted cash flows—A guided tour through recent developments, European journal of operational research, 100, 97-121, (1997) · Zbl 0947.90583
[94] Russell, A.H., Cash flows in networks, Management science, 16, 357-373, (1970) · Zbl 0187.18201
[95] Grinold, R.C., The payment scheduling problem, Naval research logistics quarterly, 19, 123-136, (1972) · Zbl 0252.90034
[96] Elmaghraby, S.E.; Herroelen, W., The scheduling of activities to maximize the net present value of projects, European journal of operational research, 49, 35-49, (1990) · Zbl 1403.90670
[97] Herroelen, W.; Gallens, E., Computational experience with an optimal procedure for the scheduling of activities to maximize the net present value of projects, European journal of operational research, 65, 274-277, (1993) · Zbl 0775.90232
[98] Demeulemeester, E.; Herroelen, W.; Van Dommelen, P., An optimal recursive search procedure for the deterministic unconstrained MAX-NPV scheduling problem, ()
[99] De Reyck, B.; Herroelen, W., An optimal procedure for the unconstrained MAX-NPV project scheduling problem with generalized precedence relations, () · Zbl 1054.90548
[100] Baroum, S.M., An exact solution procedure for maximizing the net present value of resource-constrained projects, (1992), Indiana University, Unpublished Ph.D. Dissertation
[101] Icmeli, O.; Erenguç, S., A branch-and-bound procedure for the resource-constrained project scheduling problem with discounted cash flows, Management science, 42, 1395-1408, (1996) · Zbl 0880.90074
[102] Yang, K.K.; Talbot, F.B.; Patterson, J.H., Scheduling a project to maximize its net present value: an integer programming approach, European journal of operational research, 64, 188-198, (1992) · Zbl 0769.90053
[103] De Reyck, B.; Herroelen, W., An optimal procedure for the resource-constrained project scheduling problem with discounted cash flows and generalized precedence relations, Computers and operations research, 25, 1-17, (1998) · Zbl 0909.90175
[104] Herroelen, W., Een probleem Van “resource allocation”: het toewijzen Van netwerkactiviteiten aan ingenieurs, ()
[105] Elmaghraby, S.E., Activity networks: project planning and control by network models, (1977), John Wiley and Sons New York · Zbl 0385.90076
[106] Demeulemeester, E.; De Reyck, B.; Herroelen, W., The discrete time/resource trade-off problem in project networks—A branch-and-bound approach, () · Zbl 1140.90439
[107] De Reyck, B.; Demeulemeester, E.; Herroelen, W., Local search methods for the discrete time/resource trade-off problem in project networks, () · Zbl 0948.90065
[108] Sprecher, A.; Hartmann, S.; Drexl, A., An exact algorithm for project scheduling with multiple modes, OR spektrum, 19, 195-203, (1997) · Zbl 0885.90059
[109] Speranza, M.G.; Vercellis, C., Hierarchical models for multi-project planning and scheduling, European journal of operational research, 64, 312-325, (1993) · Zbl 0779.90046
[110] Sprecher, A., Resource-constrained project scheduling: exact methods for the multi-mode case, () · Zbl 0809.90084
[111] Hartmann, S.; Sprecher, A., A note on “hierarchical models for multi-project planning and scheduling”, European journal of operational research, 94, 377-383, (1996) · Zbl 0953.90518
[112] Patterson, J.H.; Slowinski, R.; Talbot, F.B.; Weglarz, J., An algorithm for a general class of precedence and resource constrained scheduling problems, () · Zbl 1403.90678
[113] Patterson, J.H.; Slowinski, R.; Talbot, F.B.; Weglarz, J., Computational experience with a backtracking algorithm for solving a general class of precedence and resource-constrained scheduling problems, European journal of operational research, 49, 68-79, (1990) · Zbl 1403.90678
[114] Böttcher, J.; Drexl, A.; Kolisch, R., A branch-and-bound procedure for project scheduling with partially renewable resource constraints, (), 48-51
[115] Drexl, A., Local search methods for project scheduling under partially renewable resource constraints, ()
[116] Schirmer, A.; Drexl, A., Partially renewable resources—A generalization of resource-constrained project scheduling, ()
[117] Salewski, F.; Lieberam-Schmidt, S., Greedy look ahead methods for project scheduling under resource and mode identity constraints, (), 207-211
[118] Salewski, F., Tabu search algorithms for project scheduling under resource and mode identity constraints, ()
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.