A Polynomial Time OPT+1 Algorithm for the Cutting Stock Problem with a Constant Number of Object Lengths

• 成果类型: Article
• 署名作者: Jansen, Klaus; Solis-Oba, Roberto
• 署名单位: University of Kiel; Western University (University of Western Ontario)
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1110.0515
• 发表日期: 2011
• 页码: 743-753
• 关键词: bin packing problem; fixed number; integer

摘要

In the cutting stock problem, we are given a set of objects of different types, and the goal is to pack them all in the minimum possible number of identical bins. All objects have integer lengths, and objects of different types have different sizes. The total length of the objects packed in a bin cannot exceed the capacity of the bin. In this paper, we consider the version of the problem in which the number of different object types is constant, and we present a polynomial-time algorithm that computes a solution using at most one more bin than an optimum solution.