Article ID: | iaor20031874 |
Country: | United States |
Volume: | 50 |
Issue: | 4 |
Start Page Number: | 708 |
End Page Number: | 719 |
Publication Date: | Jul 2002 |
Journal: | Operations Research |
Authors: | Magnanti Thomas L., Sastry Trilochan |
Keywords: | programming: integer |
We study a scheduling problem with changeover costs and capacity constraints. The problem is NP-complete, and combinatorial algorithms for solving it have not performed well. We identify a general class of facets that subsumes as special cases some known facets from the literature. We also develop a cutting-plane-based procedure and reformulation for the problem, and we obtain optimal solutions to problem instances with up to 600 integer variables without resorting to branch-and-bound procedures.