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

¹ Institute of Problems of Informatics and Control, Almaty, Kazakhstan

Abstract

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.

KeywordsCuttingConvex HullPolynomial Algorithms

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
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.
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
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.
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.
H. W. Lenstra Jr., “Integer Programming with a Fixed Number of Variables,” Mathematics of Operations Research, Vol. 8, No. 4, 1983, pp. 538-548.
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.
L. A. Lyusternik, “Convex Figures and Polyhedra,” Dover Publications, New York, 1963.
R. K. Guy, “The Book of Numbers,” Springer-Verlag, New York, 1996.

Menu

Menu

Menu

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

Abstract

References (9)