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\text{,}{a}_i)\text{,}i\in I$ have the same width, and their heights can be various. Rectangles of the second kind (_bj,d),j∈J$(b_j\text{,}d)\text{,}j\in 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.