AJOR  Vol.4 No.1 , January 2014
A Polynomial Algorithm of Optimum Cutting a Rectangle into Rectangles with Two Heights
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.
Cite this paper: 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.

[1]   H. Dyckhoff, “A Typology of Cutting and Packing Problems,” European Journal of Operational Research, Vol. 44, No. 2, 1990, pp. 145-159.

[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.

[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.