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

A company produces a large number of products in a flexible factory consisting of numerous workcentres. Each product can follow a number of different routings through the factory. Associated with each routing is a range of materials, any one of which can be used to produce the product. At the beginning of each period the company assigns a routing and a material to each product in a list of orders to be completed. The objective is to maximise the orders that can be completed that period given constraints on workcentre capacity and material inventory at the company. After several periods have passed or whenever conditions change, the company reviews the materials it keeps in inventory to determine whether the mix and quantities should be changed. The motivation for this study is a problem instance at a steel company. The products are different chemistries, widths and gauges of galvanized steel. The workcentres are pickling lines, cold rolling mills, galvanizing lines, prefinishing and painting facilities. The materials are different chemistries, 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 problem is difficult to solve optimally in practice because of its combinatorial nature (i.e. there are a large number of orders, routings, materials and workcentres) and because the decision variables are restricted to be integer valued. However, the problem has a special structure that permits it to be decomposed into subproblems that are easier to solve. A heuristical solution procedure consisting of three steps is presented. First, an LP relaxation of the problem is solved to give an initial allocation of workcentre capacity to groups of similar orders. Second, routings and materials are assigned to orders in each group. Third, any unused capacity after the first two steps is reviewed to determine whether it can be used to improve the assignment in the second step. Lower and upper bounds on the value of the optimal 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 lower bound. Dual variables are used to decide where additional capacity should be added.