Solving The One-Dimensional Cutting Stock Problem With Multiple Stock Lengths Using Squential Value Correction Procedure

In industries, large pieces of material are often required to be separated into small items while minimize the cost. Such kind of problem is called Cutting Stock Problem (CSP). The one-dimensional CSP (1DCSP) deals with the case that all the stocks and items are given in one dimensional, where only the lengths need to be considered. The 1DCSP is also referred to as the linear CSP. It includes the cutting of bars, profiles and tubes.In this paper, the mathematical model for the 1DCSP with multiple stock lengths is established first. Then, a sequential value correction heuristic for solving the problem is presented. Known the item values, the heuristic calls a bounded knapsack algorithm to generate each pattern, determines its frequency from considering the remaining demands. The patterns are generated one after the other until all item demands are met. After the generation of each pattern, the item values are adjusted according to the information of the pattern, so as to diversify the cutting plans. Many cutting plans are generated through iteration, so that the item values are thoroughly adjusted and the solution quality is improved.Other works of this paper include:(1) Applying parallel computing to the algorithm according to the character of the sequential value correction heuristic; (2) Discussing the way of applying the sequential value correction heuristic to two dimensional cutting stock (bin packing) problems.A software prototype of the proposed algorithm is developed and intensive experimental computation is performed to evaluate the effectiveness and efficiency of the proposed algorithm. According to the computational results, the proposed heuristic is more effective than some of the recently published algorithms. The computation time is also reasonable.