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 material 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. The problem can be formulated as an integer linear programming problem. The problem has a special structure that makes it possible to construct and solve a Lagrangian relaxation.