Resource Constrained Project Computing Lower Bounds By Solving Minimum Problems

We propose a novel approach to compute bounds on the objective function value of a wide class of resource-constrained project scheduling problems. The basis is a polynomial-time algorithm to solve the following scheduling problem: Given a set of activities with start-time dependent costs and temporal constraints in the form of time windows, find a feasible schedule of minimum total cost. Motivated by a known result that this problem can be formulated as a cardinality-constrained stable set problem in comparability graphs, we show how to reduce it to a minimum cut problem in an appropriate directed graph. We focus on an application of this algorithm to different types of resource-constrained project scheduling problems by using it for the computation of lower bounds on the objective function value via Lagrangian relaxation of these problems. This approach shows to be applicable to various problem settings, and an extensive study based on widely accepted test b..