Solving a bi-criterion cutting stock problem with open-ended demand: a case study

We consider a real-life cutting stock problem with two types of orders. All orders have to be cut from a given number of raws (also known as stock unit, master reel or jumbo). For each order the width of the final (also known as reels or units) and the number of finals is given. An order is called an exact order when the given number of finals must be produced exactly. An order is called an open order when at least the given number of finals must be produced. There is a given maximum on the number of finals that can be produced from a single raw which is determined by the number of knives on the machine. A pattern specifies the number of finals of a given width that will be produced from one raw. A solution consists of specifying a pattern for each raw such that in total the number of finals of exact orders is produced exactly and at least the number of finals of open orders is produced. There are two criteria defined for a solution. One criterion is the cutting loss: the total width of the raws minus the total width of the produced finals. The second criterion is the number of different patterns used in the solution. We describe a branch-and-bound algorithm that produces all Pareto-optimal solutions.