A Heuristic Algorithm for the Guillotine Constrained Cutting Stock Problem

This paper presents a heuristic algorithm, programmed in PROLOG (a rule-based programming language) and run on a personal computer with 4.77 MHz CPU, for determining the packing of identical rectangles (boxes) onto a larger rectangle (pallet) such that the amount of waste is minimized. The algorithm has the additional property of producing solutions which satisfy the guillotine cut constraint. The rule-based approach takes advantage of the recursive and backtracking properties to expedite the matching operations. The algorithm is tested using 7500 randomly generated test cases and is compared to other cutting stock algorithms. Test results for one set of problems indicate that the rule-based method generates layout solutions that are within one box of the optimal solution 85% of the time.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.