کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
475152 | 699219 | 2014 | 12 صفحه PDF | دانلود رایگان |
• New data structures for the cutting stock problem.
• Pattern-based versions of FFD/BFD heuristics.
• Polynomial FFD/BFD on the cutting stock input size.
The conventional assignment-based first/best fit decreasing algorithms (FFD/BFD) are not polynomial in the one-dimensional cutting stock input size in its most common format. Therefore, even for small instances with large demands, it is difficult to compute FFD/BFD solutions. We present pattern-based methods that overcome the main problems of conventional heuristics in cutting stock problems by representing the solution in a much more compact format. Using our pattern-based heuristics, FFD/BFD solutions for extremely large cutting stock instances, with billions of items, can be found in a very short amount of time.
Journal: Computers & Operations Research - Volume 48, August 2014, Pages 69–80