Transactions of Materials and Heat Treatment

Title：A hybrid genetic algorithm on two-dimensional orthogonal layout for rectangular parts

Authors：

Unit：

KeyWords：

ClassificationCode：TP391

year,vol(issue):pagenumber：2021,46(10):106-111

Abstract：

The two-dimensional orthogonal layout problem of rectangular parts was discussed, namely, a group of small rectangular parts with known sizes were orthogonally arranged into a large rectangular plate, and a layout method was found to maximize the utilization rate of plate. A hybrid genetic algorithm was proposed by combining the genetic algorithm based on random key values with the layout strategy. Then, the layout sequence of rectangular parts was determined by hybrid genetic algorithm. According to the layout sequence, the rectangular parts were arranged into the plate one by one. When each time the rectangular parts were arranged, a best free rectangular space was selected from the set of free rectangular space to layout the current rectangular parts to be arranged, and the extra free space was divided into two sub-free spaces along the upper and right sides of the rectangular part. Furthermore, the sub-free space was added to the set of free rectangular space, and the layout operation of the next rectangular part to be arranged was continued according to the above rules until the plate could no longer be arranged into the rectangular part. Finally, the algorithm was tested by benchmark examples in the literature and compared with the literature algorithm. Experimental results show that this algorithm is better than two typical literature algorithms.

Funds：

广西2020年度中青年教师基础能力提升项目(2020KY41016)；广西农业职业技术大学2021年科学研究与技术开发计划课题（YKJ2124）

作者简介：唐伟萍（1983-），女，硕士，副教授 E-mail：hxnz2002@126.com 通信作者：王坤（1985-），男，硕士，副教授 E-mail：wkscgy01@163.com

Reference：

[1]Gonalves J F, Resende M G C. A parallel multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem[J]. Journal of Combinatorial Optimization, 2011, 22(2): 180-201.

[2]Ayadi O, Masmoudi M, Ben Ameur M, et al. A new PSO-based algorithm for two-dimensional non-guillotine non-oriented cutting stock problem[J]. Applied Artificial Intelligence, 2017, 31(4): 376-393.

[3]Ma N, Zhou Z. Mixed-integer programming model for two dimensional non-guillotine bin packing problem with free rotation[A]. 2017 4th International Conference on Information Science and Control Engineering (ICISCE) [C]. IEEE, 2017.

[4]Alvarez-Valdés R, Parajón A. A tabu search algorithm for large-scale guillotine (un) constrained two-dimensional cutting problems[J]. Computers & Operations Research, 2002, 29(7): 925-947.

[5]Hadjiconstantinou E, Iori M. A hybrid genetic algorithm for the two-dimensional single large object placement problem[J]. European Journal of Operational Research, 2007, 183(3): 1150-1166.

[6]Russo M, Sforza A, Sterle C. An exact dynamic programming algorithm for large-scale unconstrained two-dimensional guillotine cutting problems[J]. Computers & Operations Research, 2014, 50: 97-114.

[7]Wei L, Lim A. A bidirectional building approach for the 2D constrained guillotine knapsack packing problem[J]. European Journal of Operational Research, 2015, 242(1): 63-71.

[8]Martin M, Birgin E G, Lobato R D, et al. Models for the two-dimensional rectangular single large placement problem with guillotine cuts and constrained pattern[J]. International Transactions in Operational Research, 2020, 27(2): 767-793.

[9]刘小可, 扈少华, 邓国斌. 基于普通块的四块排样方式及其生成算法[J]. 锻压技术, 2019, 44(11): 51-56.

Liu X K, Hu S H, Deng G B. Four-ordinary-block cutting pattern and its generation algorithmg[J]. Forging & Stamping Technology, 2019, 44(11): 51-56.

[10]Birgin E G, Lobato R D, Morabito R. Generating unconstrained two-dimensional non-guillotine cutting patterns by a recursive partitioning algorithm[J]. Journal of the Operational Research Society, 2012, 63(2): 183-200.

[11]Shiangjen K, Chaijaruwanich J, Srisujjalertwaja W, et al. An iterative bidirectional heuristic placement algorithm for solving the two-dimensional knapsack packing problem[J]. Engineering Optimization, 2018, 50(2): 347-365.

[12]Wscher G, Hauβner H, Schumann H. An improved typology of cutting and packing problems[J]. European Journal of Operational Research, 2007, 183(3):1109-1130.

[13]Mellouli A, Mellouli R, Masmoudi F. An innovative genetic algorithm for a multi-objective optimization of two-dimensional cutting-stock problem[J]. Applied Artificial Intelligence, 2019, 33(6): 531-547.

[14]Laabadi S, Naimi M, El Amri H, et al. A crow search-based genetic algorithm for solving two-dimensional bin packing problem[A]. Joint German/Austrian Conference on Artificial Intelligence (Künstliche Intelligenz) [C]. Springer, Cham, 2019.

[15]Lai K K, Chan W M. An evolutionary algorithm for the rectangular cutting stock problem[J]. International Journal of Industrial Engineering: Theory Applications and Practice, 1997, 4(2): 130-139.

Service：

【This site has not yet opened Download Service】【Add Favorite】