6533b7d7fe1ef96bd1268258
RESEARCH PRODUCT
The project scheduling polyhedron: Dimension, facets and lifting theorems
Josémanuel Tamarit GoerlichRamón Alvarez-valdés Olaguíbelsubject
Convex hullDiscrete mathematicsmedicine.medical_specialtyInformation Systems and ManagementGeneral Computer SciencePolyhedral combinatoricsDimension (graph theory)Graph theoryManagement Science and Operations ResearchIndustrial and Manufacturing EngineeringLongest path problemCombinatoricsPolyhedronRectificationModeling and SimulationmedicineGraph (abstract data type)Mathematicsdescription
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 the inequalities that do not define facets, we derive some general lifting theorems and apply them to obtain in general stronger inequalities and facets in some special cases.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1993-06-01 | European Journal of Operational Research |