广西师范大学学报（自然科学版） ›› 2012, Vol. 30 ›› Issue (3): 149-153.

• • 上一篇    下一篇

多线材一维下料问题的求解策略

崔耀东, 周密, 杨柳   

  1. 广西大学计算机与电子信息学院,广西南宁530004
  • 收稿日期:2012-04-11 出版日期:2012-09-20 发布日期:2018-12-04
  • 通讯作者: 崔耀东(1957—),男,河南林州人,广西大学教授,博导。E-mail:ydcui@263.net
  • 作者简介:崔耀东,男,1957年生,汉族,河南林州人,博士,教授,博士生导师。
  • 基金资助:
    国家自然科学基金资助项目(61063031)

Strategies for Solving the 1D Cutting Stock Problem of Multiple Stock Lengths

CUI Yao-dong, ZHOU Mi, YANG Liu   

  1. School of Computer,Electronics and Information,Guangxi University,Nanning Guangxi 530004,China
  • Received:2012-04-11 Online:2012-09-20 Published:2018-12-04

摘要： 本文将线性规划与增强顺序法相结合,求解多线材一维下料问题。采用具有全容量特性的解法,一次生成多个排样方式,按比值法选择新排样方式。实验结果表明:对于文献中报道的一些例题,运用算法可降低线材成本;和商业一维下料CAD系统相比,在下料方案的线材成本相同的前提下,本文算法可大幅度缩短计算时间。

关键词: 一维下料, 线材下料, 排样问题

Abstract: The linear programming approach and the enhanced sequential heuristicprocedure are combined to solve the 1D cutting stock problem of multiple stock lengths.A procedure of the all capacity property is used to generate multiple patterns,from which the new pattern is selected using a ratio method.The experimental result indicates that the algorithm can improve the solutions to some benchmarkinstances and give solutions of the same material cost as that of some commercial packages,using much shorter computation time.

Key words: 1D cutting stock, lengthwise cutting stock, cutting stock problems

中图分类号: 

  • TP301.6
[1] SCHEITHAUER G,TERNO J,MÜLLER A,et al.Solving one-dimensional cutting stockproblems exactly with a cutting plane algorithm[J].Journal of the OperationalResearch Society,2001,52(12)1390-1401.
[2] CUI Yao-dong,YANG Yu-li.A heuristic for the one-dimensional cutting stock problem with usable leftover[J].European Journal of Operational Research,2010,204(2):245-250.
[3] CUI Y,ZHAO X,YANG Y,et al.A heuristic for the one dimensional cutting stockproblem with pattern reduction[J].Proceedings of the Institution of Mechanical Engineers,Part B:Journal of Engineering Manufacture,2008,222(6):677-685.
[4] LIANG Ko-hsin,YAO Xin,NEWTON C,et al.A new evolutionary approach to cuttingstock problems with and without contiguity[J].Computers and Operations Research,2002,29(12):1641-1659.
[5] YANG Chien-tung,SUNG Tso-chung,WENG Wei-chu.An improved tabu search approachwith mixed objective function for one-dimensional cutting stock problems[J].Advances in Engineering Software,2006,37(8):502-513.
[6] 郑晓军,杨光辉,滕弘飞.多规格一维下料问题基于满意度模拟退火算法[J].大连理工大学学报,2009,49(6):865-871.
[7] KELLERER H,PFERSCHY U,PISINGER D.Knapsack problems[M].Berlin:Springer,2004.
[1] 许伦辉,黄宝山,钟海兴. AGV系统路径规划时间窗模型及算法[J]. 广西师范大学学报（自然科学版）, 2019, 37(3): 1-8.
[2] 石亚冰, 黄予, 覃晓, 元昌安. 基于优化初始种子新策略的K-Means聚类算法[J]. 广西师范大学学报（自然科学版）, 2013, 31(4): 33-40.
[3] 曹永春, 邵亚斌, 田双亮, 蔡正琦. 一种基于免疫遗传算法的聚类方法[J]. 广西师范大学学报（自然科学版）, 2013, 31(3): 59-64.
[4] 张超群, 郑建国, 李陶深. 侦察蜂在人工蜂群算法中的作用[J]. 广西师范大学学报（自然科学版）, 2013, 31(3): 72-80.
[5] 周艳聪, 顾军华, 董永峰. 逆向二进制防碰撞算法及其FPGA硬件实现[J]. 广西师范大学学报（自然科学版）, 2013, 31(3): 94-99.
[6] 黄敏, 靳婷, 钟声, 马玉春. 基于改进蚁群算法求解连续空间寻优问题[J]. 广西师范大学学报（自然科学版）, 2013, 31(2): 34-38.
[7] 马宁, 于洪志. 基于Arnold变换和DCT变换的图像水印算法[J]. 广西师范大学学报（自然科学版）, 2011, 29(3): 163-167.
[8] 王俊杰, 温雪岩, 徐克生, 于鸣. 基于局部敏感哈希的改进堆叠算法[J]. 广西师范大学学报（自然科学版）, 2020, 38(4): 21-31.
[9] 韦振汉, 宋树祥, 夏海英. 基于随机森林的锂离子电池荷电状态估算[J]. 广西师范大学学报（自然科学版）, 2018, 36(4): 27-33.
[10] 鄂旭, 邵良杉, 李胜, 王全铁. 一种基于关联度的区间型数据离散化方法[J]. 广西师范大学学报（自然科学版）, 2011, 29(2): 134-137.
[11] 吕虹, 秦永彬, 罗聪. 基于Memetic算法的飞机地面作业调度问题研究[J]. 广西师范大学学报（自然科学版）, 2011, 29(2): 145-150.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 广西师范大学学报（自然科学版）编辑部
地址：广西桂林市三里店育才路15号　邮编：541004
电话：0773-5857325　E-mail: gxsdzkb@mailbox.gxnu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发