Controlling Cutting Pattern Changes in One-Dimensional Trim Problems

This paper develops a formulation of the one-dimensional trim problem when there is a fixed charge associated with using a cutting pattern. The purpose of the fixed charge is to limit the number of pattern changes that must be made. Because of the large number of possible cutting patterns, the resulting problem is a combinatorial program that is far beyond the capability of existing algorithms. As a result, we develop a heuristic procedure that can be experimentally tuned to balance the potentially conflicting objectives of minimizing both trim loss and pattern changes. The heuristic procedure is organized around a sequential search that relies on descriptors of the unscheduled orders to set goals on factors such as trim loss and pattern usage for the next pattern to enter the solution. A sample problem is presented along with a discussion of the scope of the application of the heuristic procedure.