Formation of the Guillotine Cutting Card of a Sheet by the Guillotine Layout Functions

A.A. Andrianova* , T.M. Mukhtarova** , V.R. Fazylov***
Kazan Federal University, Kazan, 420008 Russia
E-mail: *Anastasiya.Andrianova@kpfu.ru, **Tatyana.Moukhtarova@kpfu.ru, ***vfazylov@gmail.com
Received April 11, 2016

Full text PDF

Abstract

An extension of the concept of the guillotine layout function has been suggested in the paper for solving the problem of rectangular orthogonal packing, which is a function that assigns a triple of values to the width of the sheet. In addition to the standard result for the guillotine layout function - the minimum length of the sheet with a given width, which is sufficient to accommodate a given set of rectangles in a guillotine manner, two additional values have been used. They represent data on the method of cutting this sheet, with which you can uniquely form a guillotine cutting card and a guillotine layout card of the set of rectangles. These data are the characteristics of the first cut of the sheet, as well as the partition of the set of rectangles corresponding to the cut into two subsets, which is uniquely determined by the number of one of these subsets.

 The des­cription of the first cut is modeled by a single numerical value that reflects both the size of the indentation from the lower-left corner of the sheet and the orientation of the cut – along or back of the sheet, a cut is required. It has been shown that this information is sufficient for restoration of the guillotine cutting card and the guillotine layout card for a set of rectangles.

 To determine additional information about the first cut and calculate the extension of the guillotine layout function, we have proposed modifications of algorithms for obtaining the sum of two step semicontinuous right monotonically nonincreasing functions with a finite number of steps and also a minimum of two such functions. Furthermore, an algorithm for formation guillotine cutting card and for guillotine layout card for rectangles with using the calculated extensions of the guillotine layout functions for all subsets of the required set of rectangles has been proposed.

Keywords: rectangular orthogonal packing problem, guillotine cutting, extension of guillotine layout function

References

1. Kantorovich L.V., Zalgaller V.A. Calculation of Rational Cutting of Industrial Materials. Leningrad, Lenizdat, 1951. 198 p. (In Russian)

2. Kantorovich L.V., Zalgaller V.A. Rational Cutting of Industrial Materials. Novosibirsk, Nauka, 1971. 198 p. (In Russian)

3. Mukhacheva Je.A. Rational Cutting of Industrial Materials. Application in the Automated Control System. Novosibirsk, Nauka, 1987. 274 p. (In Russian)

4. Lodi A., Martello S., Monaci M. Two-dimensional packing problems: A survey.  Eur. J. Oper. Res., 2002, vol. 141, no. 2, pp. 241–252. doi: 10.1016/S0377-2217(02)00123-6.

5. Zhang D.F., Kang Y., Deng S. A new heuristic recursive algorithm for the strip rectangular packing problem.  Comput. Oper. Res., 2006, vol. 33, no. 8, pp. 2209–2217. doi: 10.1016/j.cor.2005.01.009.

6. Chen M., Huang W. A two-level search algorithm for 2D rectangular packing problem.  Comput. Ind. Eng., 2007, vol. 53, no. 1, pp. 123–136. doi: 10.1016/j.cie.2007.04.007.

7. Mukhacheva E.A., Valeeva A.F., Kartak V.M., Mukhacheva A.S. Models and methods for solving orthogonal cutting and packaging problems: Analytical overview and new technology of block structures.  Inf. Tekhnol. Prilozh., 2004, no. 5. 31 p. (In Russian)

8. Valeeva A.F. Constructive heuristics for the rectangular packing problem.  Vestn. Bashkir. Univ., 2006, no. 3, pp. 5–6. (In Russian)

9. Romanovskii I.V. Solution of the guillotine cutting problem by the method of processing the list of states.  Kibernetika, 1969, no. 1, pp. 102–103. (In Russian)

10. Gribov A.B. Algorithm for solving the plain cutting problem.  Kibernetika, 1973, no. 6, pp. 110–115. (In Russian)

11. Romanovskii I.V. Algorithms for Solving Extremal Problems. Moscow, Nauka, 1977. 352 p. (In Russian)

 12. Mukhacheva E.A., Rubinshtein G.Sh. Mathematical Programming. Novosibirsk, Nauka, 1987. 274 p. (In Russian)

13. Lerner E.Yu., Fazylov V.R. Guillotine layout function.  Issled. Prikl. Mat., 1999, vol. 21, pp. 187–196. (In Russian)

14. Andrianova A.A., Mukhtarova T.M., Faazylov V.R. Models of nonguillotine sheet and strip rectangular packing problem.  Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2013, vol. 155, no. 2, pp. 5–18. (In Russian)

15. Andrianova A.A., Mukhtarova T.M., Fazylov V.R. Model of the non-guillotine placement problem of a set of rectangles on a half-strip. Materialy XVII Mezhdunar. konf. Problemy teoreticheskoj kibernetiki [Proc. XVII Int. Conf. Problems of Theoretical Cybernetics]. Kazan, Otechestvo, 2014, pp. 23–26. (In Russian)

16. Andrianova A.A., Mukhtarova T.M., Fazylov V.R. The model of compact placement of a set of rectangles on a sheet. Tez. dokl. XVI Baikal'skoi mezhdunar. shkoly-seminara ``Metody optimizacii i ikh prilozhenija'' [Proc. XVI Baik. Int. Sch.-Semin. Optimization Methods and Their Applications]. Irkutsk, ISEM Sib. Otd. Ross. Akad. Nauk, 2014, p. 33. (In Russian)

 17. Lerner E.Yu., Fazylov V.R. Quasiinverse functions and their properties.  Issled. Prikl. Mat., 1997, vol. 22, pp. 63–74. (In Russian)

18. Humby E. Programs from Decision Tables. London, New York, Macdonald and Co., American Elsevier, 1973. 91 p.

For citation: Andrianova A.A., Mukhtarova T.M., Fazylov V.R. Formation of the guillotine cutting card of a sheet by the guillotine layout functions. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2017, vol. 159, no. 2, pp. 161–173. (In Russian)

The content is available under the license Creative Commons Attribution 4.0 License.