×

A new lower bound for the resource-constrained project scheduling problem with generalized precedence relations. (English) Zbl 1231.90177

Summary: We propose a new lower bound for the resource-constrained project scheduling problem with generalized precedence relationships. The lower bound is based on a relaxation of the resource constraints among independent activities and on a solution of the relaxed problem suitably represented by means of an AON acyclic network. Computational results are presented and confirmed a better practical performance of the proposed method with respect to those present in the literature.

MSC:

90B35 Deterministic scheduling theory in operations research
90C11 Mixed integer programming
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Blazewicz, J.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Scheduling subject to resource constraints: classification and complexity, Discrete Applied Mathematics, 5, 1, 11-24 (1983) · Zbl 0516.68037
[2] Elmaghraby, S. E.E.; Kamburowski, J., The analysis of activity networks under generalized precedence relations (GPRs), Management Science, 38, 9, 1245-1263 (1992) · Zbl 0758.90044
[3] Dorndorf U. Project scheduling with time windows. Physica; 2002.; Dorndorf U. Project scheduling with time windows. Physica; 2002. · Zbl 1058.90027
[4] Neumann K, Schwindt C, Zimmerman J. Project scheduling with time windows and scarce resources. In: Lecture notes in economics and mathematical systems, vol. 508. Berlin: Springer; 2002.; Neumann K, Schwindt C, Zimmerman J. Project scheduling with time windows and scarce resources. In: Lecture notes in economics and mathematical systems, vol. 508. Berlin: Springer; 2002.
[5] Bartusch, M.; Mohring, R. H.; Radermacher, F. J., Scheduling project networks with resource constraints and time windows, Annals of Operations Research, 16, 201-240 (1988) · Zbl 0693.90047
[6] De Reyck B. Scheduling projects with generalized precedence relations—exact and heuristic approaches. PhD thesis, Department of Applied Economics. Katholieke Universiteit Leuven, Leuven, Belgium, 1998.; De Reyck B. Scheduling projects with generalized precedence relations—exact and heuristic approaches. PhD thesis, Department of Applied Economics. Katholieke Universiteit Leuven, Leuven, Belgium, 1998.
[7] Bianco L, Caramia M. A new formulation of the resource-unconstrained project scheduling problem with generalized precedence relations to minimize the completion time. Technical Report DII, University of Rome “Tor Vergata”, 2007, submitted for publication, downloadable from ⟨http://www.dii.uniroma2.it/doc/gprs.pdf; Bianco L, Caramia M. A new formulation of the resource-unconstrained project scheduling problem with generalized precedence relations to minimize the completion time. Technical Report DII, University of Rome “Tor Vergata”, 2007, submitted for publication, downloadable from ⟨http://www.dii.uniroma2.it/doc/gprs.pdf · Zbl 1202.90123
[8] Bianco L, Caramia M. A new approach for the project scheduling problem with generalized precedence relations. In: Proceedings of the 11th international workshop on project management and scheduling, Istanbul, April 28-30, 2008.; Bianco L, Caramia M. A new approach for the project scheduling problem with generalized precedence relations. In: Proceedings of the 11th international workshop on project management and scheduling, Istanbul, April 28-30, 2008. · Zbl 1231.90177
[9] Demeulemeester, E. L.; Herroelen, W. S., A branch-and-bound procedure for the generalized resource-constrained project scheduling problem, Operations Research, 45, 201-212 (1997) · Zbl 0890.90098
[10] De Reyck, B.; Herroelen,, W., A branch-and-bound procedure for the resource-constrained project scheduling problem with generalized precedence relations, European Journal of Operational Research, 111, 1, 152-174 (1998) · Zbl 0948.90077
[11] Demeulemeester, E. L.; Herroelen, W. S., Project Scheduling—A Research Handbook (2002), Kluwer Academic Publishers: Kluwer Academic Publishers Boston · Zbl 1059.90068
[12] Klein, R.; Scholl, A., Computing lower bounds by destructive improvement: an application to resource-constrained project scheduling, European Journal of Operational Research, 112, 322-346 (1999) · Zbl 0938.90030
[13] Demeulemeester, E. L.; Herroelen, W. S., New benchmark results for the resource-constrained project scheduling problem, Management Science, 43, 11, 1485-1492 (1997) · Zbl 0914.90160
[14] Hochbaum, D.; Naor, J., Simple and fast algorithms for linear and integer programs with two variables per inequality, SIAM Journal on Computing, 23, 6, 1179-1192 (1994) · Zbl 0831.90089
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.