Journal of Guangxi Normal University(Natural Science Edition) ›› 2012, Vol. 30 ›› Issue (3): 149-153.

Previous Articles     Next Articles

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

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

CLC Number: 

  • 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] XU Lunhui,HUANG Baoshan,ZHONG Haixing. Time Window Model and Algorithm with AGV System Path Planning [J]. Journal of Guangxi Normal University(Natural Science Edition), 2019, 37(3): 1-8.
[2] SHI Ya-bing, HUANG Yu, QIN Xiao, YUAN Chang-an. K-Means Clustering Algorithm Based on a Novel Approach for Improved Initial Seeds [J]. Journal of Guangxi Normal University(Natural Science Edition), 2013, 31(4): 33-40.
[3] CAO Yong-chun, SHAO Ya-bin, TIAN Shuang-liang, CAI Zheng-qi. A Clustering Method Based on Immune Genetic Algorithm [J]. Journal of Guangxi Normal University(Natural Science Edition), 2013, 31(3): 59-64.
[4] ZHANG Chao-qun, ZHENG Jian-guo, LI Tao-shen. Effect of Scout Bees on the Performance of Artificial Bee Colony Algorithm [J]. Journal of Guangxi Normal University(Natural Science Edition), 2013, 31(3): 72-80.
[5] ZHOU Yan-cong, GU Jun-hua, DONG Yong-feng. Converse Binary Anti-collision Algorithm and Hardware Implementation Based on FPGA [J]. Journal of Guangxi Normal University(Natural Science Edition), 2013, 31(3): 94-99.
[6] HUANG Min, JIN Ting, ZHONG Sheng, MA Yu-chun. Ant Colony Algorithm for Solving Continuous Function Optimization Problem Based on Pheromone Distributive Function [J]. Journal of Guangxi Normal University(Natural Science Edition), 2013, 31(2): 34-38.
[7] MA Ning, YU Hong-zhi. Image Watermarking Algorithm Based on DCT Transform and ArnoldTransform [J]. Journal of Guangxi Normal University(Natural Science Edition), 2011, 29(3): 163-167.
[8] WANG Junjie, WEN Xueyan, XU Kesheng, YU Ming. An Improved Stack Algorithm Based on Local Sensitive Hash [J]. Journal of Guangxi Normal University(Natural Science Edition), 2020, 38(4): 21-31.
[9] WEI Zhenhan, SONG Shuxiang, XIA Haiying. State-of-charge Estimation Using Random Forest for Lithium Ion Battery [J]. Journal of Guangxi Normal University(Natural Science Edition), 2018, 36(4): 27-33.
[10] E Xu, SHAO Liang-shan, LI Sheng, WANG Quan-tie. Discretization Algorithm for Interval Numbers by Associated Degree [J]. Journal of Guangxi Normal University(Natural Science Edition), 2011, 29(2): 134-137.
[11] LU Hong, QIN Yong-bin, LUO Cong. Application of Memetic Algorithm in the Airport Ground Services Scheduling Problem [J]. Journal of Guangxi Normal University(Natural Science Edition), 2011, 29(2): 145-150.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!