应用三块排样方式求解二维下料问题

广西师范大学学报（自然科学版） ›› 2014, Vol. 32 ›› Issue (3): 41-45.

应用三块排样方式求解二维下料问题

梁秋月, 崔耀东, 游凌伟

广西大学计算机与电子信息学院,广西南宁 530004

收稿日期:2014-04-16 出版日期:2014-09-25 发布日期:2018-09-25
通讯作者: 崔耀东(1957—),男,河南林州人,广西大学教授,博士。E-mail:ydcui@263.net
基金资助:
国家自然科学基金资助项目(61363026,71371058)

Solving Two-dimensional Cutting Stock Problem with Three-block Patterns

LIANG Qiu-yue, CUI Yao-dong, YOU Ling-wei

College of Computer and Electronic Information, Guangxi University, Guangxi Nanning 530004,China

Received:2014-04-16 Online:2014-09-25 Published:2018-09-25

摘要/Abstract

摘要： 本文采用顺序价值修正框架和三块排样方式求解二维下料问题。该框架顺序生成排样方案中的各个排样方式(排样图),用每个排样方式满足部分毛坯的需求,直到满足全部需求为止;动态调整毛坯价值,使毛坯价值趋于合理;多次迭代生成多个不同的排样方案,实现优选。采用的三块排样方式通过不完全枚举法生成,其中最多包含三种毛坯,从而有利于简化下料工艺。通过与线性规划算法比较,说明在毛坯需求量较小的情况下,本文算法能有效减少板材消耗量。

关键词: 二维下料问题, 顺序启发式算法, 顺序价值修正, 三块排样方式

Abstract: The proposed approach solves two-dimensional cutting stock problem using three-block patterns and a sequential value correction framework. Cutting patterns in a cutting plan are generated sequentially. Each pattern is used to fulfill some portion of the remaining items until all the required items are fulfilled. The item values are adjusted dynamically to make the value more reasonable. Multiple cutting plans are generated in order to select the optimal one. The three-block patterns are generated by an incomplete enumeration method, in which each pattern contains at most three types of items to simplify the cutting process. The comparison with the linear programming algorithm indicates that the proposed approach can effectively reduce the plate consumption when the item demands are small.

Key words: two-dimensional cutting stock problem, sequential heuristic procedure, sequential value correction, three-block patterns

中图分类号:

TH164

梁秋月, 崔耀东, 游凌伟. 应用三块排样方式求解二维下料问题[J]. 广西师范大学学报（自然科学版）, 2014, 32(3): 41-45.

LIANG Qiu-yue, CUI Yao-dong, YOU Ling-wei. Solving Two-dimensional Cutting Stock Problem with Three-block Patterns[J]. Journal of Guangxi Normal University(Natural Science Edition), 2014, 32(3): 41-45.

参考文献

[1] FURINI F, MALAGUTI E, DURAN R M, et al. A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size[J]. European Journal of Operational Research, 2012, 218 (1):251-260.
[2] CUI Yao-dong, LIU Yang, ZHAO Zhi-gang, et al. Sequential grouping heuristic for the two-dimensional cutting stock problem with pattern reduction[J]. International Journal of Production Economics, 2013, 144 (2):432-439.
[3] BELOV G. Setup and open-stacks minimization in one-dimensional stock cutting[J]. INFORMS Journal on Computing, 2007, 19(1):27-35.
[4] 杨玉丽,孙英,崔耀东,等.矩形毛坯三块排样方式及其算法[J].现代制造工程,2006(10):67-69.
[5] CUI Yao-dong. Generating optimal T-shape cutting patterns for rectangular blanks[J]. Journal of Engineering Manufacture, 2004, 218(8):857-866.
[6] 杨玉丽,崔耀东,景运革,等. 生成矩形毛坯最优三块排样方式的精确算法[J]. 机械设计与制造,2008(9):11-13.
[7] 黄少丽,杨剑,侯桂玉,等. 解决二维下料问题的顺序启发式算法[J]. 计算机工程与应用,2011,47(13):234-237.
[8] IMAHORI S, YAGIURA M, UMETANI S, et al. Local search algorithms for the two-dimensional cutting stock problem with a given number of different patterns[M]//IBARAKI T, NONOBE K, YAGIURA M. Metaheuristics:Progress as Real Problem Solvers. New York: Springer, 2005:181-202.
[9] SILVA E, ALVELOS F, VALéRIO de CARVALHO J M. An integer programming model for two-and three-stage two-dimensional cutting stock problems[J]. European Journal of Operational Research, 2010, 205(3):699-708.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed