The two-dimensional cutting stock problem revisited

• 成果类型: Article
• 署名作者: Seiden, SS; Woeginger, GJ
• 署名单位: Louisiana State University System; Louisiana State University; Eindhoven University of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-004-0548-1
• 发表日期: 2005
• 页码: 519-530
• 关键词: two-dimensional packing; performance bounds; strip packing; algorithms

摘要

In the strip packing problem (a standard version of the two-dimensional cutting stock problem), the goal is to pack a given set of rectangles into a vertical strip of unit width so as to minimize the total height of the strip needed. The k-stage Guillotine packings form a particularly simple and attractive family of feasible solutions for strip packing. We present a complete analysis of the quality of k-stage Guillotine strip packings versus globally optimal packings: k = 2 stages cannot guarantee any bounded asymptotic performance ratio. k = 3 stages lead to asymptotic performance ratios arbitrarily close to 1.69103; this bound is tight. Finally, k = 4 stages yield asymptotic performance ratios arbitrarily close to 1.