摘要
为解决大规模矩形毛坯无约束的二维剪切排样问题,提出双排多段排样方式及其生成算法。排样时采用一条剪切线将板材切分为两段,用一组剪切线将每段切分成一系列的块,每个块由一组水平方向的同质条带构成。采用枚举法确定两段分界线的最优位置,通过求解背包模型确定所有可能尺寸的块的最大价值和块在段中的最优布局。利用文献中的2组基准测题对所述算法进行测试,实验结果表明,该算法能在合理的计算时间内取得较好的优化结果。
To solve large scale unconstrained two-dimensional guillotine-cutting problem of rectangular items, an algorithm for generating the patterns of double-rows and multi segments is proposed, where the plate is divided into two segments by a cut, each of which is then divided into a series of blocks with a set of cuts, and each block contains a group of horizontal strips. The optimal position of the cut that divides the plate into two segments is determined through enumeration. Knapsack problems are solved to obtain the maximum values of all possible blocks and the block layouts on the segments. The algorithm is tested on two groups of benchmark problems in the literature. The computational results indicate that the algorithm can obtain better optimization results in a reasonable computation time.
出处
《图学学报》
CSCD
北大核心
2016年第3期285-289,共5页
Journal of Graphics
基金
国家自然科学基金项目(61363026
71371058)
广西自然科学基金项目(2014GXNSFAA118357)
关键词
无约束二维切割
下料
双排多段排样方式
背包问题
unconstrained two-dimensional cutting
stock packing
double-rows and multi-segments patterns
knapsack problem
