A Strong Cutting Plane Algorithm for Production Scheduling with Changeover Costs

T. L. Magnanti and R. Vachani
Additional contact information
T. L. Magnanti: Massachusetts Institute of Technology, Cambridge, Massachusetts
R. Vachani: GTE Laboratories, Waltham, Massachusetts

Operations Research, 1990, vol. 38, issue 3, 456-473

Abstract: 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.

Keywords: inventory/production: production planning with product changeover; production/scheduling: integer programming for product changeover; programming; integer algorithms: facets for production planning (search for similar items in EconPapers)
Date: 1990
References: Add references at CitEc
Citations: View citations in EconPapers (19)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.38.3.456 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:38:y:1990:i:3:p:456-473

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().