abstract

We study the convex hull of feasible solutions to the cumulative constraint and propose families of facet-defining inequalities for the case in which all jobs have identical data (release and due dates, processing time, and resource consumption). Those families can be used to derive valid inequalities for the case with non-identical job data. We implement our cuts inside a branch-and-cut algorithm for cumulative scheduling and present some preliminary computational results.