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 settin g up the line to produce a different product. The problem of finding t he schedule for producing products on a single level, capacitated line such that the best trade-off between changeover and inventory carryin g costs is obtained can be complex. In this paper, we solve a mixed in teger programming formulation of that problem utilizing Lagrangean dec omposition for finding lower bounds, and a primal heuristic for genera ting feasible schedules from Lagrangean solutions. Compared to existin g approaches, our procedure yields near optimum solutions to large pro blems faster.