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

山东大学学报(工学版) ›› 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)

647

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

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

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] 宋佳芮,陈艳平,王凯,黄瑞章,秦永彬. 基于Affix-Attention的命名实体识别语义补充方法[J]. 山东大学学报 (工学版), 2023, 53(2): 70-76.
[2] 杨巨成,韩书杰,毛磊,代翔子,陈亚瑞. 胶囊网络模型综述[J]. 山东大学学报 (工学版), 2019, 49(6): 1-10.
[3] 方波,陈红梅. 一种新的双策略进化果蝇优化算法[J]. 山东大学学报 (工学版), 2019, 49(3): 22-31.
[4] 吴红岩,冀俊忠. 基于花授粉算法的蛋白质网络功能模块检测方法[J]. 山东大学学报(工学版), 2018, 48(1): 21-30.
[5] 周志杰,赵福均,胡昌华,王力,冯志超,刘涛源. 基于证据推理的航天继电器故障预测方法[J]. 山东大学学报(工学版), 2017, 47(5): 22-29.
[6] 裴小兵,陈慧芬,张百栈,陈孟辉. 改善式BVEDA求解多目标调度问题[J]. 山东大学学报(工学版), 2017, 47(4): 25-30.
[7] 任永峰,董学育. 基于自适应流形相似性的图像显著性区域提取算法[J]. 山东大学学报(工学版), 2017, 47(3): 56-62.
[8] 翟继友,周静波,任永峰,王志坚. 基于背景和前景交互传播的图像显著性检测[J]. 山东大学学报(工学版), 2017, 47(2): 80-85.
[9] 邬慧敏,吴璟莉. 重建二倍体个体单体型的改进环基算法[J]. 山东大学学报(工学版), 2016, 46(4): 9-14.
[10] 朱杰,王晶,刘菲,高冠东,段庆. 基于成分金字塔匹配的对象分类方法[J]. 山东大学学报(工学版), 2016, 46(2): 14-21.
[11] 景运革,李天瑞. 基于知识粒度的增量约简算法[J]. 山东大学学报(工学版), 2016, 46(1): 1-9.
[12] 王立宏,李强. 旅行商问题的一种选择性集成求解方法[J]. 山东大学学报(工学版), 2016, 46(1): 42-48.
[13] 任永峰, 周静波. 基于信息弥散机制的图像显著性区域提取算法[J]. 山东大学学报(工学版), 2015, 45(6): 1-6.
[14] 高艳普, 王向东, 王冬青. 多变量受控自回归滑动平均系统的极大似然辨识方法[J]. 山东大学学报(工学版), 2015, 45(2): 49-55.
[15] 卢文羊, 徐佳一, 杨育彬. 基于LDA主题模型的社会网络链接预测[J]. 山东大学学报(工学版), 2014, 44(6): 26-31.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 孔祥臻,刘延俊,王勇,赵秀华 . 气动比例阀的死区补偿与仿真[J]. 山东大学学报(工学版), 2006, 36(1): 99 -102 .
[2] Yue Khing Toh1 ， XIAO Wendong2 ， XIE Lihua1 . 基于无线传感器网络的分散目标跟踪：实际测试平台的开发应用（英文）[J]. 山东大学学报(工学版), 2009, 39(1): 50 -56 .
[3] 李辉平, 赵国群, 张雷, 贺连芳. 超高强度钢板热冲压及模内淬火工艺的发展现状[J]. 山东大学学报(工学版), 2010, 40(3): 69 -74 .
[4] 薛翊国，李术才，赵岩，苏茂鑫，李为腾，丁志海. 青岛胶州湾海底隧道F44含水断层注浆前后TSP探测分析[J]. 山东大学学报(工学版), 2009, 39(2): 108 -112 .
[5] 胡天亮,李鹏,张承瑞,左毅 . 基于VHDL的正交编码脉冲电路解码计数器设计[J]. 山东大学学报(工学版), 2008, 38(3): 10 -13 .
[6] 邓斌,王江 . 基于混沌同步与自适应控制的神经元模型参数估计[J]. 山东大学学报(工学版), 2007, 37(5): 19 -23 .
[7] 孙媛媛 徐衍亮 姚之宁. 旁磁制动单相感应电动机制动力的分析与计算[J]. 山东大学学报(工学版), 2009, 39(5): 120 -123 .
[8] 任敬喜,耿金花,高齐圣 . 多因素多指标产品的质量优化[J]. 山东大学学报(工学版), 2007, 37(3): 114 -117 .
[9] 乔小燕. 赤潮藻显微图像自动识别方法[J]. 山东大学学报(工学版), 2016, 46(3): 1 -6 .
[10] 张志钢,张承慧，赵洪国,焉杰. 观测时滞连续系统的白噪声H2估计[J]. 山东大学学报(工学版), 2009, 39(3): 56 -61 .
版权所有 © 2018 《山东大学学报(工学版)》编辑部　
地址: 济南市山大南路27号（250100）　 电话: 0531-88366735　 E-mail: xbgxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发