The project scheduling polyhedron: Dimension, facets and lifting theorems

1993

Abstract The Project scheduling with resource constraints can be formulated as follows: given a graph G with node set N, a set H of directed arcs corresponding to precedence relations, and a set H′ of disjunctive arcs reflecting the resource incompatibilities, find among the subsets of H′ satisfying the resource constraints the set S that minimizes the longest path in graph (N, H ∪ S). We define the project scheduling polyhedron Qs as the convex hull of the feasible solutions. We investigate several classes of inequalities with respect to their facet-defining properties for the associated polyhedron. The dimension of Qs is calculated and several inequalities are shown to define facets. For …