|
Abstract：
|
|
For the problem of rectangular workpiece layout, a new hybrid optimization algorithm was proposed by combining blank rectangle filling and neighborhood search algorithms. Firstly, when the blank rectangle filling algorithm was designed, a method to eliminate extra blank rectangles was proposed to reduce the computation time complexity. Secondly, two kinds of neighborhood operators such as crossover and insertion of the limited distance are designed when the layout order of rectangular workpieces was optimized by using neighborhood search algorithm according to the characteristics of the problem. In addition, the execution point selection strategy of special operators was proposed. Then, a neighborhood search algorithm was implemented based on alternating iteration of two neighborhood operators. Finally, the experiment calculations of twenty-one classical cases in literature show that the layout utilization rate of four cases is up to 100%, the layout utilization rate of most cases exceeds 99%, and the minimum layout utilization rate exceeds 98%. Compared with other algorithms commonly used in the literature, the effectiveness of the proposed algorithm was verified. At the same time, eight actual cases provided by a building materials processing enterprise were tested and calculated, and the average difference between the obtained layout utilization rate and the ideal optimal layout utilization rate is 1.7% to indicate the practicability of the algorithm in this paper.
|
|
Funds：
|
|
湖北省教育厅科学技术研究计划指导性项目（B2016171）
|
|
AuthorIntro：
|
|
陈仕军（1980-），男，博士，讲师，E-mail：csj@hbuas.edu.cn；通讯作者：许继影（1980-），女，硕士，讲师，E-mail:xjy@hbuas.edu.cn
|
|
Reference：
|
[1]Oliveira J F, Alvaro N J, Silva E M, et al. A survey on heuristics for the two-dimensional rectangular strip packing problem[J]. Pesquisa Operacional, 2016, 36(2):197-226.
[2]王睿，崔轶平，崔耀东，等.PCB多工作板尺寸单一下料精确算法[J]. 锻压技术，2019,44(3):17-23.
Wang R，Cui Y P，Cui Y D，et al. Exact algorithm of single cutting for PCB multi-working plate size[J]. Forging & Stamping Technology，2019,44(3):17-23.
[3]Baker B S, Coffman E G, Rivest R L. Orthogonal packings in two dimensions[J]. SIAM Journal on Computing, 1980, 9(4):846-855.
[4]Hopper E, Turton B C H. A genetic algorithm for a 2D industrial packing problem[J]. Computers & Industrial Engineering, 1999, 37(1-2)：375-378.
[5]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.
[6]Leung S C H, Zhang D F. A fast layer-based heuristic for non-guillotine strip packing[J]. Expert Systems with Applications, 2011,38(10):13032-13042.
[7]Chen Z, Chen J. An effective corner increment-based algorithm for the two-dimensional strip packing problem[J]. IEEE Access, 2018, 6:72906-72924.
[8]邓见凯,王磊,尹爱华. 一种求解二维矩形Packing问题的拟人型全局优化算法[J]. 计算机工程与科学, 2018, 40(2): 331-340.
Deng J K, Wang L, Yin A H. A quasi-human global optimization algorithm for solving the two dimensional rectangular packing problem[J]. Computer Engineering and Science, 2018, 40(2): 331-340.
[9]王凌. 智能优化算法及其应用[M]. 北京：清华大学出版社，2001.
Wang L. Intelligence Optimization Algorithm and Its Application[M]. Beijing: Press of Tsinghua University, 2001.
[10]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.
[11]Babalik A. Implementation of bat algorithm on 2D strip packing problem[A]. Lavangnananda K, Phon-Amnuaisuk S, Engchuan W, et al. Proceedings in Adaptation, Learning and Optimization[C].Switzerland：Springer International Publishing，2016.
[12]Babaoglu I. Solving 2D strip packing problem using fruit fly optimization algorithm[J]. Procedia Computer Science, 2017, 111:52-57.
[13]许继影,陈仕军,郑晴. 基于两阶段排放算法的矩形件排样优化方法[J]. 计算机时代, 2020, (5):13-15,19.
Xu J Y, Chen S J, Zheng Q. Optimal rectanglepacking based on two-stage placing algorithm[J]. Computer Eta, 2020,(5):13-15,19.
[14]Anand K V, Babu A R. Heuristic and genetic approach for nesting of two-dimensional rectangular shaped parts with common cutting edge concept for laser cutting and profile blanking processes[J]. Computers & Industrial Engineering, 2015, 80(2):111-124.
[15]刘海明,周炯,吴忻生,等. 基于改进最低水平线方法与遗传算法的矩形件排样优化算法[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, 2015, 36(4):526-531.
[16]范展,梁国龙,林旺生,等. 求解TSP问题的自适应邻域搜索法及其扩展[J].计算机工程与应用, 2008, (12):75-78.
Fan Z, Liang G L, Lin W S, et al. Design and expending of adaptive neighborhood searching algorithm for TSP[J]. Computer Engineering and Applications, 2008, (12):75-78.
[17]李妍峰,李军,高自友. 大规模邻域搜索算法求解时变车辆调度问题[J]. 管理科学学报, 2012, 15(1):22-32.
Li Y F, Li J, Gao Z Y. Very large scale neighborhood search algorithm for solving time dependent vehicle routing problem[J]. Journal of Management Sciences in China, 2012, 15(1):22-32.
|
|
Service：
|
|
【This site has not yet opened Download Service】【Add
Favorite】
|
|
|
|
Copyright Forging & Stamping Technology.All rights reserved