A Polynomial Algorithm of Optimum Cutting a Rectangle into Rectangles with Two Heights


We consider the problem of guillotine cutting a rectangular sheet into rectangular pieces with two heights. A polynomial time algorithm for this problem is constructed.

Share and Cite:

M. Arslanov, "A Polynomial Algorithm of Optimum Cutting a Rectangle into Rectangles with Two Heights," American Journal of Operations Research, Vol. 4 No. 1, 2014, pp. 22-29. doi: 10.4236/ajor.2014.41003.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] H. Dyckhoff, “A Typology of Cutting and Packing Problems,” European Journal of Operational Research, Vol. 44, No. 2, 1990, pp. 145-159. http://dx.doi.org/10.1016/0377-2217(90)90350-K
[2] A. G. Tarnowski, J. Terno and G. Scheithauer, “A Polynomial Time Algorithm for the Guillotine Pallet Loading Problem,” INFOR, Vol. 32, 1994, pp. 275-287.
[3] M. Z. Arslanov, “A Polynomial Algorithm for One Problem of Guillotine Cutting,” Operations Research Letters, Vol. 35, No. 5, 2007, pp. 636-644. http://dx.doi.org/10.1016/j.orl.2006.12.003
[4] 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.
[5] E. Girlich and A. G. Tarnowski, “On Polynomial Solvability of Two Multiprocessor Scheduling Problems,” Mathematical Methods of Operations Research, Vol. 50, No. 1, 1999, pp. 27-51.
[6] H. W. Lenstra Jr., “Integer Programming with a Fixed Number of Variables,” Mathematics of Operations Research, Vol. 8, No. 4, 1983, pp. 538-548.
[7] S. T. McCormick, S. R. Smallwood and F. C. R. Spieksma, “A Polynomial Algorithm for Multiprocessor Scheduling with Two Job Lengths,” Mathematics of Operations Research, Vol. 26, No. 1, 2001, pp. 31-49.
[8] L. A. Lyusternik, “Convex Figures and Polyhedra,” Dover Publications, New York, 1963.
[9] R. K. Guy, “The Book of Numbers,” Springer-Verlag, New York, 1996.

Copyright © 2022 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.