Research On The Algorithm For The Two-Dimensional Cutting Stock Problem With Usable Leftover

This paper studies the two-dimensional rectangular cutting stock problem with usable leftover (short for usable leftover problem:ULP):Rectangular items required by the current customer order are produced from stock plates, where the item demands must be met and the plate cost should be minimized. The stock plates include both the standard sizes purchased from the market and leftovers produced in previous cutting stock processes. The current cutting plan yields the required items of the current order. It may also produce new leftovers that can be used for processing future orders. The solution to the ULP is a cutting plan that consists of different cutting patterns, where each pattern may include a leftover. This paper combines the generation algorithm of uniform blocks with the sequential heuristic procedure to obtain the cutting plan. The main research works include the following:(1) Proposing a recursive pattern-generation algorithm to generate patterns of uniform blocks. The algorithm considers both material utilization and section cost to maximize the pattern value (the difference between the total value of the included items and that of the section cost). Computational results of two sets of instances indicate that the algorithm can effectively reduce the number of sections, leading to lower cutting cost and larger pattern value.(2) Proposing a sequential heuristic procedure for solving the ULP. It calls the pattern-generation algorithm to generate the patterns in each cutting plan and considers multiple cutting plans. Leftovers are allowed in the cutting patterns. The range of the leftover sizes are determined such that the leftovers have sizes sufficiently large for being used in the future. Formulas are established to give the leftovers larger priorities in use.30 random successive orders are used in the experimental computation, where the leftovers generated by each cutting plan can be used in processing subsequent orders. The results show that compared with the common strategy (in which only the last pattern of a cutting plan is allowed to include a leftover), the proposed algorithm can significantly improve the material utilization and reduce the plate cost.