|
|
- 2018
有顺序依赖损耗的一维下料问题
|
Abstract:
摘要： 针对从具体工业应用中抽象出的一种特殊一维下料问题,提出一种基于顺序价值校正框架的下料算法,在考虑问题特殊性的同时求取最小化线材使用量的下料方案。定义并求得每两个毛坯间的损耗值后,顺序生成各个排样图,并得到下料方案。通过不断修正毛坯价值,生成多个下料方案,取其中线材消耗量最小者来逼近最优解。与其他算法进行比较的结果表明,本算法有较少的材料消耗量与合适的计算时间。
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 problems 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
| [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] | 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. |
| [3] | 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. |
| [4] | 刘睿, 于波, 崔耀东. 一维下料问题中提高计算效率方法的研究[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. |
| [5] | BELOV G, SCHEITHAUER G. Setup and open-stacks minimization in one-dimensional stock cutting [J]. Informs Journal on Computing, 2007, 19(1): 27-35. |
| [6] | 金升平, 陈定方, 张翔,等. 一维优化下料问题的基因遗传算法[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. |
| [7] | WAGNER B J. A genetic algorithm solution for one-dimensional bundled stock cutting[J]. European Journal of Operational Research, 1999, 117(2):368-381. |
| [8] | 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. |
| [9] | 梁秋月, 崔耀东, 游凌伟. 应用三块排样方式求解二维下料问题[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. |
| [10] | 崔轶平. 多线材一维下料问题的顺序价值校正算法[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. |
| [11] | GILMORE P C, GOMORY R E. A linear programming approach to the cutting stock problem: II [J]. Operations Research, 1963, 11(6): 863-888. |
| [12] | 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. |
| [13] | 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. |
| [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]. 华南理工大学学报(自然科学版), 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. |
| [16] | 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. |
| [17] | 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. |
| [18] | 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. |
| [19] | HAESSLER R W. Controlling cutting pattern changes in one-dimensional trim problems[J]. Operations Research, 1975, 23(3): 483-493. |
| [20] | VAHRENKAMP R. Random search in the one-dimensional cutting stock problem[J]. European Journal of Operational Research, 1996, 95(1):191-200. |
| [21] | 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. |
