MHA: A Mixed Heuristic Algorithm for the Cutting Stock Problem
Cutting Stock Problem (CSP), the studies of which mainly focus on building up specific mathematical models and finding efficient solution methods, has been widely applied in engineering and industrial production. This paper builds a single objective linear programming model for the one-dimensional (1D) and two-dimensional (2D) cutting stock problems with time restriction, and presents an effective multistage mixed heuristic algorithm (MHA) for model solving. MHA integrates heuristic strategy, lemma of dropping inferior patterns, greedy theory and the time dimension handling method to optimize the combination of patterns and reduce the computational complexity. The final cutting solution gotten by the MHA achieves a utilization ratio of more than 95％. The MHA can be implemented easily and is very fast. It is widely applicable and especially suitable for 1D and 2D cutting stock problems. For the demonstration problems, the number of raw materials, the number of cutting patterns, the total wastes, and the utilization ratio are 800, 46, 6430mm and 98.96％ respectively for the 1D case, are 462, 65, 4340880mm2 and 96.87％ respectively for the 2D case.
Yingyu Huo Kejing He Rengui Zhang Yong Zhong
School of Science,Foshan University,Foshan 528000,China School of Computer Science and Engineering,South China University of Technology,Guangzhou 510641,Chi Guangzhou University,Guangzhou,China Foshan University,Foshan 528000,China and Postdoctoral Research Station of Computer Applications,Nan
国际会议
2009 IEEE International Conference on Information and Automation(2009年 IEEE信息与自动化国际学术会议)
珠海、澳门
英文
460-465
2009-06-22（万方平台首次上网日期，不代表论文的发表时间）