zbMATH — the first resource for mathematics

Computing lower bounds by destructive improvement: An application to resource-constrained project scheduling. (English) Zbl 0938.90030
Summary: Two meta-strategies for computing lower bounds (for minimization problems) are described. Constructive (direct) methods directly calculate a bound value by relaxing a problem and solving this relaxation. Destructive improvement techniques restrict a problem by setting a maximal objective function value $$F$$ and try to contradict (destruct) the feasibility of this reduced problem. In case of success, $$F$$ or even $$F+1$$ is a valid lower bound value. The fundamental properties and differences of both meta-strategies are explained by applying them to the well-known resource-constrained project scheduling problem (RCPSP). For this problem, only a few constructive bound arguments are available in the literature.
The authors present a number of extensions and new methods as well as techniques for reducing problem data which can be exploited within the destructive improvement framework. Comprehensive numerical experiments show that the new constructive bound arguments clearly provide better bounds than the former ones and that further really significant improvements are obtained through an appropriate application of destructive improvement.

MSC:
 90B35 Deterministic scheduling theory in operations research
Software:
Algorithm 520; Bison; PSPLIB
Full Text:
References:
 [1] Alvarez-Valdez, R., Tamarit, J.M., 1989. Heuristic algorithms for resource-constrained project scheduling: A review and an empirical analysis, in: Slowinski, R., Weglarz, J. (Eds.), Advances in Project Scheduling, Elsevier, Amsterdam, pp. 113-134 [2] Balas, E., 1970. Project scheduling with resource constraints, in: Beale, E.M.L. (Ed.), Applications of Mathematical Programming Techniques, Elsevier, New York, pp. 187-200 [3] Boctor, F.F., Some efficient multi-heuristic procedures for resource-constrained project scheduling, European journal of operational research, 49, 3-13, (1990) · Zbl 1403.90305 [4] Brucker, P., Schoo, A., Thiele, O., 1996. A branch and bound algorithm for the resource-constrained project scheduling problem. European Journal of Operational Research (to appear) · Zbl 0970.90030 [5] Carlier, J.; Latapie, B., Une méthode arborescente pour résoudre LES problémes cumulatifs, Recherche opérationelle, 25, 311-340, (1991) · Zbl 0733.90036 [6] Christofides, N.; Alvarez-Valdes, R.; Tamarit, J.M., Project scheduling with resource constraints: A branch and bound approach, European journal of operational research, 29, 262-273, (1987) · Zbl 0614.90056 [7] Demeulemeester, E., 1992. Optimal Algorithms for Various Classes of Multiple Resource-Constrained Project Scheduling Problems. Unpublished Ph.D. Thesis, Department of Applied Economic Sciences, Katholieke Universiteit Leuven [8] Demeulemeester, E.; Herroelen, W., A branch-and-bound procedure for the multiple resource-constrained project scheduling problem, Management science, 38, 1803-1818, (1992) · Zbl 0761.90059 [9] Demeulemeester, E., Herroelen, W., 1997. New benchmark results for the resource-constrained project scheduling problem. Management Science 43, 1485-1492 · Zbl 0914.90160 [10] De Reyck, B.; Herroelen, W., On the use of the complexity index as a measure of complexity in activity networks, European journal of operational research, 91, 347-366, (1996) · Zbl 0924.90092 [11] De Reyck, B., Herroelen, W., 1996b. A branch-and-bound procedure for the resource-constrained project scheduling problem with generalized precedence relations, Research Report No. 9613, Department of Applied Economic Sciences, Katholieke Universiteit Leuven · Zbl 0948.90077 [12] Fischetti, M.; Toth, P., An additive bounding procedure for combinatorial optimization problems, Operations research, 37, 319-328, (1989) · Zbl 0676.90049 [13] Fisher, M.L., Optimal solution of scheduling problems using Lagrange multipliers: part I, Operations research, 21, 1114-1127, (1973) · Zbl 0294.90085 [14] Kolisch, R., Serial and parallel resource-constrained project scheduling methods revisited – theory and computation, European journal of operational research, 90, 320-333, (1996) · Zbl 0916.90151 [15] Kolisch, R.; Sprecher, A.; Drexl, A., Characterization and generation of a general class of resource-constrained project scheduling problems, Management science, 41, 1693-1703, (1995) · Zbl 0870.90070 [16] Mingozzi, A., Maniezzo, V., Ricciardelli, S., Bianco, L., 1995. An exact algorithm for project scheduling with resource constraints based on a new mathematical formulation. Management Science (to appear) · Zbl 1004.90036 [17] Patterson, J.H., A comparison of exact approaches for solving the multiple constrained resource, project scheduling problem, Management science, 30, 854-867, (1984) [18] Scholl, A.; Klein, R.; Jürgens, C., BISON: A fast hybrid procedure for solving the one-dimensional bin packing problem, Computers and operations research, 24, 627-645, (1997) · Zbl 0882.90113 [19] Sprecher, A., 1996. Solving the RCPSP efficiently at modest memory requirements. Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel, No. 425 [20] Stinson, J.P.; Davis, E.W.; Khumawala, B.M., Multiple resource-constrained scheduling using branch and bound, AIIE transactions, 10, 252-259, (1978) [21] Talbot, F.B.; Patterson, J.H., An efficient integer programming algorithm with network cuts for solving resource-constrained scheduling problems, Management science, 24, 1163-1175, (1978) · Zbl 0395.90036 [22] Thomas, P.R.; Salhi, S., An investigation into the relationship of heuristic performance with network-resource characteristics, Journal of the operational research society, 48, 34-43, (1997) · Zbl 0881.90076 [23] Weglarz, J.; Blazewicz, J.; Cellary, W.; Slowinski, R., ALGORITHM 520: an automatic revised simplex method for constrained resource network scheduling, ACM transactions on mathematical software, 3, 295-300, (1977) · Zbl 0374.90033
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.