您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（工学版）》

山东大学学报(工学版) ›› 2018, Vol. 48 ›› Issue (3): 75-80.doi: 10.6040/j.issn.1672-3961.0.2017.425

• • 上一篇    下一篇

有顺序依赖损耗的一维下料问题

梁泽华,崔耀东*,张雨   

  1. 广西大学计算机与电子信息学院, 广西 南宁 530004
  • 收稿日期:2017-08-29 出版日期:2018-06-20 发布日期:2017-08-29
  • 通讯作者: 崔耀东(1957— ),男,河南林州人,教授,博士生导师,主要研究方向为优化计算技术与CAD,智能算法与设计. E-mail:ydcui@263.net E-mail:394766924@qq.com
  • 作者简介:梁泽华(1992— ),女,广西柳州人,硕士研究生,主要研究方向为人工智能. E-mail:394766924@qq.com
  • 基金资助:
    国家自然科学基金资助项目(71371058);国家自然科学基金资助项目(61363026)

The one-dimensional cutting stock problem with sequence-dependent cut losses

LIANG Zehua, CUI Yaodong*, ZHANG Yu   

  1. College of Computer and Electronic Information, Guangxi University, Nanning 530004, Guangxi, China
  • Received:2017-08-29 Online:2018-06-20 Published:2017-08-29

PDF (PC)

338

摘要： 针对从具体工业应用中抽象出的一种特殊一维下料问题,提出一种基于顺序价值校正框架的下料算法,在考虑问题特殊性的同时求取最小化线材使用量的下料方案。定义并求得每两个毛坯间的损耗值后,顺序生成各个排样图,并得到下料方案。通过不断修正毛坯价值,生成多个下料方案,取其中线材消耗量最小者来逼近最优解。与其他算法进行比较的结果表明,本算法有较少的材料消耗量与合适的计算时间。

关键词: 顺序依赖损耗, 顺序价值校正, 一维下料问题

Abstract: For a particular one-dimensional cutting stock problem abstracted from specific industrial applications, an algorithm based on sequential value correction proposed with considering minimize stock material waste and the problems special properties was proposed. The cutting patterns were generated sequentially after defining and getting the cost between each two items, and then a cutting plan make-up was got by these patterns. Many different cutting plans were produced by continuously correcting the value of items, and the best one was chosen to approach optimal solution. Compared with the other algorithms, the results showed that the proposed approach could get less consumption of raw material and low computation time.

Key words: one-dimensional cutting stock problem, sequential value correction, sequence-dependent cut losses

中图分类号: 

  • TP301
