Polynomial algorithms for guillotine cutting of a rectangle into small rectangles of two kinds

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.