Algorithms for order cutting in the paper industry

More than 35 years after Gilmore and Gomory published their column generation algorithms for linear programming of the cutting stock problem, available software has not always been readily accepted in industry. The task of accepting all customer orders for a particular product grade and producing a completed production plan that can be passed to the production crew (or the direct control of the finishing equipment itself) is rarely left as a ‘hands-off’, automatic process. This paper reviews theoretical developments adopted in software since 1963 and relates these to specific applications encountered in paper mills of various configurations. The paper presents the underlying computer science using schematics rather than heavy mathematical notation and concentrates on explaining the practical limitations of various approaches. The paper argues that significant advances have been made, but presents a series of requirements which still await theoretical breakthroughs from the computer scientists or operations research experts. The weaknesses of existing software in relation to the time sequencing of the slitting and cutting operations is discussed and several new hybrid solution approaches are proposed. Issues related to tighter customer delivery scheduling, high priority or urgent orders, last-minute orders and ‘seamless’ production plan changes are discussed.