Formation of the guillotine cutting card of a sheet by the guillotine layout functions

A. A. Andrianova   ; T. M. Mukhtarova   ; V. R. Fazylov

Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 159 (2017) no. 2, pp. 161-173

Résumé

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

Détail

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

Bibliographie

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

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

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

[4] Lodi A., Martello S., Monaci M., “Two-dimensional packing problems: A survey”, Eur. J. Oper. Res., 141:2 (2002), 241–252 | DOI | MR | Zbl

[5] Zhang D. F., Kang Y., Deng S., “A new heuristic recursive algorithm for the strip rectangular packing problem”, Comput. Operat. Res., 33:8 (2006), 2209–2217 | DOI | MR | Zbl

[6] Chen M., Huang W., “A two-level search algorithm for 2D rectangular packing problem”, Comput. Ind. Eng., 53:1 (2007), 123–136 | DOI

[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 pp. (In Russian)

[8] Valeeva A. F., “Constructive heuristics for the rectangular packing problem”, Vestn. Bashkir. Univ., 2006, no. 3, 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, 102–103 (In Russian)

[10] Gribov A. B., “Algorithm for solving the plain cutting problem”, Kibernetika, 1973, no. 6, 110–115 (In Russian) | Zbl

[11] Romanovskii I. V., Algorithms for Solving Extremal Problems, Nauka, Moscow, 1977, 352 pp. (In Russian) | MR

[12] Mukhacheva E. A., Rubinshtein G. Sh., Mathematical Programming, Nauka, Novosibirsk, 1987, 274 pp. (In Russian) | MR

[13] Lerner E. Yu., Fazylov V. R., “Guillotine layout function”, Issled. Prikl. Mat., 21, 1999, 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, 155, no. 2, 2013, 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”, Proc. XVII Int. Conf. Problems of Theoretical Cybernetics, Otechestvo, Kazan, 2014, 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”, Proc. XVI Baik. Int. Sch.-Semin. Optimization Methods and Their Applications, ISEM Sib. Otd. Ross. Akad. Nauk, Irkutsk, 2014, 33 (In Russian)

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

[18] Humby E., Programs from Decision Tables, Macdonald and Co., American Elsevier, London–New York, 1973, 91 pp. | Zbl