Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
481363 | European Journal of Operational Research | 2008 | 15 Pages |
Abstract
This paper focuses on guillotine cuts which often arise in real-life cutting stock problems. In order to construct a solution verifying guillotine constraints, the first step is to know how to determine whether a given cutting pattern is a guillotine pattern. For this purpose, we first characterize guillotine patterns by proving a necessary and sufficient condition. Then, we propose a polynomial algorithm to check this condition. Based on this mathematical characterization of guillotine patterns, we then show that guillotine constraints can be formulated into linear inequalities. The performance of the algorithm to check guillotine cutting patterns is evaluated by means of computational results.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Said Ben Messaoud, Chengbin Chu, Marie-Laure Espinouse,