An LP-based tabu search for batch scheduling in a cutting process with finite buffers

This paper addresses a cutting stock problem under typical resource constraints that arise when working centres with nesting capabilities are associated with automatic feeders/stackers. The critical resource is the number of buffers available to host the batches built up by the centre. To cope with it, pattern and batch sequencing problems must be addressed simultaneously. A tabu-search algorithm exploring batch output sequences is proposed. The algorithm never opens more stacks than buffers, respects batch compatibility/precedence constraints, and keeps the maximum order spread under control. To demonstrate its effectiveness and efficiency, a computational study was set up, solving 920 test problems derived from the literature. The study enabled a proper tuning of the method and offered encouraging results: in 228 cases an optimum was found; in nearly all, the gap from the optimum was below 1%. Computation times range from fractions of seconds to a couple of minutes in the worst cases. Compared to existing methods, the algorithm provides on average the same solution quality, with the advantage of solving a problem which is more general and hence closer to application. The paper includes a discussion on the method extensions required to deal with asynchronous stacking and heterogeneous batches.