Production planning problem where products have alternative routings and bills-of-material

A company produces a large number of products in a flexible factory consist ing of numerous workcentres. Each product can follow a number of different routings through the factory. Associated with each routing is a range of ma terials, any one of which can be used to produce the product. At the beginn ing of each period the company assigns a routing and a material to each pro duct in a list of orders to be completed. The objective is to maximize the orders that can be completed that period given constraints on workcentre ca pacity and material inventory at the company. After several periods have pa ssed or whenever conditions change, the company reviews the materials it ke eps in inventory to determine whether the mix and quantities should be chan ged. The motivation for this study is a problem instance at a steel company . The products are different chemistries, widths and gauges of galvanized s teel. The workcentres are pickling lines, cold rolling mills, galvanizing l ines, prefinishing and painting facilities. The materials are different che mistries, widths and gauges of semi-finished steel. The general problem is not unique to steel companies. Versions of it are likely to exist in other companies where production systems have some flexibility. The production pr oblem is di? cult to solve optimally in practice because of its combinatori al nature (i.e. there are a large number of orders, routings, materials and workcentres) and because the decision variables are restricted to be integ er valued. However, the problem has a special structure that permits it to be decomposed into subproblems that are easier to solve. A heuristical solu tion procedure consisting of three steps is presented. First, an LP relaxat ion of the problem is solved to give an initial allocation of workcentre ca pacity to groups of similar orders. Second, routings and materials are assi gned to orders in each group. Third, any unused capacity after the first tw o steps is reviewed to determine whether it can be used to improve the assi gnment in the second step. Lower and upper bounds on the value of the optim al solution are calculated to evaluate the quality of the solution in Step 3. The solution for the instance at the steel company is within 4% of the l ower bound. Dual variables are used to decide where additional capacity sho uld be added.