Solving a combined cutting-stock and lot-sizing problem with a column generating procedure

• Published in: Computers & operations research 2008-10, Vol.35 (10), p.3371-3392
• Main Authors: NonÅs, Sigrid Lise, Thorstenson, Anders
• Format: Article
• Language: English
• Subjects: Applied sciences; Column generation; Comparative analysis; Cutting; Cutting stock problem; Exact sciences and technology; Flows in networks. Combinatorial problems; Heuristic; Inventory; Inventory control, production control. Distribution; Manufacturing; Non-linear programming; Nonlinear programming; Operational research and scientific management; Operational research. Management science; Problem solving; Studies
• ISSN: 0305-0548; 1873-765X; 0305-0548
• DOI: 10.1016/j.cor.2007.03.005

In NonÅs and Thorstenson [A combined cutting stock and lot sizing problem. European Journal of Operational Research 120(2) (2000) 327–42] a combined cutting-stock and lot-sizing problem is outlined under static and deterministic conditions. In this paper we suggest a new column generating solution procedure for this problem that works well on both small and large-sized problems. The procedure includes characteristics from both the column generating procedure in NonÅs and Thorstenson, which works well on small-sized problems, and from the sequential heuristic due to Haessler [A heuristic programming solution to a nonlinear cutting stock problem, Management Science 17(12) (1971) 793–802], which works well on large-sized problems. Numerical results are presented that show that the new heuristic performs better than both of the earlier procedures. Comparisons with results obtained by other authors indicate that the procedure works well also for the extended cutting-stock problem with only a setup cost for each pattern change.