C&SA | Contents

Volume 55 >>> № 6 NOVEMBER — DECEMBER 2019

UDC 519.87

I.V. Kozin¹, S.E. Batovskiy²

¹ Zaporizhzhya National University, Zaporizhzhya, Ukraine

² Zaporizhzhya National University, Zaporizhzhya, Ukraine

FRAGMENTARY STRUCTURES IN TWO-DIMENSIONAL STRIP PACKING PROBLEM

Abstract. The paper considers a two-dimensional strip packing problem. It is shown that the problem can be considered as an optimization problem on a fragmented structure, which reduces to the problem of combinatorial optimization on a set of permutations. A universal approach of representing two-dimensional figures and the algorithm of their packing into the strip are considered. An approach to the modification of the original problem for the attainability of the optimal solution is proposed.

Keywords: discrete optimization, fragmentary structure, two-dimensional strip packing, evolutionary algorithm.

FULL TEXT

REFERENCES

Garey M., Johnson D. Computing machines and hard problems [Russian translation]. Moscow: Mir, 1982. 416 p.

Glover F., Taillard E., de Werra D. A user’s guide to tabu search. Annals of Operation Research. 1993. Vol. 41, Iss. 1. P. 1–28.

Holland J.H. Adaptation in natural and artificial systems. Boston, MA: MIT Press, 1992. 288 p.

Kureichik V.M. Genetic Algorithms. Condition. Problems. Prospects. Proceedings of the RAS. Theory and control systems. 1999. N 1. P. 144–160.

Gonсalves J.F. A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem. European Journal of Operational Research. 2007. Vol. 183, N 3. P. 1212–1229.

Shtovba S.D. Ant algorithms: theory and application. Programmirovaniye. 2005. N 4. P. 1–16.

Dorigo М. Optimization, learning, and natural algorithms. PhD Thesis, Dipartimento di Elettronica, Politechnico di Milano, Italy, 1992. 140 p.

Lodi A., Martello S., Monaci M. Two-dimensional packing problems: A survey. European Journal of Operation Research. 2002. Vol. 141, N 2. P. 241–252.

Jain S., Gea H.C. Two dimensional packing problems using genetic algorithms. Engineering with Computers. 1998. Vol. 14, N 3. P. 206–213.

Vanidovsky V.A., Lebedev O.B. Two-dimensional packaging in a semi-limited strip based on modeling the adaptive behavior of an ant colony. News SFU. Technical science. 2014. N 7 (156). P. 34–42.

Kartak V.M. The problem of packing rectangles. Exact matrix based algorithm. Bulletin of USATU. 2007. Vol. 9, N 4 (22). P. 104–110.

Rudnev A.S. Probabilistic search with prohibitions for the problem of packing circles and rectangles in a strip. Diskretnyy analiz i issledovaniye operatsiy. 2009. Vol. 16, N 4. P. 61–86.

Stoyan Yu.G., Zlotnik M.V. Placement of circles and non-convex polygons with rotations in a rectangle of minimum length. Dopovіdі National Academy of Sciences of Ukraine. 2007. N 2. P. 37–42.

Kozin I.V., Maksishko N.K., Perepelitsa V.A. Fragmented structures in discrete optimization problems. Kibernetika i sistemnyj analiz. 2017. Vol. 53, N 6. P. 125–131.

Kozin I.V. An evolutionary-fragmented model of the pentamino packing problem. Diskretnyj analiz i issledovaniye operatsiy. 2014. Vol. 21, N 6. P. 35–50.

Romanova T.E., Stupak E.A., Zlotnik M.V. Mathematical model and method for solving the problem of optimizing the packaging of arbitrary two-dimensional objects in rectangular areas. Dopovіdі National Academy of Sciences of Ukraine. 2009. N 1. P. 48–53.