کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427809 | 686560 | 2011 | 4 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: A simple OPT+1OPT+1 algorithm for cutting stock under the modified integer round-up property assumption A simple OPT+1OPT+1 algorithm for cutting stock under the modified integer round-up property assumption](/preview/png/427809.png)
We present a simple algorithm for the cutting stock problem with objects of a constant number d of different sizes. Our algorithm produces solutions of value at most OPT+1OPT+1 in time dO(d)(log7n+s3.5), where OPT is the value of an optimum solution, n is the number of objects, and s is the total number of bits needed to encode the object sizes. This algorithm works under the assumption that the modified integer round-up property of Scheithauer and Terno for the cutting stock problem holds.
Research highlights
► We present a simple algorithm for cutting stock with a constant number of sizes.
► Our algorithm produces solutions of value at most OPT+1OPT+1, where OPT is the optimum.
► The algorithm is faster than previous algorithms for the problem.
► The algorithm makes the assumption that the modified integer round-up property holds.
Journal: Information Processing Letters - Volume 111, Issue 10, 30 April 2011, Pages 479–482