A Strong Cutting Plane Algorithm for Production Scheduling with Changeover Costs

Changeover costs (and times) are central to numerous manufacturing operations. These costs arise whenever work centers capable of processing only one product at a time switch from the manufacture of one product to another. Although many researchers have contributed to the solution of scheduling problems that include changeover costs, due to the problem's combinatorial explosiveness, optimization-based methods have met with limited success. In this paper, we develop and apply polyhedral methods from integer programming for a dynamic version of the problem. Computational tests with problems containing one to five products (and up to 225 integer variables) show that polyhedral methods based upon a set of facet inequalities developed in this paper can effectively reduce the gap between the value of an integer programming formulation of the problem and its linear programming relaxation (by a factor of 94 to 100%). These results suggest the use of a combined cutting plane/branch-and-bound procedure as a solution approach. In a test with a five product problem, this procedure, when compared with a standard linear programming-based branch-and-bound approach, reduced computation time by a factor of seven.