The project scheduling polyhedron: Dimension, facets and lifting theorems

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 …

Un procedimiento de fuerte reducción de las dimensiones del RCPS/π

Recently, in the field of project scheduling problems the concept of partially renewable resources has been introduced. Theoretically, it is a generalization of both renewable and non-renewable resources. From an applied point of view, partially renewable resources allow us to model a large variety of situations that do not fit into classical models, but can be found in real problems in timetabling and labour scheduling. When modelling real problems, the problem of project scheduling with partially renewable resources, as many other combinatorial problems, gets such large dimensions that it is quite difficult to apply solution procedures. In this paper, we describe some powerful preprocessi…

HEURISTIC ALGORITHMS FOR RESOURCE-CONSTRAINED PROJECT SCHEDULING: A REVIEW AND AN EMPIRICAL ANALYSIS