1.东北林业大学机电工程学院，黑龙江哈尔滨 150040
扫 描 看 全 文
刘诚,孙远升,花军等.基于贪心算法及局部枚举策略的人造板排样方案研究[J].木材科学与技术,2021,35(06):55-61.
LIU Cheng,SUN Yuan-sheng,HUA Jun,et al.Research on Wood-based Panel Cutting Program Based on a Greedy Algorithm with an Enumeration Strategy[J].Chinese Journal of Wood Science and Technology,2021,35(06):55-61.
人造板排样问题主要为“一刀切”约束下的矩形排样问题，本文通过局部枚举求解的方法，分析原料利用率、运算时间与工件排样顺序之间的关系，并提出贪心排样方案。检测结果表明，工件排样顺序对原料利用率影响较小，原料利用率变化在0.05%以内，但运算时间随着枚举空间扩大而呈现指数级上升；与文献中二叉树排样算法对比，本文算法可提高1.3%的原料板利用率，降低30.8%的余料数量。
The cutting of wood-based panels is rectangular cutting under the restrained guillotine. It is solved by a local enumeration through a greedy strategy. The relationship among the utilization rate of the raw material board, the computing time, and the cutting sequence of the work pieces is analyzed. A greedy cutting algorithm is proposed. The experimental results show that the cutting sequence of the workpieces has little effect on the utilization rate of the raw board, and the utilization rate of the raw board changes within 0.05%, but the calculation time increases exponentially with the expansion of the enumeration space. Comparing with the literature, the algorithm can improve the raw material board utilization rate by 1.3%; the remaining material quantity is reduced by 30.8%.
人造板排样贪心算法枚举排样“一刀切”检测
wood-based panel cuttinggreedy algorithmcutting of enumerationdetection of guillotine
吕斌, 贾东宇. 现代家居对人造板产品的新要求[J]. 木材工业, 2016, 30(2): 7-10.
LYU B, JIA D Y. New requirements for wood-based panel products in modern housing[J]. China Wood Industry, 2016, 30(2): 7-10.
叶克林. 当前我国人造板工业面临的新挑战[J]. 木材工业, 2016, 30(2): 4-6.
YE K L. New challenges faced by wood-based panel industry in China[J]. China Wood Industry, 2016, 30(2): 4-6.
戈鹏, 邱厌庆, 刘柱胜, 等. 一刀切问题的优化二叉树排样[J]. 计算机集成制造系统, 2011, 17(2): 329-337.
GE P, QIU Y Q, LIU Z S, et al. Optimized binary tree packing of guillotine problem[J]. Computer Integrated Manufacturing Systems, 2011, 17(2): 329-337.
曹大勇, 杨梅, 科托夫·弗拉基米尔·米哈伊拉维奇, 等. 二维一刀切装箱问题的两阶段启发式算法[J]. 计算机集成制造系统, 2012, 18(9): 1954-1963.
CAO D Y , YANG MV. M..Kotov,et al. Two-stage heuristic algorithm for two-dimensional guillotine Bin packing problem[J]. Computer Integrated Manufacturing Systems, 2012, 18(9): 1954-1963.
Vassiliadis V S. Two-dimensional stock cutting and rectangle packing: binary tree model representation for local search optimization methods[J]. Journal of Food Engineering, 2005, 70(3): 257-268.
Fleszar K. Three insertion heuristics and a justification improvement heuristic for two-dimensional Bin packing with guillotine cuts[J]. Computers & Operations Research, 2013, 40(1): 463-474.
李波, 王石, 施松新, 等. 基于启发式动态分解算法的矩形件优化排样[J]. 计算机应用, 2013, 33(7): 1908-1911.
LI B, WANG S, SHI S X, et al. Optimum packing of rectangles based on heuristic dynamic decomposition algorithm[J]. Journal of Computer Applications, 2013, 33(7): 1908-1911.
潘卫平, 张瑞友. 矩形件简单块占角排样方式的动态规划[J]. 中国图象图形学报, 2019, 24(6): 934-945.
PAN W P, ZHANG R Y. Dynamic programming algorithm for simple block corner-occupying pattern of rectangular blanks[J]. Journal of Image and Graphics, 2019, 24(6): 934-945.
Scheithauer G, Sommerweiß U. 4-Block heuristic for the rectangle packing problem[J]. European Journal of Operational Research, 1998, 108(3): 509-526.
罗运贞, 潘立武. 约束剪切问题的三块排样方式及其生成算法[J]. 锻压技术, 2018, 43(10): 185-189.
LUO Y Z, PAN L W. Three-block layout pattern and its generation algorithm of constrained cutting problem[J]. Forging & Stamping Technology, 2018, 43(10): 185-189.
何双池, 陈学松. 二维矩形件排样的切割式填充算法[J]. 数学的实践与认识, 2019, 49(18): 132-139.
HE S C, CHEN X S. Cut-filling algorithm of 2D rectangle packing[J]. Mathematics in Practice and Theory, 2019, 49(18): 132-139.
Hifi M, Roucairol C. Approximate and exact algorithms for constrained (un) weighted two-dimensional two-staged cutting stock problems[J]. Journal of Combinatorial Optimization, 2001, 5(4): 465-494.
曹炬, 周济, 余俊. 矩形件排样优化的背包算法[J]. 中国机械工程, 1994, 5(2): 11-12, 79.
CAO J, ZHOU J, YU J. Knapsack algorithm for layout optimization of rectangular pieces on stock[J]. China Mechanical Engineering, 1994, 5(2): 11-12, 79.
曾兆敏, 王祺, 潘立武. 冲压条带二维优化排样问题的一种启发式算法[J]. 锻压技术, 2018, 43(7): 204-208.
ZENG Z M, WANG Q, PAN L W. A heuristic algorithm for two-dimensional optimal nesting problem of stamping strips[J]. Forging & Stamping Technology, 2018, 43(7): 204-208.
彭碧涛, 周永务. 求解2D条带矩形packing问题的迭代启发式算法[J]. 软件学报, 2012, 23(10): 2600-2611.
PENG B T, ZHOU Y W. Recursive heuristic algorithm for the 2D rectangular strip packing problem[J]. Journal of Software, 2012, 23(10): 2600-2611.
许华杰, 檀洪森, 胡小明. 基于AGA和集中剩余矩形区域策略的排样方法研究[J]. 计算机应用研究, 2016, 33(11): 3235-3239.
XU H J, TAN H S, HU X M. Research of packing method based on AGA and concentrated surplus rectangle area strategy[J]. Application Research of Computers, 2016, 33(11): 3235-3239.
赵新芳, 崔耀东, 杨莹, 等. 矩形件带排样的一种遗传算法[J]. 计算机辅助设计与图形学学报, 2008, 20(4): 540-544.
ZHAO X F, CUI Y D, YANG Y, et al. A genetic algorithm for the rectangular strip packing problem[J]. Journal of Computer-Aided Design & Computer Graphics, 2008, 20(4): 540-544.
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.
Sotelo-Figueroa M A, Puga Soberanes H J, Carpio J M, et al. Improving the Bin packing heuristic through grammatical evolution based on swarm intelligence[J]. Mathematical Problems in Engineering, 2014, DOI:10.1155/2014/545191http://dx.doi.org/10.1155/2014/545191.
梁利东, 贾文友. 基于宽容分层策略的启发式排样算法[J]. 计算机应用, 2018, 38(4): 1195-1200.
LIANG L D, JIA W Y. Heuristic packing algorithm based on forbearing stratified strategy[J]. Journal of Computer Applications, 2018, 38(4): 1195-1200.
宋连超, 朱建良, 张彤. 矩形件排样优化贪婪算法及系统开发[J]. 哈尔滨理工大学学报, 2007(1): 29-31, 35.
SONG L C, ZHU J L, ZHANG T. Research and development on the greedy algorithm and system of the rectangular cutting stock problem[J]. Journal of Harbin University of Science and Technology, 2007(1): 29-31, 35.
相关文章
相关作者
相关机构
京公网安备11010802024621
微信公众号