Exact Algorithm for Solving Project Scheduling Problems under Multiple Resource Constraints
Publication: Journal of Construction Engineering and Management
Volume 131, Issue 9
Abstract
This paper presents a new algorithm, called the enumerative branch-and-cut procedure (EBAC), for minimizing the total project duration of a construction project under multiple resource constraints based on an enumeration tree. The EBAC generates new branches to the tree corresponding to “better” feasible alternatives. It starts with all of the feasible schedule alternatives as the trial schedule alternatives at any node. The trial schedule alternatives are then evaluated to determine whether they are “worse” than any existing partial schedules in the tree by using the presented cut rules, and a worse alternative will be eliminated from the enumeration tree. In other words, the tree will contain only better feasible schedules. The presented algorithm has been coded in the VB6.0 language on a personal computer. It has been tested with the 110 scheduling problems, which have been widely used for validating a variety of schedule algorithms over the last . The EBAC can obtain the shortest project durations for all of the 110 problems.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgment
The writers are grateful to Professor James H. Patterson at Indiana University for providing them with the source data for the 110 test problems.
References
Arditi, D. (1985). “Construction productivity improvement.” J. Constr. Eng. Manage., 111(1), 1–14.
Brucker, P., Drexl, A., Möhring, R., Neuman, K., and Pesch, E. (1999a). “Resource-constrained project scheduling: Notation, classification, models, and methods.” Eur. J. Oper. Res., 112, 3–41.
Brucker, P., Knust, S., and Schoo, A. (1999b). “A branch and bound algorithm for the resource-constrained project scheduling problem.” Eur. J. Oper. Res., 107, 272–288.
Chan, W., Chua, D., and Kanan, G. (1996). “Construction resource scheduling with genetic algorithms.” J. Constr. Eng. Manage., 122(2), 125–132.
Christofides, N., Alvarez-Valdes, R., and Tamarit, J. M. (1987). “Project scheduling with resource-constraints: A branch and bound approach.” Eur. J. Oper. Res., 29, 262–273.
Davis, E. (1969). “An exact algorithm for the multiple constrained-resource project scheduling problem.” PhD dissertation, Yale Univ.
Davis, E. W., and Patterson, J. H. (1975). “A comparison of heuristic and optimum solutions in resource-constrained project scheduling.” Manage. Sci., 21(8), 944–955.
Demeulemeester, E., and Herroelen, W. (1992). “A branch-and-bound procedure for the multiple resource-constrained project schedule problem.” Manage. Sci., 38(12), 1803–1818.
Dorndorf, U., Pesch, E., and Phan-Huy, T. (2000). “A branch-and-bound algorithm for the resource-constrained project scheduling problem.” Math. Methods Oper. Res., 52, 413–439.
Faniran, O. O., Love, P. E. D., and Li, H. (1999). “Optimal allocation of construction planning resources.” J. Constr. Eng. Manage., 125(5), 311–319.
Gorenstein, S. (1970). “Planning tire production.” Manage. Sci., 17(2), 72–82.
Hamilton, M. R., and Gibson, G. E. (1996). “Benchmarking preproject-planning efforts.” J. Manage. Eng., 12(2), 25–33.
Hegazy, T. et al. (2000). “Algorithm for scheduling with multiskilled constrained resources.” J. Constr. Eng. Manage., 126(6), 414–421.
Kim, K., and de la Garza, J. M. (2003). “Phantom float.” J. Constr. Eng. Manage., 129(5), 507–517.
Klein, R., and Scholl, A. (1999). “Computing lower bounds by destructive improvement-an application to resource-constrained project scheduling.” Eur. J. Oper. Res., 112, 322–346.
Koehn, E., and Caplan, S. (1987). “Work improvement data for small and medium size contractors.” J. Constr. Eng. Manage., 113(2), 327–339.
Leu, S.-S., and Yang, C.-H. (1999). “A genetic-algorithm-based resource constrained construction scheduling system.” Constr. Manage. Econom., 17, 767–776.
Lu, M., and Li, H. (2003). “Resource-activity critical-path method for construction planning.” J. Constr. Eng. Manage., 129(4), 412–420.
Mingozzi, A., Maniezzo, V., Ricciardelli, S., and Bianco, L. (1998). “An exact algorithm for the resource-constrained project scheduling problem based on a new mathematical formulation.” Manage. Sci., 44, 714–729.
Ozdamar, L., and Ulusou, G. (1995). “A survey on the resource-constrained project scheduling problem.” IIE Trans., 27, 574–586.
Patterson, J. H. (1984). “A comparison of exact procedures for solving the multiple constrained resource project scheduling problem.” Manage. Sci., 30(7), 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.” Advances in project scheduling, R. Sowinski, and J. Weglarz, eds., Elsevier, Amsterdam, 3–28.
Shanmuganayagam, V. (1989). “Current float techniques for resources scheduling.” J. Constr. Eng. Manage., 115(3), 401–411.
Shi, J., and Deng, Z. (2000). “Object-oriented resource-based planning and control method.” Proj. Manage. J., 18(3), 179–188.
Sprecher, A., and Drexl, A. (1998). “Multi-mode resource-constrained project scheduling by a simple, general and powerful sequencing algorithm.” Eur. J. Oper. Res., 107, 431–450.
Stinson, J. P., Davis, E., and Khumawala, B. M. (1978). “Multiple resource-constrained scheduling using branch and bound.” AIIE Trans., 10(3), 252–259.
Tabot, B., and Patterson, J. H. (1978). “An efficient integer programming algorithm with network cuts for solving resource-constrained scheduling problems.” Manage. Sci., 24(11), 1163–1174.
Information & Authors
Information
Published In
Journal of Construction Engineering and Management
Volume 131 • Issue 9 • September 2005
Pages: 986 - 992
Copyright
© 2005 ASCE.
History
Received: Aug 20, 2004
Accepted: Jan 12, 2005
Published online: Sep 1, 2005
Published in print: Sep 2005
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.