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

Author(s)
M. Z. Arslanov

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.

M. Arslanov, "A Polynomial Algorithm of Optimum Cutting a Rectangle into Rectangles with Two Heights,"

References

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

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