A Branch and Bound Algorithm for Resource Constrained Project Scheduling Problem Subject to Cumulative Resources
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.
[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.
[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.
@article{"International Journal of Mechanical, Industrial and Aerospace Sciences:54431", author = "A. Shirzadeh Chaleshtari and Sh. Shadrokh", title = "A Branch and Bound Algorithm for Resource Constrained Project Scheduling Problem Subject to Cumulative Resources", 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.", volume = "6", number = "2", pages = "427-6", }