[1] GILMORE P C, GOMORY R E. A linear programming approach to the cutting-stock problem [J]. Operations Research, 1961, 11(6):849-859.
[2] GILMORE P C, GOMORY R E. A linear programming approach to the cutting stock problem: II [J]. Operations Research, 1963, 11(6): 863-888.
[3] VANCE P H, BARNHART C, JOHNSON E L, et al. Solving binary cutting stock problems by column generation and branch-and-bound[J]. Computational Optimization and Applications, 1994, 3(2):111-130.
[4] SCHEITHAUER G, TERNO J, MÜLLER A, et al. Solving one-dimensional cutting stock problems exactly with a cutting plane algorithm[J]. Journal of the Operational Research Society, 2001, 52(12):1390-1401.
[5] BELOV G, SCHEITHAUER G. A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths[J]. European Journal of Operational Research, 2002, 141(2):274-294.
[6] HAESSLER R W. Controlling cutting pattern changes in one-dimensional trim problems[J]. Operations Research, 1975, 23(3): 483-493.
[7] VAHRENKAMP R. Random search in the one-dimensional cutting stock problem[J]. European Journal of Operational Research, 1996, 95(1):191-200.
[8] GRADISAR M, KLJAJIC M, RESINOVIC G, et al. A sequential heuristic procedure for one-dimensional cutting[J]. European Journal of Operational Research, 1999, 114(3):557-568.
[9] GRADISAR M, RESINOVIC G, KLJAJIC M. A hybrid approach for optimization of one-dimensional cutting[J]. European Journal of Operational Research, 1999, 119(3):719-728.
[10] 刘睿, 于波, 崔耀东. 一维下料问题中提高计算效率方法的研究[J]. 计算机工程与应用, 2013, 49(9):247-250. LIU Rui, YU Bo, CUI Yaodong. Several heuristic strategies to improve computational efficiency for one-dimensional cutting stock problem[J]. Computer Engineering and Applications, 2013, 49(9):247-250.
[11] BELOV G, SCHEITHAUER G. Setup and open-stacks minimization in one-dimensional stock cutting [J]. Informs Journal on Computing, 2007, 19(1): 27-35.
[12] CUI Y, ZHAO X, YANG Y, et al. A heuristic for the one-dimensional cutting stock problem with pattern reduction[J]. Proceedings of the Institution of Mechanical Engineers Part B: Journal of Engineering Manufacture, 2008, 222(6):677-685.
[13] CUI Y P, TANG T B. Parallelized sequential value correction procedure for the one-dimensional cutting stock problem with multiple stock lengths[J]. Engineering Optimization, 2014, 46(10):1352-1368.
[14] 张春玲, 崔耀东. 一维优化下料问题[J]. 桂林理工大学学报, 2004, 24(1):103-106. ZHANG Chunling, CUI Yaodong. Optimization of one-dimensional cutting stock problem[J]. Journal of Guilin University of Technology, 2004, 24(1):103-106.
[15] 金升平, 陈定方, 张翔,等. 一维优化下料问题的基因遗传算法[J]. 武汉交通科技大学学报, 1997,21(2):168-172. JIN Shengping, Chen Dingfang, ZHANG Xiang, et al. A genetic algorithm for cutting one-dimension material[J]. Journal of Wuhan Transportation University, 1997, 21(2):168-172.
[16] WAGNER B J. A genetic algorithm solution for one-dimensional bundled stock cutting[J]. European Journal of Operational Research, 1999, 117(2):368-381.
[17] 沈显君, 杨进才, 应伟勤,等. 一维下料问题的自适应广义粒子群优化求解[J]. 华南理工大学学报(自然科学版), 2007, 35(9):113-117. SHEN Xianjun, YANG Jincai, YING Weiqin, et al. Adaptive general particle swarm optimization for one-dimension cutting stock problem[J]. Journal of South China University of Technology(Natural Science Edition), 2007, 35(9):113-117.
[18] GARRAFFA M, SALASSA F, VANCROONENBURG W, et al. The one-dimensional cutting stock problem with sequence-dependent cut losses[J]. International Transactions in Operational Research, 2015, 23(1-2): 5-24.
[19] 梁秋月, 崔耀东, 游凌伟. 应用三块排样方式求解二维下料问题[J]. 广西师范大学学报(自然科学版), 2014, 32(3): 41-45. LIANG Qiuyue, CUI Yaodong, YOU Lingwei. Soving two-dimensional cutting stock problem with three-block patterns[J]. Journal of Guangxi Normal University(Natural Science Edition), 2014, 32(3): 41-45.
[20] 崔轶平. 多线材一维下料问题的顺序价值校正算法[D]. 桂林: 广西大学, 2015. CUI Yiping. Solving the one-dimensional cutting stock problem with multiple stock lengths using sequential value correction procedure [D]. Guilin: Guangxi University, 2015.
[21] VANCROONENBURG W, DE CAUSMAECKER P, SPIEKSMA F, et al. Column generation for the 1D-CSP with SDCL, and the orienteering problem with multiplicity[R]. [2017-03-16]. http://allserv. kahosl. be/∽ wimvc/cg-1D-csp-with-sdcl. pdf, 2014.
[1] 李新玉, 徐桂云, 任世锦, 杨茂云. 基于鉴别流形的不相关稀疏投影非负矩阵分解[J]. 山东大学学报(工学版), 2015, 45(5): 1-12.
[2] 吴红岩,冀俊忠. 基于花授粉算法的蛋白质网络功能模块检测方法[J]. 山东大学学报(工学版), 2018, 48(1): 21-30.
[3] 周志杰,赵福均,胡昌华,王力,冯志超,刘涛源. 基于证据推理的航天继电器故障预测方法[J]. 山东大学学报(工学版), 2017, 47(5): 22-29.
[4] 裴小兵,陈慧芬,张百栈,陈孟辉. 改善式BVEDA求解多目标调度问题[J]. 山东大学学报(工学版), 2017, 47(4): 25-30.
[5] 任永峰,董学育. 基于自适应流形相似性的图像显著性区域提取算法[J]. 山东大学学报(工学版), 2017, 47(3): 56-62.
[6] 翟继友,周静波,任永峰,王志坚. 基于背景和前景交互传播的图像显著性检测[J]. 山东大学学报(工学版), 2017, 47(2): 80-85.
[7] 邬慧敏,吴璟莉. 重建二倍体个体单体型的改进环基算法[J]. 山东大学学报(工学版), 2016, 46(4): 9-14.
[8] 朱杰,王晶,刘菲,高冠东,段庆. 基于成分金字塔匹配的对象分类方法[J]. 山东大学学报(工学版), 2016, 46(2): 14-21.
[9] 景运革,李天瑞. 基于知识粒度的增量约简算法[J]. 山东大学学报(工学版), 2016, 46(1): 1-9.
[10] 王立宏,李强. 旅行商问题的一种选择性集成求解方法[J]. 山东大学学报(工学版), 2016, 46(1): 42-48.
[11] 任永峰, 周静波. 基于信息弥散机制的图像显著性区域提取算法[J]. 山东大学学报(工学版), 2015, 45(6): 1-6.
[12] 高艳普, 王向东, 王冬青. 多变量受控自回归滑动平均系统的极大似然辨识方法[J]. 山东大学学报(工学版), 2015, 45(2): 49-55.
[13] 卢文羊, 徐佳一, 杨育彬. 基于LDA主题模型的社会网络链接预测[J]. 山东大学学报(工学版), 2014, 44(6): 26-31.
[14] 江伟坚1,2,郭躬德1,2*,赖智铭1,2. 基于新Haar-like特征的Adaboost人脸检测算法[J]. 山东大学学报(工学版), 2014, 44(2): 43-48.
[15] 陈文强1,林琛1,2,陈珂3,陈锦秀1,邹权1,2*. 基于GraphLab的分布式近邻传播聚类算法[J]. 山东大学学报(工学版), 2013, 43(5): 13-18.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(工学版)》编辑部　
地址: 济南市山大南路27号（250100）　 电话: 0531-88366735　 E-mail: xbgxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发