Abstract
The resource-constrained project scheduling problem (RCPSP) can be given as follows. A single project consists of a set J = {0,1,…, n, n +1} of activities which have to be processed. Fictitious activities 0 and n + 1 correspond to the “project start” and to the “project end”, respectively. The activities are interrelated by two kinds of constraints. First, precedence constraints force activity j not to be started before all its immediate predecessor activities comprised in the set P j have been finished. Second, performing the activities requires resources with limited capacities. We have k resource types, given by the set K = {1,…,K}. While being processed, activity j requires r j,k units of resource type k ∈ K during every period of its non-preemptable duration p j . Resource type k has a limited capacity of R k at any point in time. The parameters pj,r j,k , and R k are assumed to be deterministic; for the project start and end activities we have pj = 0 and r j,k = 0 for all k ∈ K. The objective of the RCPSP is to find precedence and resource feasible completion times for all activities such that the makespan of the project is minimized. Figure 7:1 gives an example of a project comprising n = 6 activities which have to be scheduled subject to K = 1 renewable resource type with a capacity of 4 units. A feasible schedule with an optimal makespan of 13 periods is represented in Figure 7:2.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alvarez-Valdés, R. and J.M. Tamarit 1989a. Heuristic algorithms for resource-constrained project scheduling: A review and an empirical analysis. Advances in project scheduling. 113–134, Słowiński, R. and J. Węglarz (eds.). Elsevier, Amsterdam.
Alvarez-Valdés, R., and J.M. Tamarit 1989b. Algoritmos heurísticos de-terministas y aleatorios en secuenciacón de proyectos con recursos limitados. Qüestiió 13, 173–191.
Baar, T., Brucker, P., and S. Knust 1997. Tabu-search algorithms for the resource-constrained project scheduling problem. Technical Report, Univer-sität Osnabrück.
Bean, J. 1994. Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing, 6, 2, 154–160.
Bell, C., and J. Han 1991. A new heuristic solution method in resource-constrained project scheduling. Naval Research Logistics 38, 315–331.
Bixby, N., and E. Boyed 1996. Using the CPLEX callable library. CPLEX Optimization Inc., Houston.
Błażewicz, J., Lenstra, J., and A. Rinnooy Kan 1983. Scheduling subject to resource constraints: Classification and complexity. Discrete Applied Mathematics 5, 11–24.
Boctor, F. 1990. Some efficient multi-heuristic procedures for resource-constrained project scheduling. European Journal of Operational Research 49, 3–13.
Bouleimen, K., and H. Lecocq 1998. A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem. Technical Report, Service de Robotique et Automatisation, Université de Liège.
Brucker, P., and S. Knust 1998 Solving large-sized resource-constrained project scheduling problems. Handbook on recent advances in project scheduling. Chapter 18, J. Weglarz (ed.). Kluwer, Dordrecht.
Brucker, P., Knust, S., Schoo, A., and O. Thiele 1998. A branch & bound algorithm for the resource-constrained project scheduling problem. European Journal of Operational Research, forthcoming.
Cho, J.-H., and Y.-D. Kim 1997. A simulated annealing algorithm for resource constrained project scheduling problems. Journal of the Operational Research Society 48, 735–744.
Christofides, N., Alvarez-Valdés, R., and J.M. Tamarit 1987. Project scheduling with resource constraints: A branch and bound approach. European Journal of Operational Research 29, 262–273.
Cooper, D. 1976. Heuristics for scheduling resource-constrained projects: An experimental investigation. Management Science 22, 11, 1186–1194.
Cooper, D. 1977. A note on serial and parallel heuristics for resource-constrained project scheduling. Foundations of Control Engineering 2, 4, 131–133.
Davies, E. 1973. An experimental investigation of resource allocation in muli-tactivity projects. Operational Research Quarterly 24, 587–591.
Davis, E., and J. Patterson 1975. A comparison of heuristic and optimum solutions in resource-constrained project scheduling. Management Science 21, 944–955.
Della Croce, F. 1995. Generalized pairwise interchanges and machine scheduling. European Journal of Operational Research 83, 310–319.
Demeulemeester, E., and W. Herroelen 1997a. New benchmark results for the resource-constrained project scheduling problem. Management Science 43, 11, 1485–1492.
Dorndorf, U., and E. Pesch 1994. Evolution based learning in a job shop scheduling environment. Computers & Operations Research 22, 1, 25–40.
Drexl, A. 1991. Scheduling of project networks by job assignment. Management Science 37, 12, 1590–1602.
Elmaghraby, S. 1977. Activity networks: Project planning and control by network models. Wiley, New York.
Elsayed, E. 1982. Algorithms for project scheduling with resource constraints. International Journal of Production Research 20, 1, 95–103.
Glover, F. 1989a. Tabu search — Part I. ORSA Journal on Computing 1, 190–206.
Glover, F. 1989b. Tabu search — Part II. ORSA Journal on Computing 2, 4–32.
Hartmann, S. 1998. A competitive genetic algorithm for resource-constrained project scheduling. Naval Research Logistics, forthcoming.
+Hartmann, S., and R. Kolisch 1998. An experimental investigation of state-of-the-art heuristics for the resource-constrained project scheduling problem. Technical Report, Universität Kiel, 1998. In preparation.
Herroelen, W., Demeulemeester, E., and B. De Reyck 1998}. A classification scheme for project scheduling}. Handbook on recent advances in project scheduling}. Chapter 1, J. Weglarz} (ed.). Kluwer, Dord
Holland, H. 1975. Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor.
Kelley, J. 1963. The critical-path method: Resources planning and scheduling. 347-365. Industrial scheduling, Muth, J. and G. Thompson (eds.). Prentice-Hall, New Jersey.
Kim, Y.-D. 1995. A backward approach in list scheduling algorithms for multi-machine tardiness problems. Computers & Operations Research 22, 3, 307–319.
Klrkpatrick, S., Gelatt Jr., C. D., And M.P. Vecchi 1983. Optimization by simulated annealing. Science 220, 671–680.
Kohlmorgen, U., Schmeck, H., And K. Haase 1998. Experiences with fine-grained parallel genetic algorithms. Annals of Operations Research, forthcoming.
Kolisch, R. 1995. Project scheduling under resource constraints — Efficient heuristics for several problem classes. Physica, Heidelberg.
Kolisch, R. 1996a. Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation. European Journal of Operational Research 90, 320–333.
Kolisch, R. 1996b. Efficient priority rules for the resource-constrained project scheduling problem. Journal of Operations Management 14, 3, 179–192.
Kolisch, R., and A. Drexl 1996. Adaptive search for solving hard project scheduling problems. Naval Research Logistics 43, 23–40.
Kolisch, R., and R. Padman 1997. An integrated survey of project scheduling. Technical Report 463, Manuskripte aus den Instituten für Betriebswirt-schaftslehre der Universität Kiel.
Kolisch, R., Schwindt, C., and A. Sprecher 1998. Benchmark instances for project scheduling problems. Handbook on recent advances in project scheduling. Chapter 9, J. Weglarz (ed.). Kluwer, Dordrecht.
Kolisch, R., and A. Sprecher 1996. PSPLIB — a project scheduling problem library. European Journal of Operational Research 96, 205–216.
Kolisch, R., Sprecher, A., and A. Drexl 1995. Characterization and generation of a general class of resource-constrained project scheduling problems. Management Science 41, 10, 1693–1703.
Lawrence, S. 1985. Resource constrained project scheduling — A computational comparison of heuristic scheduling techniques. Technical Report, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh.
Lee, J.-K., and Y.-D. Kim 1996. Search heuristics for resource constrained project scheduling. Journal of the Operational Research Society 47, 678–689.
Leon, V., and B. Ramamoorthy 1995. Strength and adaptability of problem-space based neighborhoods for resource-constrained scheduling. OR Spektrum 17, 2/3, 173–182.
Li, R.-Y., and J. Willis 1992. An iterative scheduling technique for resource-constrained project scheduling. European Journal of Operational Research 56, 370–379.
Mausser, H., and S. Lawrence 1998. Exploiting block structure to improve resource-constrained project schedules. Metaheuristics, forthcoming.
Mlngozzi, A., Maniezzo, V., Rlcciardelli, S., And L. Bianco 1998. An exact algorithm for project scheduling with resource constraints based on a new mathematical formulation. Management Science, forthcoming.
Naphade, K., Wu, S., and R. Storer 1997. Problem space search algorithms for resource-constrained project scheduling. Annals of Operations Research 70, 307–326.
Oguz, O., and H. Bala 1994. A comparative study of computational procedures for the resource constrained project scheduling problem. European Journal of Operational Research 72, 406–416.
Özdamar, L., and G. Ulusoy 1994. A local constraint based analysis approach to project scheduling under general resource constraints. European Journal of Operational Research 79, 287–298.
Özdamar, L., and G. Ulusoy 1996a. A note on an iterative forward/backward scheduling technique with reference to a procedure by Li and Willis. European Journal of Operational Research 89, 400–407.
Özdamar, L., and G. Ulusoy 1996b. An iterative local constraint based analysis for solving the resource constrained project scheduling problem. Journal of Operations Management 14, 3, 193–208.
Patterson, J. 1973. Alternate methods of project scheduing with limited resources. Naval Research Logistics Quarterly 23, 767–784.
Patterson, J. 1976. Project scheduling: The effects of problem structure on heuristic performance. Naval Research Logistics Quarterly 20, 95–123.
Pinson, E., Prins, C., and F. Rullier 1994. Using tabu search for solving the resource-constrained project scheduling problem. Proceedings of the 4. International Workshop on Project Management and Scheduling, 102–106, Leuven.
Pollack-Johnson, B. 1995. Hybrid structures and improving forecasting and scheduling in project management. Journal of Operations Management 12, 101–117.
Pritsker, A., Watters, L., and P. Wolfe 1969. Multiproject scheduling with limited resources: A zero-one programming approach. Management Science 16, 93–107.
Sampson, S., and E. Weiss 1993. Local search techniques for the generalized resource constrained project scheduling problem. Naval Research Logistics 40, 665–675.
Schirmer, A., and S. Riesenberg 1997. Parameterized heuristics for project scheduling — Biased random sampling methods. Technical Report 456, Manu-skripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel.
Schirmer, A. 1998. Case-based reasoning and improved adaptive search for project scheduling. Technical Report 472, Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel.
Schutten, J. 1996. List scheduling revisited. Operations Research Letters 18, 167–170.
Shaffer, L., Ritter, J., and W. Meyer 1965. The critical-path method. McGraw Hill, New York.
Sprecher, A. 1996. Solving the RCPSP efficiently at modest memory requirements. Technical Report 425, Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel.
Sprecher, A., Kolisch, R., and A. Drexl 1995. Semi-active, active, and non-delay schedules for the resource-constrained project scheduling problem. European Journal of Operational Research 80, 94–102.
Stinson, J., Davis, E., and B. Khumawala 1978. Multiple resource-constrained scheduling using branch and bound. AIIE Transactions 10, 252–259.
Storer, R., Wu, S., and R. Vaccari 1992. New search spaces for sequencing problems with application to job shop scheduling. Management Science 38, 10, 1495–1509.
Thesen, A. 1976. Heuristic scheduling of activities under resource and precedence restrictions. Management Science 23, 4, 412–422.
Thomas, P., and S. Salhi 1997. An investigation into the relationship of heuristic performance with network-resource characteristics. Journal of the Operational Research Society 48, 1, 34–43.
Ulusoy, G., and L. Özdamar 1989. Heuristic performance and network/resource characteristics in resource-constrained project scheduling. Journal of the Operational Research Society 40, 12, 1145–1152.
Ulusoy, G., and Özdamar, L. 1994. A constraint-based perspective in resource constrained project scheduling. International Journal of Production Research 32, 3, 693–705.
Valls, V., Pérez, M., and M. Quintanilla 1992. Heuristic performance in large resource-constrained projects. Technical Report 92-2, Departament D’Estadistica I Invecigacio Operativa, Universitat de Valencia.
Whitehouse, G., and J. Brown 1979. Genres: An extension of Brooks algorithm for project scheduling with resource constraints. Computers & Industrial Engineering 3, 261–268.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer Science+Business Media New York
About this chapter
Cite this chapter
Kolisch, R., Hartmann, S. (1999). Heuristic Algorithms for the Resource-Constrained Project Scheduling Problem: Classification and Computational Analysis. In: Węglarz, J. (eds) Project Scheduling. International Series in Operations Research & Management Science, vol 14. Springer, Boston, MA. https://doi.org/10.1007/978-1-4615-5533-9_7
Download citation
DOI: https://doi.org/10.1007/978-1-4615-5533-9_7
Publisher Name: Springer, Boston, MA
Print ISBN: 978-1-4613-7529-6
Online ISBN: 978-1-4615-5533-9
eBook Packages: Springer Book Archive