Transactions of Materials and Heat Treatment

Title：Rectangular workpiece nesting based on an improved genetic algorithm of composite evaluation factor

Authors： Luo Qiang Li Shihong Yuan Yuelan Rao Yunqing Liu Quanhu

Unit： Huazhong University of Science and Technology Guizhou Communications Polyteching

KeyWords： genetic algorithm the lowest horizontal line rectangular workpiece nesting composite evaluation factor fitness

ClassificationCode：TP391

year,vol(issue):pagenumber：2018,43(2):0-0

Abstract：

The rectangular workpiece nesting is a combinational optimization problem of NP-Hard. Because its computation complexity is increased with the number of rectangles sharply, it is difficult to obtain an exact solution within an acceptable time. Based on the lowest horizontal algorithm , considering the effect factors of height, width and area of rectangular，a composite evaluation factor was presented to evaluate the rectangle，and the superior rectangle was opted to be nested. Then, the local searching capability of genetic algorithm was improved by reasonable genetic operators，and the nesting quality of rectangle was improved. Being widely used in the example N and C, the experiment result shows that the average best relative distance is lower than that of GA+BLF and SA+BLF algorithm by 70% and 55% respectively. Thus, the approach is effective, efficient and stable.

Funds：

国家重点基础研究发展计划(2014CB046705)

作者简介：罗强（1994-），男，硕士研究生 E-mail：luoqiang0002@163.com 通讯作者：饶运清（1968-），男，博士，教授 E-mail：ryq@hust.edu.cn

Reference：

［1］Baker B S, Coffman E G J, Rivest R L. Orthogonal packings in two dimensions
［J］. Siam Journal on Computing, 1980,9(4):846-855.

［2］Hopper E, Turton B. A genetic algorithm for a 2D industrial packing problem
［J］. Computers and Industrial Engineering, 1999, 37(1-2):375-378.

［3］刘德全，滕弘飞. 矩形件排样问题的遗传算法求解
［J］. 小型微型计算机系统，1998，19(12)：20-25.

Liu D Q, Teng H F.On gnentic algorithm for the orthogonal packing of rectangles
［J］. Journal of Chinese Computer Systems, 1998, 19(12): 20-25.

［4］贾志欣，殷国富，罗阳. 二维不规则零件排样问题的遗传算法求解
［J］. 计算机辅助设计与图形学学报，2002，14(5)：467-470.

Jia Z X, Yin G F, Luo Y. Two-dimensional irregular parts packing with genetic algorithm
［ J］ .Journal of Computer-Aided Design & Computer Graphics, 2002, 14(5):467-470.

［5］Christoforos C, Fleszar K. A constructive bin-oriented heuristic for the two-dimensional bin packing problem with guillotine cuts
［J］. Computers & Operations Research, 2011, 38(10): 1443-1451.

［6］贾志欣，殷国富，罗阳，等. 矩形件排样的模拟退火算法求解
［J］. 四川大学学报：自然科学版，2001，33(5)：35-38.

Jia Z X, Yin G H, Luo Y, et al. Application of simulated annealing to the rectangular packing problem
［J］ Journal of Sichuan University：Engineering Science Edition, 2001, 33(35): 35-38.

［7］Chiong R, Dhakal S. Natural Intelligence for Scheduling, Planning and Packing Problems
［M］. Heidelberg: Springer Berlin Heidelberg, 2009.

［8］Babaog⌒lu I. Solving 2D strip packing problem using fruit fly optimization algorithm
［J］.Procedia Computer Science, 2017,111: 52-57.

［9］Wei L J, Hu Q, Leung S C H, et al. An improved skyline based heuristic for the 2D strip packing problem and its efficient implementation
［J］. Computers & Operations Research, 2017, 80(Supplement C): 113-127.

［10］Liu H, Zhou J, Wu X, et al. Optimization algorithm for rectangle packing problem based on varied-factor genetic algorithm and lowest front-line strategy
［A］.2014 IEEE Congress on Evolutionary Computation (CEC)
［C］. Beijing, 2014.

［11］龚志辉. 基于遗传算法的矩形件优化排样系统研究
［D］.长沙：湖南大学，2003.

Gong Z H. Research On the Genetic Algorithm for the Rectangular Optimal Packing System
［D］. Changsha： Hunan University, 2003.

［12］赵新芳，崔耀东，杨莹,等. 矩形件带排样的一种遗传算法
［J］. 计算机辅助设计与图形学学报，2008，20(4)：540-544.

Zhao X F, Cui Y D, Yang Y, et al. A genetic algorithm for rectangle strip packing problem
［J］. Journal of Computer-Aided Design & Computer Graphics, 2008,20 (4):540-544.

［13］刘海明，周炯，吴忻生,等. 基于改进最低水平线方法与遗传算法的矩形件排样优化算法
［J］. 图学学报，2015，36(4)：526-531.

Liu H M, Zhou J, Wu X S, et al. Optimization algorithm for rectangle packing based on improved lowest horizontal line method and genetic algorithm
［J］. Journal of Graphics, 2012, 36(4):526-531.

［14］孙佳正，郭骏. 改进的双种群遗传算法在矩形件排样中的应用
［J］. 计算机工程与应用，http://kns.cnki.net/ KCMS/detail/11.2127.TP.20170824.0954.034.html.

Sun J Z, Guo J. Improved dual population genetic algorithm for rectangle packing
［J］. Computer Engineering and Applications, http://kns.cnki.net/KCMS/detail/11.2127.TP.20170824.0954. 034.html.

［15］Wscher G, Schumann H. An improved typology of cutting and packing problems
［J］.European Journal of Operational Research,2007, 183(3):1109-1130.

［16］Burke E K, Kendall G, Whitwell G. A new placement heuristic for the orthogonal stock-cutting problem
［J］. Operations Research, 2004,52(4):655-671.

［17］赵晓东，米小珍. 遗传算法模型在矩形件排样优化中的应用
［J］. 锻压技术，2007，32(6)：153-156.

Zhao X D, Mi X Z. Application of genetic algorithm model in optimal layout of rectangular part
［J］. Forging ＆ Stamping Technology, 2007, 32(6):153-156.

［18］Hopper E, Turton B C H. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem
［J］. European Journal of Operational Research, 2001, 128(1): 34-57

［19］Wei L, Lim A, Zhu W. A skyline-based heuristic for the 2D rectangular strip packing problem
［J］. Modern Approaches in Applied Intelligence, 2011, 6704: 286-295.

［20］Alvarez R. Reactive GRASP for the strip-packing problem
［J］. Computers & Operations Research, 2008, 35(4): 1065-1083.

［21］Wei L, Qin H, Cheang B, et al. An efficient intelligent search algorithm for the two-dimensional rectangular strip packing problem
［J］. International Transactions in Operational Research, 2014, 23(1-2): 65-92.

［22］Leung S C H, Zhang D, Sim K M. A two-stage intelligent search algorithm for the two-dimensional strip packing problem
［J］. European Journal of Operational Research, 2011, 215(1): 57-69.

［23］Yang S, Han S, Ye W. A simple randomized algorithm for two-dimensional strip packing
［J］. Computers & Operations Research,2013, 40(1): 1-8.

Service：

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