Valid inequalities and facets for the capacitated lot-sizing problem with changeover costs

Abstract

We study a scheduling problem with changeover costs and capacity constraints. The problem is NP-complete and combinatorial algorithms have not been very successful. We identify a general class of facets which subsumes as a special case all facets described earlier. We also develop a cutting plane based procedure for the dynamic version of the problem, and solve problem instances with up to 1200 integer variables to optimality without resorting to branch and bound procedures.