Computing lower bounds by destructive improvement: An application to resource-constrained project scheduling

Computing lower bounds by destructive improvement: An application to resource-constrained project scheduling

0.00 Avg rating0 Votes
Article ID: iaor20001475
Country: Netherlands
Volume: 112
Issue: 2
Start Page Number: 322
End Page Number: 346
Publication Date: Jan 1999
Journal: European Journal of Operational Research
Authors: ,
Keywords: scheduling
Abstract:

In this paper, 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. For this problem, only a few constructive bound arguments are available in the literature. We 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.

Reviews

Required fields are marked *. Your email address will not be published.