A Heuristic Programming Solution to a Nonlinear Cutting Stock Problem

Abstract

A heuristic procedure for scheduling production rolls of paper through a finishing operation to cut them down to finished roll sizes is described. The ratio of service time to interarrival time of production rolls at the initial cutting station is large so that insufficient time is available to set it up unless a minimum number of production rolls are to be processed in the same manner. Otherwise, some portion of each production roll must go through a reprocessing operation to complete the cutting of finished sizes. The objective is to minimize the cost of trim loss and reprocessing. The procedure generates cutting patterns and usage levels sequentially until all the requirements are satisfied. At each step the search is dependent upon the characteristics of the unsatisfied requirements. A maximum of three solutions is generated for each problem. If none satisfies a predetermined aspiration level, the best of the three is chosen. The procedure was evaluated by scheduling a specific paper production facility and observing the results for a set of 15 problems. For each problem, the best solution was recorded. The overall results from this set of problems were then compared to previously recorded results on problems solved manually. There was a 16% improvement in solution quality for the heuristic procedure relative to the manual method.