JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE) ›› 2018, Vol. 48 ›› Issue (3): 75-80.doi: 10.6040/j.issn.1672-3961.0.2017.425

Previous Articles     Next Articles

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)

271

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

CLC Number: 

  • 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] LI Xinyu, XU Guiyun, REN Shijin, YANG Maoyun. Discriminative manifold-based uncorrelated sparse projective nonnegative matrix factorization [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(5): 1-12.
[2] WU Hongyan, JI Junzhong. Flower pollination algorithm-based functional module detection in protein-protein interaction networks [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(1): 21-30.
[3] ZHOU Zhijie, ZHAO Fujun, HU Changhua, WANG Li, FENG Zhichao, LIU Taoyuan. Failure prognosis method based on evidential reasoning for aerospace relay [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(5): 22-29.
[4] PEI Xiaobing, CHEN Huifen, ZHANG Baizhan, CHEN Menghui. Improved bi-variables estimation of distribution algorithms for multi-objective permutation flow shop scheduling problem [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(4): 25-30.
[5] REN Yongfeng, DONG Xueyu. An image saliency object detection algorithm based on adaptive manifold similarity [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(3): 56-62.
[6] ZHAI Jiyou, ZHOU Jingbo, REN Yongfeng, WANG Zhijian. A visual saliency detection based on background and foreground interaction [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(2): 80-85.
[7] WU Huimin, WU Jingli. An improved cycle basis algorithm for haplotyping a diploid individual [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(4): 9-14.
[8] ZHU Jie, WANG Jing, LIU Fei, GAO Guandong, DUAN Qing. Object classification method based on component pyramid matching [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(2): 14-21.
[9] JING Yunge, LI Tianrui. An incremental approach for reduction based on knowledge granularity [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(1): 1-9.
[10] WANG Lihong, LI Qiang. A selective ensemble method for traveling salesman problems [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(1): 42-48.
[11] REN Yongfeng, ZHOU Jingbo. An image saliency object detection algorithm based on information diffusion [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(6): 1-6.
[12] GAO Yanpu, WANG Xiangdong, WANG Dongqing. Maximum likelihood identification method for a multivariable controlled autoregressive moving average system [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(2): 49-55.
[13] LU Wenyang, XU Jiayi, YANG Yubin. LDA-based link prediction in social network [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2014, 44(6): 26-31.
[14] JIANG Weijian1,2, GUO Gongde1,2*, LAI Zhiming1,2. An improved adaboost algorithm based on new Haar-like feature for face detection [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2014, 44(2): 43-48.
[15] CHEN Wen-qiang1, LIN Chen1,2, CHEN Ke3, CHEN Jin-xiu1, ZOU Quan1,2*. Distributed affinity propagation clustering algorithm based on GraphLab [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2013, 43(5): 13-18.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd