New integer programming formulations and an exact algorithm for the ordered cutting stock problem

Abstract

Apart from trim loss minimization, there are many other issues concerning cutting processes that arise in real production systems. One of these is related to the number of stacks that need to be opened near the cutting machines. Many researchers have worked in the last years on cutting stock problems with additional constraints on the number of open stacks. In this paper, we address a related problem: the Ordered Cutting Stock Problem (OCSP). In this case, a stack is opened for every new client's order, and it is closed only when all the items of that order are cut. The OSCP has been introduced recently in the literature. Our aim is to provide further insight into this problem. This paper describes three new integer programming formulations for solving it, and an exact algorithm based on column generation, branch-and-bound and cutting planes. We report on computational experiments on a set of random instances. The results show that good lower bounds can be computed quickly, and that optimal solutions can be found in a reasonable amount of time.

Keywords:

• cutting stock
• pattern sequencing
• integer programming models
• column generation
• branch-and-bound
• cutting planes

Acknowledgements

This work was partially supported by the portuguese Science and Technology Foundation (Projecto POS C/57203/EIA/2004) and by the Algoritmi Research Center of the University of Minho, and was developed in the Industrial and Systems Engineering Group.