This paper presents a sequential heuristic procedure (SHP) for the 1D cutting stock problem with pattern reduction, where a set of items are cut from stock bars of the same length to minimize the bar cost, with a secondary objective being to reduce the pattern count of the cutting plan. The SHP generates the current pattern to produce some items, and continues until all items are fulfilled. The algorithm uses two candidate sets (C-Sets). The first is the set of the candidate items for generating the current pattern. The second is the set of candidate patterns from which the current pattern is selected. The algorithm generates candidate patterns using the candidate items, determines the estimated cutting-plan cost (ECP-cost) of each pattern using a look-ahead strategy, and selects the pattern of the minimum ECP-cost as the current pattern. The computational results indicate that the algorithm is efficient.
9 February 2017 in International Transactions in Operational Research
A pattern-set generation algorithm (PSG) for the one-dimensional multiple stock sizes cutting stock problem (1DMSSCSP) is presented. The solution process contains two stages. In the first stage, the PSG solves the residual problems repeatedly to generate the patterns in the pattern set, where each residual problem is solved by the column-generation approach, and each pattern is generated by solving a single large object placement problem. In the second stage, the integer linear programming model of the 1DMSSCSP is solved using a commercial solver, where only the patterns in the pattern set are considered. The computational results of benchmark instances indicate that the PSG outperforms existing heuristic algorithms and rivals the exact algorithm in solution quality.