Article ID: | iaor20082158 |
Country: | United Kingdom |
Volume: | 58 |
Issue: | 9 |
Start Page Number: | 1156 |
End Page Number: | 1166 |
Publication Date: | Sep 2007 |
Journal: | Journal of the Operational Research Society |
Authors: | Hartman J.C., Huegler P.A. |
Keywords: | manufacturing industries, heuristics, lagrange multipliers, programming: integer |
This paper investigates the steel plate order fulfilment problem from existing inventory, which is a generalization of one-dimensional cutting and packing problems. Semi-processed inventory of steel slabs can be burned, heated, rolled, and sheared to meet customer order requirements. This problem is an integral part of the day-to-day operations of steel plate manufacturing. A 0–1 integer programming formulation is presented and two heuristics, based on single-order formulations, are presented to quickly generate lower and upper bounds. The bounds are improved using Lagrangian relaxation and subgradient optimization, producing average optimality gaps of 2.12% on 17 real-world data sets. The upper bound improvements represent actual savings over the current solution method of 1.94%, or an average of about $230 000 over a 3-week period. An economic interpretation of the Lagrange multipliers is also discussed and shown to be useful for handling rush orders.