A Lagrangian Relaxation Algorithm For A Production Planning Problem Where Products Have Alternate Routings

A manufacturer of specialty steels produces to customer order. The economy is booming and the company has more orders than it has production capacity or raw materia] inventory to produce. However the company has considerable flexibility in how it produces specialty steels. At the beginning of each time period planners assign a routing and a raw material to each order in a list of orders to be completed. the objective is to maximize the orders that can be completed given constraints on workcenter capacity and raw material inventory. Each order can follow more than one routing. Associated with each routing is a range of raw materials, any one of which can be used to produce the order. the problem can be formulated as an integer linear programming problem. However a typical instance has over 3,500 zero-one decision variables and so cannot be solved optimally by a commercial integer programming solver. the problem has a special structure that makes it possible to construct and solve a Lagrangian relaxation. the value of the Lagrangian is a lower bound on the value of the optimal solution and is used to stop a commercial solver when a good solution is found. A computational study shows that the Lagrangian relaxation can be completed in a reasonable amount of time for instances of practical size.