A Recursive Algorithm Of One-Dimensional Cutting Stock Problem Based On Multi-Thread Technique

There are plenty of cutting stock problems in national economical industry. How to improve material utilization, reduce the cost, and simplify the cutting pattern, is the focal point which various enterprises pay attention to. The One-Dimensional Cutting Stock Problem (1D-CSP) only needs to consider one directional size, therefore it is called rod cutting stock problem. Stacks refer to the vessel used for depositing each kind of item in the cutting process. The stacks at open condition are called "open stacks". At different time of cutting process, the number of open stacks may be different, and its maximum value is called the maximum number of open stacks. Because the cutting location area is certain, the maximum number of open stacks often will be restricted.What this article studies is the 1D-CSP of single-length material. In order to minimize the number of open stacks and simplify the cutting craft, a recursive algorithm is proposed to constrain the number of item types in each pattern. Besides, in view of the long computing time of precise algorithm, upper bound method and multi-thread technique is successively used for making improvement to the recursive algorithm. These two methods decrease the operation time effectively. At the same time, consider the high material utilization, and develop one-dimensional cutting stock system. Through the empirical datum testing, the computational results confirm the correctness and the validity of this article's algorithm. The main work of this paper is as follows:First, according to the research content, establish mathematical model of current optimal cutting pattern, use recursive algorithm to solve knapsack problem based on this model, and then current optimal cutting pattern with maximum value of items is generated. After that, upper bound method and multi-thread programming technique is successively used to further optimize the recursive algorithm, and the data of renewing current optimal cutting pattern is synchronized.Then, relax linear integer programming model to obtain linear programming mode of 1D-CSP, articulated the optimal cutting pattern with the linear programming model, use delayed pattern generation method to obtain the optimal solution of linear programming problem, and suitable rounding method is adopted to get approximate optimal solution of 1D-CSP.Finally, based on the proposed algorithm, develop one-dimensional cutting stock system, providing user-friendly input and output contact surface, being able to satisfy user's ordering demand. The testing results indicate that the presented approach can reduce effectively the area around the cutting machine and simplify the cutting craft.