Article

Article title COMBINED GENETIC ALGORITHM FOR A CUTTING PROBLEM
Authors A.N. Orlov, V.V. Kureychik, A.E. Glushchenko
Section SECTION I. EVOLUTIONAL SIMULATION
Month, Year 06, 2016 @en
Index UDC
DOI
Abstract The article deals with one of the most important optimization problems – the cutting stock and packaging (C&P) problem. This problem consists two subproblem, such as two-dimensional packaging and minimization of tool head way. Each of this problems belongs to the class of NP-hard and complex problems. In the article authors offered combined approach for solving this optimization problem based on genetic methods of search. The formulation and restrictions of the C&P problem are considered in the article. Authors offer a combined approach with using multi-level evolution, which partially allows to avoid a preliminary convergence of algorithms. The modified genetic algorithm (MGA) of packaging and the modified genetic algorithm minimization of tool head way is developed, which obtain sets of quasi-optimal solutions in polynomial time. For effective work of genetic algorithms in the article describes process of creation initial population of alternative solutions. Authors offered new codding-decoding algorithm, which allows to receive only the "real" solutions of the optimization problem of cutting stock probleml. To carry out computational experiments on test examples (benchmarks) authors developed a software on the basis of hybrid approach for the C&P problem. Quality of the C&P problem obtained on the basis of the developed hybrid approach is higher on average 2 % than packing results obtained using known algorithms suggested by AJANCAM, Cutter, TEHTRAN, which demonstrates the effectiveness of the proposed approach. Conducted tests and experiments allow possible to clarify theoretical estimations of algorithm time complexity. In the best case algorithms the time complexity is represented as O(n2), in the worst case – O(n3).

Download PDF

