A Lagrangean decomposition solution to a single line multiproduct scheduling problem

One of the major concerns in manufacturing is the cost and/or time of product changeovers on a production line. A changeover involves setting up the line to produce a different product. The problem of finding the schedule for producing products on a single level, capacitated line such that the best trade-off between changeover and inventory carrying costs is obtained can be complex. In this paper, we solve a mixed integer programming formulation of that problem utilizing Lagrangean decomposition for finding lower bounds, and a primal heuristic for generating feasible schedules from Lagrangean solutions. Compared with existing approaches, our procedure yields near-optimum solutions to large problems faster.