Transactions of Materials and Heat Treatment

Title：One-dimensional cutting problem in random environment

Authors： Ma Junyan Han Zhihui Luo Decheng Han Hechun Xiao Haihua

Unit： Guangxi University

KeyWords： one-dimensional cutting mathematical model random environments random expected value model recursive matrix column generation

ClassificationCode：TP391.7

year,vol(issue):pagenumber：2020,45(3):190-196

Abstract：

For the uncertainty of one-dimensional cutting environment in practical engineering, the mathematical model was established, and a column generation algorithm based on recursive matrix was proposed. Firstly, the mathematical model under the certain environment and the cutting model under the random environment were established based on the least amount of raw materials used as the target. Then, it was found that the material utilization rate could be increased in a random environment to be more in line with the actual production demand through the comparison of experiments. Furthermore, the random programming problem transformed into a conventional linear problem was analyzed and calculated by establishing a random expected value model to generate random values, and the cutting scheme was calculated by the column generation algorithm based on recursive matrix. According to the results of optimization calculation, the result analysis shows that using the column generation algorithm based on recursive matrix in a random large order environment can not only reduce the ways of cutting, but also reduce the consumption of raw materials, which provides a way for effectively improving the utilization rate of materials, reducing the cutting schemes and the cost in factory.

Funds：

广西自然科学基金资助项目（2018GXNSFAA138158）；广西教育厅项目（2017KY0023）；2016年广西制造系统与先进制造技术重点实验室项目（16-380-12S006）

马俊燕 (1977-)，女，博士，副教授 E-mail：191159191@qq.com

Reference：

［1］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, 2016, 23(1-2): 5-24.

［2］Zak E J. Row and column generation technique for a multistage cutting stock problem
［J］. Computers & Operations Research, 2002, 29(9):1143-1156.

［3］Kang M, Yoon K. An improved best-first branch-and-bound algorithm for unconstrained two-dimensional cutting problems
［J］. International Journal of Production Research, 2013, 51(6):1680-1693.

［4］Lu H C, Huang Y H. An efficient genetic algorithm with a corner space algorithm for a cutting stock problem in the TFT-LCD industry
［J］. European Journal of Operational Research, 2015, 246(1): 51-65.

［5］管卫利,龚击,薛焕堂.一维下料问题的一种混合启发式算法
［J］.机械设计与制造,2018，(8):237-239.

Guan W L,Gong J,Xue H T.A hybrid heuristic algorithm for the one dimensional cutting stock problem
［J］.Machinery Design & Manufacture,2018，(8):237-239.

［6］曹静静,崔耀东,李东兴.多线材变截面一维下料问题解法研究
［J］.锻压技术,2017,42(1):161-165.

Cao J J,Cui Y D,Li D X.Study on the solution of one-dimensional cutting stock for multiple stock lengths with variable cross-section
［J］. Forging & Stamping Technology, 2017,42(1):161-165.

［7］肖海华. 矩形件下料问题的创新线性规划布局方法研究与应用
［D］. 南宁：广西大学,2017.

Xiao H H. Research and Application on Innovative Linear Programming Layout Method for Rectangular Material Cutting Problem
［D］. Nanning：Guangxi University, 2017.

［8］Cui Y, Song X, Chen Y, et al. New model and heuristic solution approach for one-dimensional cutting stock problem with usable leftovers
［J］. Journal of the Operational Research Society, 2017, 68(3): 269-280.

［9］Sarper H, Jaksic N I. Evaluation of procurement scenarios in one-dimensional cutting stock problem with a random demand mix
［J］.Procedia Manufacturing, 2018, 17: 827-834.

［10］Reinertsen H. Optimization of Industrial Cutting Stock Problems-Production Scheduling in a Dynamic Stochastic Environment
［D］. Boulder：University of Colorado at Boulder, 2010.

［11］Beraldi P, Bruni M E, Conforti D. The stochastic trim-loss problem
［J］. European Journal of Operational Research, 2009, 197(1): 42-49.

［12］Alem D J, Munari P A, Arenales M N, et al. On the cutting stock problem under stochastic demand
［J］. Annals of Operations Research,2010,179(1): 169-186.

［13］胡源,别朝红,宁光涛,等.计及风电不确定性的多目标电网规划期望值模型与算法
［J］. 电工技术学报, 2016, 31(10):168-175.

Hu Y,Bie Z H,Ning G T,et al.The expected model and algorithm of multi-objective transmission network planning considering the uncertainty of wind power
［J］.Transactions of China Electrotechnical Society, 2016, 31(10):168-175.

［14］Wang Y,Zhao S, Zhou Z, et al. Risk adjustable day-ahead unit commitment with wind power based on chance constrained goal programming
［J］. IEEE Transactions on Sustainable Energy, 2017, 8(2):530-541.

［15］Zhang H, Song J. Dependent-chance programming on sugeno measure space
［J］. Journal of Uncertainty Analysis and Applications, 2017, 5(1):7.

Service：

【This site has not yet opened Download Service】【Add Favorite】