Keywords Cutting stock problem; two-dimensional packaging problem; finding of minimum way; combined approach; genetic algorithm; genetic operators; evolutionary algorithm.
References 1. Sherwani N.A. Algorithms for VLSI Physical Design Automation. Third Edition, Kluwer Academic Publisher, USA, 2013.
2. Frolovskiy V.D. Optimal'noe gruppirovanie geometricheskikh ob"ektov pri proektiro-vanii kart raskroya materialov [Optimal grouping of geometric objects saving under maps in the material cutting], Programmnye produkty i sistemy [Software Products and Systems], 2000, No. 3, pp. 47-48.
3. Gladkov L.A. Kureychik V.V., Kureychik V.M. Geneticheskie algoritmy [Genetic algorithms]. Moscow: Fizmatlit, 2010, 368 p.
4. Kureychik V.V., Bova V.V., Kureychik Vl.Vl. Kombinirovannyy poisk pri proektirovanii [Combined search in the design], Obrazovatel'nye resursy i tekhnologii [Educational Resources and Technology], 2014, No. 2 (5), pp. 90-94.
5. Gladkov L.A., Kureychik V.V., Kureychik V.M., Sorokoletov P.V. Bioinspirirovannye metody v optimizatsii [Bioinspired methods in optimization]. Moscow: Fizmatlit, 2009, 384 p.
6. Kureychik V.M., Kureychik L.V. Kompleksnyy metod upakovki blokov [Integrated packing method units], Informatika, vychislitel'naya tekhnika i inzhenernoe obrazovanieb [Computer science, computer engineering and engineering education], 2015, No. 1 (21), pp. 17-26.
7. MukhachevaE.A., Verkhoturov M.A., Martynov V.V. Modeli i metody rascheta raskroya – upakovki geometricheskikh ob"ektov [Models and methods of calculation of cutting – packing of geometric objects]. Ufa: UGATU, 1998, 216 p.
8. Petunin A.A., Polevov A.V., Kurennov D.V. Ob odnom podkhode k resheniyu zadach raskroyaupakovki [About one approach to solving the problems of cutting-packaging], Konstruirovanie i tekhnologiya izgotovleniya mashin: Sbornik nauchnykh trudov [Design and fabrication of machines: Collection of scientific works]. Part 2. Vestnik UGTU – UPI. Ekaterinburg: UGTU – UPI, 2005, No. 18 (70), pp. 212-216.
9. Emel'yanov V.V., Kureychik V.V., Kureychik V.M. Teoriya i praktika evolyutsionnogo
modelirovaniya [Theory and practice of evolutionary simulation]. Moscow: Fizmatlit, 2003, 432 p.
10. Orlov A.N., Kureychik V.V., Kudryakova T.Yu. Geneticheskiy algoritm pryamougol'noy upakovki [Genetic algorithm for rectangular packing], Trudy Kongressa po intellektual'nym sistemam i informatsionnym tekhnologiyam «IS&IT’15» [Proceedings of Congress on intelligent systems and information technologies "IS&IT'15"]. Taganrog: Izd-vo YuFU, 2015, Vol. 3, pp. 207-212.
11. Orlov A.N., Kureychik V.V., Kudryakova T.Yu. Kombinirovannyy algoritm resheniya zadachi pryamougol'nogo raskroya [A combined algorithm for solving the rectangular cutting], Trudy Kongressa po intellektual'nym sistemam i in-formatsionnym tekhnologiyam «IS&IT’15» [Proceedings of Congress on intelligent systems and information technologies "IS&IT'15"]. Scientific publication in 3 vol. Vol. 3. Taganrog: Izd-vo YuFU, 2015, pp. 212-217.
12. Orlov A.N., Kudryakova T.Yu. Kombinirovannyy modifitsirovannyy geneticheskiy algoritm resheniya zadachi raskroya materiala [Combined modified genetic algorithm for solving the problem of nesting material], Fundamental'nye i prikladnye aspekty komp'yuternykh tekhnologiy i informatsionnoy bezopasnosti: Sbornik statey I Vserossiyskoy nauchno-tekhnicheskoy konferentsii molodykh uchenykh, aspirantov i studentov [Fundamental and applied aspects of computer technologies and information security: a Collection of articles I all-Russian scientific-technical conference of young scientists, postgraduates and students], 2015, pp. 417-419.
13. Batishchev D.I., Neymark E.A., Starostin N.V. Primenenie geneticheskikh algoritmov k resheniyu zadach diskretnoy optimizatsii [Application of genetic algorithms to the solution of problems of discrete optimization]. FGUP Nizhegorodskiy gosudarstvennyy universitet im. N.I. Lobachevskogo, 2007.
14. Kureychik V.V., Kureychik Vl.Vl. Bioinspirirovannyy poisk pri proektirovanii i upravlenii [Search inspired by natural systems, for the design and management], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 11 (136), pp. 178-183.
15. Muhlenbein Н. Parallel Genetic Algorithms, Population Genetics and Combinatorial Optimization, Proc. of the Third International Conference on Genetic Algorithms. SanMateo. MorganKaufmann, 1989б 576 p.
16. Podlazova A.V. Geneticheskie algoritmy na primerakh resheniya zadach raskroya [Genetic algorithms on the examples of solving problems cutting], Problemy upravleniya [Problems of Management], 2008, No. 2, pp. 58-63.
17. Falkenauer Е.A. Genetic Algorithm for Bin Packing and Time Balancing, In: Proc. Of the IEEE 1992 International Conference on Robotics and Automation (RA92), Nice, 1992.
18. Orlov A.N. Kureychik V.V. Mekhanizm kodirovaniya-dekodirovaniya pri reshenii zadachi pryamougol'nogo raskroya-upakovki materiala [The mechanism of encoding-decoding when solving tasks of the rectangular cutting-packing material], Sbornik nauchnykh statey Vserossiyskoy molodezhnoy shkoly seminara «Aktual'nye problemy informatsionnykh tekhnologiy, elektroniki i radiotekhniki - 2015» [Collection of scientific articles of the all-Russian youth school-seminar "Actual problems of information technologies, electronics and radio engineering - 2015"]. Taganrog: Izd-vo NOTs ZIS KT YuFU, 2015, pp. 420-428.
19. Kuliev E.V. Dukkardt A.N, Kureychik V.V. Legebokov A.A. Neighborhood Research Approach in Swarm Intelligence for Solving the Optimization Problems, Proceedings of IEEE East-West Design & Test Symposium – (EWDTS’2014) Kiev, Ukraine, September 26–29, 2014, pp. 112-115.
20. Garey M.R.,Graham R.L., Johnson D.S., Yao A.C. Resource constrained scheduling as generalized bin packing, J. CombinatorialTheory. Ser. A21, pp. 257-298.

Comments are closed.