A Branch and Bound Algorithm for Resource Constrained Project Scheduling Problem Subject to Cumulative Resources

Authors: A. Shirzadeh Chaleshtari, Sh. Shadrokh

Abstract:

Renewable and non-renewable resource constraints have been vast studied in theoretical fields of project scheduling problems. However, although cumulative resources are widespread in practical cases, the literature on project scheduling problems subject to these resources is scant. So in order to study this type of resources more, in this paper we use the framework of a resource constrained project scheduling problem (RCPSP) with finish-start precedence relations between activities and subject to the cumulative resources in addition to the renewable resources. We develop a branch and bound algorithm for this problem customizing precedence tree algorithm of RCPSP. We perform extensive experimental analysis on the algorithm to check its effectiveness and performance for solving different instances of the problem in question.

Keywords: Resource constrained project scheduling problem, cumulative resources, branch and bound algorithm, precedence tree.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1060864

References:

[1] K. Neumann, C. Schwindt, "Project scheduling with inventory constraints," Mathematical Methods of Operations Research, vol. 56, pp. 513-533, 2002.
[2] C. Schwindt, and N. Trautmann, "Batch scheduling in process industries: An application of resource-constrained project scheduling,"OR Spectrum, vol. 22, pp. 501-524, 2000.
[3] K. Neumann, C.Schwindt, and N. Trautmann, "Scheduling of continuous and discontinuous material flows with intermediate storage restrictions,"European Journal of Operational Research, vol. 165, pp. 495-509, 2005.
[4] J. H. Bartels, and J. Zimmermann, "Scheduling tests in automotive R&D projects,"European Journal of Operational Research, vol. 193, pp. 805- 819, 2009.
[5] J.A. Carruthers, and A. Battersby, "Advances in critical path methods,"Operational Research Quarterly, vol. 17, pp. 359-380, 1996.
[6] O. Icmeli, S.S. Erenguc, and C.J. Zappe, "Project scheduling problems: a survey," International Journal of Operations & Production Management, vol. 13(11), pp. 80-91, 1993.
[7] L. Özdamar, and G.Ulusoy, "A survey on the resource constrained project scheduling problem,"IIE Transactions, vol. 27, pp. 574-586, 1995.
[8] W. Herroelen, E. Demeulemeester, and B. De Reyck, "Resourceconstrained project scheduling: a survey of recent developments,"Computers & Operations Research, vol. 25, pp. 279- 302, 1998.
[9] P. Brucker, A.Drexl, R.Mohring, K. Neumann, and E. Pesch, "Resourceconstrained project scheduling: notation, classification, models, and methods,"European Journal of Operational Research, vol. 112, pp. 3- 41, 1999.
[10] S. Hartmann, and R.Kolisch, "Experimental evaluation of state-of-theart heuristics for the resource-constrained project scheduling problem. European Journal of Operational Research, vol. 127, pp. 394-407, 2000.
[11] R. Kolisch, and R. Padman, "An integrated survey of deterministic project scheduling,"OMEGA, vol. 29, pp. 249-272, 2001.
[12] R. Kolisch, and S. Hartmann, "Experimental investigation of heuristics for resource-constrained project scheduling: an update,"European Journal of Operational Research, vol. 174, pp. 23-37, 2006.
[13] J. Blazewicz, J. Lenstra, and A. RinnooyKan, "Scheduling subject to resource constraints: Classification and complexity," Discrete Applied Mathematics, vol. 5, pp. 11-24, 1983.
[14] E.W. Davis, and J.H. Patterson, "A comparison of heuristic and optimum solutions in resource-constrained project scheduling,"Management Science, vol. 21, pp. 944-955, 1975.
[15] D.F. Cooper, "Heuristics for scheduling resource-constrained projects: an experimental investigation,"Management Science, vol. 22, pp. 1186- 1194, 1976.
[16] G. Ulusoy, and L. Ozdamar, "Heuristic performance and network/resource characteristics in resource-constrained project scheduling,"Journal of the Operational Research Society, vol. 40, pp. 1145-1152, 1989.
[17] FF. Boctor,"Some efficient multi-heuristic procedures for resourceconstrained project scheduling,"European Journal of Operational Research, vol. 49, pp. 3-13, 1990.
[18] L. Özdamar, and G.Ulusoy, "A local constraint based analysis approach to project scheduling under general resource constraints,"European Journal of Operational Research, vol. 79, pp. 287-298, 1994.
[19] R. Kolisch, "Efficient priority rule for the resource-constrained project scheduling problem,"Journal of Operations Management, vol. 14, pp. 179-192, 1996.
[20] V.J. Leon, and B. Ramamoorthy, "Strength and adaptability of problemspace based neighborhoods for resource-constrained scheduling,"OR Spektrum, vol. 17, pp. 173-182, 1995.
[21] J.K. Lee, and Y.D. Kim, "Search heuristics for resource-constrained project scheduling,"Journal of the Operational Research Society, vol. 47, pp. 678-689, 1996.
[22] S. Hartmann, "A competitive genetic algorithm for the resourceconstrained project scheduling,"Naval Research Logistics, vol. 45, pp. 733-750, 1997.
[23] S. Hartmann "A self-adapting genetic algorithm for project scheduling under resource constraints,"Naval Research Logistics, vol. 49, pp. 433- 448, 2002.
[24] J. Alcaraz, and C. Maroto,"A robust genetic algorithm for resource allocation in project scheduling,"Annals of Operations Research, vol. 102, pp. 83-109, 2001.
[25] K.S. Hindi, H. Yang, and K. Fleszar, "An evolutionary algorithm for resource-constrained project scheduling,"IEEE Transactions on Evolutionary Computation, vol. 6, pp. 512-518, 2002.
[26] Y.C. Toklu, (2002). "Application of genetic algorithms to construction scheduling with or without resource constraints," Canadian Journal of Civil Engineering, vol. 29, pp. 421-429, 2002.
[27] V. Valls, F.Ballestin, and S. Quintanilla, "A hybrid genetic algorithm for the resource constrained project scheduling problem,"European Journal of Operational Research, vol. 185, pp. 495-508, 2008.
[28] FF. Boctor, "An adaptation of the simulated annealing algorithm for solving resource-constrained project scheduling problems,"International Journal of Production Research, vol. 34, pp. 2335-2351, 1996.
[29] J.H. Cho, and Y.D. Kim, "A simulated annealing algorithm for resourceconstrained project scheduling problems,"Journal of the Operational Research Society, vol. 48, pp. 736-744, 1997.
[30] K. Bouleimen, and H.Lecocq, "A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version,"European Journal of Operational Research, vol. 149, pp. 268-281, 2003.
[31] E. Pinson, C. Prins, and F. Rullier, "Using tabu search for solving the resource- constrained project scheduling problem," in Proc. 4th international workshop on project management and scheduling, Leuven, Belgium, 1994, pp. 102-106.
[32] P.R. Thormas, and S. Salhi, "A tabu search approach for the resource constrained project scheduling problem," Journal of Heuristics, vol. 4, pp. 123-139, 1998.
[33] D. Merkle, M.Middendorf, and H. Schmeck, "Ant colony optimization for resource-constrained project scheduling,"IEEE Transactions on Evolutionary Computation, vol. 6, pp. 333-346, 2002.
[34] A.A.B. Pritsker, L.J. Watters, P.M. Wolfe, "Multiproject scheduling with limited resources: a zero-one programming approach," Management Science, vol. 16, pp. 93-107, 1969.
[35] J.H. Patterson, and W.D. Huber, "A horizon-varying, zero-one approach to project scheduling,"Management Science, vol. 20, pp. 990-998, 1974.
[36] J.H. Patterson, and G.W. Roth, "Scheduling a project under multiple resource constraints: a zero-one programming approach,"AIIE Transactions, vol. 8, pp. 449-455, 1976.
[37] E.W. Davis, and G.E. Heidorn, "An algorithm for optimal project scheduling under multiple resource constraints," Management Science, vol. 17, pp. 803-816, 1971.
[38] F.B. Talbot, and J.H. Patterson, "An efficient integer programming algorithm with network cuts for solving resource constrained scheduling problems," Management Science, vol. 24, pp. 1163-1174, 1978.
[39] N. Christofides, R. Alvarez-Valdes, and J.M. Tamarit, "Project scheduling with resource constraints: a branch and bound approach," European Journal of Operational Research, vol. 29, pp. 262-73, 1987.
[40] E. Demeulemeester, and W. Herroelen, "A branch-and-bound procedure for the multiple resource-constrained project scheduling problems,"Management Science, vol. 38, pp. 1803-1818, 1992.
[41] E. Demeulemeester, and W. Herroelen, "New benchmark results for the resource-constrained project scheduling problem," Management Science, vol. 43, pp. 1485-1492, 1997.
[42] P. Brucker, S.Knust, A.Schoo, and O. Thiele, "A branch and bound algorithm for the resource-constrained project scheduling problem,"European Journal of Operational Research, vol. 107, pp. 272- 288, 1998.
[43] A. Mingozzi, V.Maniezzo, S. Ricciardelli, and L. Bianco, "An exact algorithm for project scheduling with resource constraints based on new mathematical formulation,"Management Science, vol. 44, pp. 714-729, 1998.
[44] U. Dorndorf, E. Pesch, and T. Phan-Huy, "A branch-and-bound algorithm for the resource-constrained project scheduling problem," Mathematical Methods of Operations Research, vol. 52, pp. 413-439, 2000.
[45] J.H. Patterson, R. Sowinski, F.B. Talbot, and J. Weglarz, "An algorithm for a general class of precedence and resource constrained scheduling problems," in Advances in Project Scheduling, R. Sowinski, and J. Weglarz, Amsterdam: Elsevier, 1989, pp. 3-28.
[46] J.P. Stinson, E.W. Davis, and B.M. Khumawala, "Multiple resourceconstrained scheduling using branch and bound," AIIE Transactions, vol. 10, pp. 252-259, 1978.
[47] G. Igelmund, and F.J. Radermacher, "Preselectivestrategies for the optimization of stochastic project networks under resource constraints," Networks, vol. 13, pp. 1-28, 1983.
[48] A. Lova, A., P. Tormos, and F. Barber, "Multimode resourceconstrained project scheduling: scheduling schemes, priority rules and mode selection rules," Inteligenica Artificial, vol. 10(30), pp. 69-86, 2006.
[49] E. Demeulemeester, and W. Herroelen, Project Scheduling, A research handbook. Boston: Kluwer Academic Publishers, 2002.
[50] R. Kolisch, A. Sprecher, "PSPLIB - A project scheduling problem library," European Journal of Operational Research, vol. 96, pp. 205- 216, 1996.