浏览全部资源
扫码关注微信
Received：09 October 2018，
Revised：2018-12-4，
Published：16 June 2019
移动端阅览
目的
2
针对矩形件无约束2维剪切排样问题，提出一种可简化板材切割工艺的简单块占角排样方式，并构造这种排样方式的动态规划生成算法。
方法
2
该排样方式在板材左下角按照简单块方式排样若干行若干列同种矩形件，将板材剩余部分划分为两个子板；将子板按照上述方法继续递归排样和划分，直至子板排满矩形件为止。采用动态规划确定所有可能尺寸的板材左下角排样的最优矩形件、矩形件的最优行列数和板材剩余部分的最优子板划分。运用规范尺寸排除不必要的计算。
结果
2
将本文算法与目前常见的算法进行比较，实验结果表明本文算法计算时间合理，排样价值较高。在第1组41道基准例题中，本文算法所有例题均求出了精确解，同质块T型算法、同质块两段算法和复合条带两段算法分别有7道、5道和4道例题未求出精确解。在第2组20道基准例题中，本文算法只有1道例题未求出精确解，普通三阶段算法、同质块T型算法、同质块两段算法和匀质条带三块算法分别有18道、15道、15道和20道例题未求出精确解。在第3组50道随机例题中，本文算法、普通两段算法和同质块两段算法板材利用率分别为99.913 7%、99.862 3%和99.796 1%。在第4组31道基准例题中，本文算法所有例题均求出了精确解，普通占角排样算法有2道例题未求出精确解。
结论
2
本文算法计算时间远小于精确算法，优化效果接近精确算法；本文算法计算时间与多种启发式算法接近，但优化效果好于多种启发式算法。
Objective
2
In industrial production
we often encounter 2D cutting problems
such as the cutting process of metal sheet
glass
and plywood. A good cutting pattern can effectively simplify the cutting process
improve the utilization rate of metal sheets
reduce resource consumption
and reduce the production costs of enterprises. The 2D cutting problem can be categorized into rectangular and other shape cutting problems according to the geometric shape of the workpiece. According to whether the workpiece can rotate
the same problem can be classified as rotatable and non-rotatable. According to the number of times each workpiece can appear in the sheet
it can be divided into constrained and unconstrained cutting problems. According to whether the cutting process of blanking meets the requirement of guillotine cuts
it can be categorized into guillotine and non-guillotine cutting problems. This study focuses on the unconstrained 2D guillotine cutting problem of rectangular pieces (UTGCR)
which refers to cutting a sheet into several rectangular pieces of different sizes and values
and the number of occurrences of each rectangular piece in the sheet is unconstrained. The optimization goal of this problem is to maximize the total value of rectangular pieces cut out of the sheet. The cutting stock algorithm iteratively calls the cutting algorithm to generate the cutting pattern of rectangular pieces on a sheet. After a new cutting pattern is generated
the number of times of using the new cutting pattern is determined by the residual demand of rectangular pieces. The value of the rectangle is corrected by the number of the rectangular pieces included in the new cutting pattern to make the subsequent cutting pattern reasonable. A good cutting algorithm can improve the material utilization of the sheet
reduce resource consumption
reduce production costs and improve the competitiveness of enterprises. From the viewpoint of computational complexity
UTGCR is a complex combinatorial optimization problem with NP complexity. The exact algorithm takes too long to solve large-scale problems and cannot meet practical application requirements because the solution space of the feasible cutting pattern is large. In practice
heuristic algorithms are generally used to solve UTGCR problems
which can be divided into two categories according to the construction idea of the algorithms. The first is the intelligent optimization algorithm
which is widely used in rectangular nonguillotine cutting problems and relatively less used in UTGCR problems. Guaranteeing the quality of the solution is difficult because of the unknown convergence of the algorithm. In addition
the structure of the cutting pattern is complex
which is not conducive to the sheet cutting process. The second is to reduce the solution space and computational complexity of the algorithm by restricting the cutting pattern to satisfy a certain geometric characteristic. Although this kind of algorithm is not guaranteed to obtain the optimal solution
it is widely used because of its minimal calculation time and simple layout structure
which is conducive to the sheet cutting process. A simple block corner-occupying pattern that can simplify the sheet-cutting process is presented
and a dynamic programming algorithm for generating this pattern is constructed.
Method
2
The dynamic programming principle is used to construct a simple block corner-occupying pattern with different sizes of sub sheets one by one from small to large. The pattern information of sub sheets with small sizes can be directly used when constructing the sub sheet with current sizes. A simple block corner-occupying pattern is obtained when the simple block corner-occupying pattern of the sub sheet
L
×
W
is obtained. With this pattern
several rows and columns of identical pieces are packed at the lower left corner of the sheet according to a simple block mode. The remaining part of the sheet is divided into two sub sheets. Recursive packing and partitioning of the sub sheet are continued according to the above method until the sub sheets are fully filled with rectangular pieces. A dynamic programming algorithm is used to determine the optimal piece type
the optimal number of rows and columns of pieces
and the optimal partitioning of the remaining part of the all possible sheet sizes. The normal size is used to exclude unnecessary calculations.
Result
2
Five groups of instances in literature are used. The first
second
and fourth groups are international benchmark instances
which can be found at
http://www.laria.u-picardie.fr/hifi/OR-Benchmark
http://www.laria.u-picardie.fr/hifi/OR-Benchmark
. The third group comprises random instances
and the fifth group consists of actual production instances. After comparing the algorithm in this study with the algorithms in common literature
experimental results show that the algorithm in this study has more reasonable calculation time and higher pattern value. In the first set of 41 benchmark instances
the algorithm in this study has found the exact solution to all instances
whereas the homogeneous block T-shape
homogeneous block two-segment
and compound strip two-segment algorithms have not found the exact solution of seven
five
and four instances
respectively. In the second set of 20 benchmark instances
only one has not been solved accurately by the algorithm in this study. A total of 18
15
15
and 20 instances have not been solved accurately by the common three-stage
homogeneous block T-type
homogeneous block two-stage
and homogeneous strip three-block algorithms
respectively. In the third set of 50 random instances
the sheet utilization rates of the algorithm in this study
the ordinary two-stage algorithm
and the homogeneous block two-stage algorithm are 99.913 7%
99.862 3%
and 99.796 1%
respectively. In the fourth set of 31 benchmark instances
the exact solutions of all instances are solved by the algorithm in this study
and the exact solutions of two instances are not solved by the common corner-occupying algorithm.
Conclusion
2
The computation time of the algorithm in this study is much less than that of the exact cutting algorithms
and its optimization effect is close to that of the exact cutting algorithms. The computation time of the algorithm in this study is close to that of many heuristic cutting algorithms
and its optimization effect is better than that of many heuristic cutting algorithms. As a cutting pattern generation algorithm
this algorithm can be combined with linear programming
integer programming
and sequential heuristic algorithm to solve the 2D guillotine cutting stock problem of rectangular pieces.
Wang L, Liu Q, Chen X. Heuristic search algorithm for the rectangular fixed-size guillotine bin packing problem[J]. Journal of Software, 2017, 28(7):1640-1654.
王磊, 刘强, 陈新.单规格一刀切矩形排样问题的启发式搜索算法[J].软件学报, 2017, 28(7):1640-1654. [DOI:10.13328/j.cnki.jos.005100]
Zhang F, Liu Q, Zhang H, et al. Packing optimization of rectangle workpieces oriented to variable-sized bin[J]. Computer Integrated Manufacturing Systems, 2015, 21(11):2921-2928.
张帆, 刘强, 张浩, 等.面向多规格板材的矩形工件排样优化方法[J].计算机集成制造系统, 2015, 21(11):2921-2928. [DOI:10.13196/j.cims.2015.11.011]
Yang W B, Wang Z, Wang W L, et al. Packing of irregular polygons based on real-coded quantum evolutionary algorithm[J]. Computer Integrated Manufacturing Systems, 2016, 22(5):1235-1243.
杨卫波, 王铮, 王万良, 等.基于实数编码量子进化算法的不规则多边形排样[J].计算机集成制造系统, 2016, 22(5):1235-1243. [DOI:10.13196/j.cims.2016.05.009]
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.[DOI:10.1016/j.ejor.2005.12.047]
Cui Y, Wang Z, Li J. Exact and heuristic algorithms for staged cutting problems[J]. Proceedings of the Institution of Mechanical Engineers, Part B:Journal of Engineering Manufacture, 2005, 219(2):201-207.[DOI:10.1243/95440505X8136]
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.[DOI:10.1016/j.cor.2014.04.001]
Alvarez-Valdés R, Parajón A, Tamarit J M. A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems[J]. Computers&Operations Research, 2002, 29(7):925-947.[DOI:10.1016/S0305-0548(00)00095-2]
Leung S C H, Zhang D F, Zhou C L, et al. A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem[J]. Computers&Operations Research, 2012, 39(1):64-73.[DOI:10.1016/j.cor.2010.10.022]
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].计算机应用, 2013, 33(7):1908-1911. [DOI:10.11772/j.issn.1001-9081.2013.07.1908]
Wang Y R, Liaw J H, Lin H L, et al. Swarm manifold PSO for solving two-dimensional guillotine cutting problem[C]//Proceedings of 2016 International Conference on Machine Learning and Cybernetics. Jeju, South Korea: IEEE, 2016: 622-626.[ DOI: 10.1109/ICMLC.2016.7872959 http://dx.doi.org/10.1109/ICMLC.2016.7872959 ]
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.[DOI:10.1080/0305215X.2017.1315571]
Hifi M. Exact algorithms for large-scale unconstrained two and three staged cutting problems[J]. Computational Optimization and Applications, 2001, 18(1):63-88.[DOI:10.1023/A:1008743711658]
Cui Y D, Ji J, Zeng T J. Recursive algorithm for generating optimal two-segment cutting patterns of rectangular blanks[J]. Journal of Nanjing University of Aeronautics&Astronautics, 2006, 38(1):111-114.
崔耀东, 季君, 曾窕俊.生成矩形毛坯最优两段排样方式的递归算法[J].南京航空航天大学学报, 2006, 38(1):111-114. [DOI:10.3969/j.issn.1005-2615.2006.01.022]
Cui Y D, Huang J M, Zhang X Q. Recursive algorithm for unconstrained two-dimensional guillotine cutting problem of rectangular pieces[J]. Journal of Computer-Aided Design&Computer Graphics, 2006, 18(7):948-951.
崔耀东, 黄健民, 张显全.矩形毛料无约束2维剪切排样的递归算法[J].计算机辅助设计与图形学学报, 2006, 18(7):948-951. [DOI:10.3321/j.issn:1003-9775.2006.07.009]
Yang C M, Wang S R, Wang X Y. Heuristic algorithm on layout of chopped cutting based on 4 pieces of structure[J]. Journal of Machine Design, 2007, 24(2):25-26.
杨传民, 王树人, 王心宇.基于4块结构的斩断切割布局启发性算法[J].机械设计, 2007, 24(2):25-26. [DOI:10.3969/j.issn.1001-2354.2007.02.008]
Cui Y D, Liu Z Y. T-shape homogenous block patterns for the two-dimensional cutting problem[J]. Journal of Global Optimization, 2008, 41(2):267-281.[DOI:10.1007/s10898-007-9252-z]
Cui Y D. A new dynamic programming procedure for three-staged cutting patterns[J]. Journal of Global Optimization, 2013, 55(2):349-357.[DOI:10.1007/s10898-012-9930-3]
Ji J, Lu Y P, Zha J Z, et al. A deterministic algorithm for optimal two-segment cutting patterns of rectangular blanks[J]. Chinese Journal of Computers, 2012, 35(1):183-191.
季君, 陆一平, 查建中, 等.生成矩形毛坯最优两段排样方式的确定型算法[J].计算机学报, 2012, 35(1):183-191. [DOI:10.3724/SP.J.1016.2012.00183]
Pan W P, Chen Q L, Cui Y D, et al. An algorithm for generating optimal homogeneous strips three block patterns of rectangular blanks[J]. Journal of Graphics, 2015, 36(1):7-11.
潘卫平, 陈秋莲, 崔耀东, 等.基于匀质条带的矩形件最优三块布局算法[J].图学学报, 2015, 36(1):7-11. [DOI:10.3969/j.issn.2095-302X.2015.01.002]
Xue H T, Dong H F, Guan W L. An algorithm for generating composite strip two-segment cutting patterns[J]. Machinery Design&Manufacture, 2017, (7):124-127.
薛焕堂, 董海芳, 管卫利.复合条带两段排样方式的生成算法[J].机械设计与制造, 2017, (7):124-127. [DOI:10.19356/j.cnki.1001-3997.2017.07.032]
Zhang H G, Zhang X, Luo Y H, et al. An overview of research on adaptive dynamic programming[J]. Acta Automatica Sinica, 2013, 39(4):303-311.
张化光, 张欣, 罗艳红, 等.自适应动态规划综述[J].自动化学报, 2013, 39(4):303-311. [DOI:10.3724/SP.J.1004.2013.00303]
相关文章
相关作者
相关机构
京公网安备11010802024621
