The authors consider the problem of minimizing the duration of a project under fixed resource constraints. For the case that there are only minimal time lags between the start of successive activities and that therefore the project can be described by an acyclic network, a large number of exact and heuristic algorithms can be found in the literature. In this paper, the authors permit both minimal and maximal time lags between activities. The project can then be modelled by an activityon-node network containing cycles. Efficient priority-rule heuristics are presented for solving the resource-constrained project-scheduling problem. Computational results are discussed for projects containing up to 1000 activities and several resources.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alvarez-Valdés, R. and Tamarit, J. M. (1989) Heurisitic algorithms for resource-constrained project scheduling: a review and an empirical analysis, in Advances in Project Scheduling, Slowinski, R. and Weglarz, J. (eds), Elsevier, Amsterdam, pp. 113–134.
Bartusch, M. (1983) Optimierung von Netzplänen mit Anordnungsbeziehungen bei knappen Betriebsmitteln, Ph. D. Thesis, RWTH Aachen, Germany.
Bartusch, M., Möhring, R. H. and Radermacher, F. J. (1988) Scheduling project networks with resource constraints and time windows. Annals of Operations Research, 16, 201–240.
Christofides, N., Alvarez-Valdés, R. and Tamarit, J. M. (1987) Project scheduling with resource constraints: a branch and bound approach. European Journal of Operational Research, 29, 262–273.
Davis, E. W. (1975) Project network summary measures constrained-resource scheduling. AIIE Transactions, 7, 132–142.
Davis, E. W. and Patterson, J. H. (1975) A comparison of heuristic and optimum solutions in resource-constrained project scheduling. Management Science, 21, 944–955.
Demeulemeester, E. and Herroelen, W. (1992) A branch-and-bound procedure for the multiple resource-constrained project scheduling problem. Management Science, 38, 1803–1818.
Elmaghraby, S. E. and Kamburowski, J. (1992) The analysis of activity networks under generalized precedence relations. Management Science, 38, 1245–1263.
Elsayed, E. A. (1982) Algorithms for project scheduling with resource constraints. International Journal of Production Research, 20, 95–103.
Even, S. (1979) Graph Algorithms, Pitman, London.
Gallo, G. and Pallottino, S. (1986) Shortest path methods: a unifying approach. Mathematical Programming Study, 26, 38–64.
Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G. and Shmoys, D. B. (eds) (1985) The Traveling Salesman Problem, John Wiley, New York.
Neumann, K. and Morlock, M. (1993) Operations Research, Carl Hanser, München.
Patterson, J. H. (1984) A comparison of exact approaches for solving the multiple constrained resource project scheduling problem. Management Science, 30, 854–867.
Patterson, J. H., Sowinski, R., Talbot, F. B. and Weglarz, J. (1989) An algorithm for a general class of precedence and resource constrained scheduling problems, in Advances in Project Scheduling, Slowinski, R. and Weglarz, J. (eds), Elsevier, Amsterdam, pp. 3–28.
Roy, B. (1964) Les problèmes d'ordonnancement, Dunod, Paris.
Stinson, J. P., Davis, E. W. and Khumawala, B. M. (1978) Multiple resource-constrained scheduling using branch and bound. AIIE Transactions, 10, 252–259.
Talbot, F. B. and Patterson, J. H. (1978) An efficient integer programming algorithm with network cuts for solving resource-constrained scheduling problems. Management Science, 24, 1163–1174.
Zhan, J. (1991), Heuristische Ressourcenplanung in MPM-Netzplänen mit beschränkter Kapazität, Ph. D. Thesis, University of Karlsruhe, Germany.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Neumann, K., Zhan, J. Heuristics for the minimum project-duration problem with minimal and maximal time lags under fixed resource constraints. J Intell Manuf 6, 145–154 (1995). https://doi.org/10.1007/BF00123686
Issue Date:
DOI: https://doi.org/10.1007/BF00123686