کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
482105 | 1446182 | 2008 | 17 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Polynomial algorithms for guillotine cutting of a rectangle into small rectangles of two kinds Polynomial algorithms for guillotine cutting of a rectangle into small rectangles of two kinds](/preview/png/482105.png)
In this paper the problem of optimally guillotine cutting a rectangle (A, B ) into small rectangles of two kinds is considered. Rectangles of the first kind (c,ai),i∈I(c,ai),i∈I have the same width, and their heights can be various. Rectangles of the second kind (bj,d),j∈J(bj,d),j∈J have the same height, and their widths can be various. The number of occurrences of each small rectangle in a cutting pattern is not restricted. Similar problems often appear in the furniture industry. This cutting problem is reduced to the shortest path problem in a special rectangular grid, for which a linear time algorithm is suggested. This approach generalizes the approach of [E. Girlich, A.G. Tarnowski, On polynomial solvability of two multiprocessor scheduling problems, Mathematical Methods of Operations Research 50 (1999) 27–51; A.G. Tarnowski, Advanced polynomial time algorithm for guillotine generalized pallet loading problem, in: The International Scientific Collection: Decision Making Under Conditions of Uncertainty (Cutting-Packing Problems), Ufa State Aviation Technical University, 1997, pp. 93–124] and allows us to construct polynomial algorithms for the guillotine cutting problem considered with a fixed number of small rectangles of two kinds.
Journal: European Journal of Operational Research - Volume 185, Issue 1, 16 February 2008, Pages 105–121