All cut up, and in the dark

Kodak manufacturers photographic film in 6km rolls, which then have to be cut up. A classic cutting stock problem? No, there are practical factors which make it harder than that

by Robert Simons, Eudoxus Ltd

Kodak has over 80 manufacturing sites worldwide making products as diverse as dental X-ray film, 35mm photographic film, photographic paper and disposable cameras. With the exception of the cameras, Kodak manufactures its product in large rolls which are then cut up and packaged into finished products. This is the classic cutting stock problem.

Until recently Kodaks plants have used an assortment of computer systems with an essentially manual approach to the cutting stock problem. In 1995 Kodak began implementation of a single Enterprise Resource Planning (ERP) system to cover their operations worldwide. This was based around SAP R/3 with Manugistics supply-chain scheduling software. Some way into the project it became apparent that specialist software was required to tackle the cutting-stock problem and decide how the orders were actually to be cut from the large rolls. This software would sit between the ERP system and the shop floor systems and generate detailed instructions as to what to do next. On the strength of its expertise and its Deckle Bench product, Greycon was selected to provide the solution.

System architecture

Greycons initial plan was to modify DeckleBench to tackle Kodaks problem. It soon became apparent, however, that Kodak had not one but six technically distinct problems and that special-purpose algorithms would have to be developed for each. Greycons experience led it to propose that the algorithms should not generate a single solution but a range of solutions from which the user could select the most appropriate and be able to modify it manually. An additional problem adviser module would assist by giving advice as to why a particular solution had been found and how to change the control parameters of the problem to achieve a solution closer to what was really wanted.

One challenge in designing the system was the variety of shop-floor systems with which it would have to interface. There was also concern about accessing the main SAP database directly. In order to provide a degree of systems independence, it was decided to adopt the architecture shown in Figure 1. A purpose-built database is used for the cutting-stock problems, into which data are loaded from SAP. The results pass to the shop-floor systems through another interface. The users interact with the system through a front-end to the database while the algorithms act as a back-end to the database.

Problem characteristics

In the paper industry most cutting-stock problems are tackled at the planning stage, i.e. before the material has been manufactured. This brings with it a number of simplifications:

all the large rolls are of equal length;
they are assumed to be of perfect quality;
one cutting pattern is used for each large roll.

Kodaks problem, on the other hand, is solved after the material has been manufactured. This means that solutions have to take account of:

variations in the length of the large rolls - typically by 20 - 30m on a 6km roll;
imperfections, which can occur anywhere in the roll and be arbitrarily complex;
the possibility of using more than one cutting pattern for a single large roll and of rehanging the roll, i.e. returning the unused portion to the store.

As with paper-industry problems, there is some tolerance on the order quantity which must be made and there may also be optional orders which do not need to be made at all (typically these are being made for stock). This flexibility provides scope for optimisation and enables waste to be minimised. In practice, although Kodak were ostensibly very concerned about minimising waste, there is actually a trade-off between incurring waste and spending time setting up cutting patterns. Setting-up must be done to a very high precision - a 4 x 6 sheet of photographic paper is actually 3.965 wide, for instance - and is done in the dark, with the result that it can take an hour or more.

There can thus be a range of potential solutions, with different numbers of set-ups, different levels of waste and different quantities of the optional orders being made. This is where the user must exercise his judgement to select a solution based on knowledge of what else is going on. For instance, if demand is high and the machines are running flat-out, a solution with higher waste will be preferred if it reduces the number of set-ups.

Sheet Square Cut

One of the most challenging of the six distinct cutting-stock problems at Kodak was known as Sheet Square Cut. This is illustrated in Figure 2. The large roll, which is about 1m wide and 6km long, is cut across its width into sheets 500 - 900mm wide by 1m high. The sheets are stacked into piles and then guillotined to make the ordered sizes. As is normal with guillotine patterns, the dissection of the large sheets must be by a series of guillotine cuts, i.e. each cut must divide the sheet being cut into two. A complication is that the resulting sheets must be of diminishing size so that they can be stacked in a pyramid; this is required because the guillotine is being operated in the dark.

The approach which was adopted was to construct a library of feasible dissections for the large sheets. At its simplest, the problem is then to select which large sheets and dissections to use and the run lengths for each of them so that the entire demand is met. This is similar to the standard approach for tackling cutting-stock problems in which patterns are constructed and then a set-covering linear programming model is used to decide how many copies of each pattern should be used.

As with the standard problem, there are complications which correspond to finding an integer programming solution rather than a linear programming one. The large sheets are guillotined in piles which are some multiple of the standard pack size, e.g. 50 sheets, and so the number of copies of a large sheet must be such a multiple too. Similarly, solutions are wanted in which large rolls are consumed in their entirety. To tackle these issues, patterns are constructed for large rolls which use the entire roll in producing acceptable run-lengths of large sheets and these are then combined to solve the problem.

This algorithm was complemented by a greedy heuristic to handle imperfections. In order to mitigate the limitations of such an algorithm, it was run many times, starting at different points and moving randomly around.

Conclusions

The project has been a considerable success and is being implemented progressively at Kodaks sites worldwide. The target response times of 60 seconds for a typical problem have been achieved.

Much that was done has proved to be correct, most notably the system architecture with its isolation of the cutting-stock problems from the ERP system and the shop-floor. Some difficulties were experienced during development, caused mainly by a paucity of test problems. Algorithms would be tested on limited data sets and then be released in prototype modules which would fail their acceptance tests when presented with very different data sets.

With hindsight it has become evident that the importance of set-ups was underestimated and that the algorithms concentrated too much on minimising losses. The use of control parameters for the algorithms has also caused difficulties: even well-disposed users have not understood how to change them to achieve what they wanted. Other users, possibly worried about losing their jobs, have been more hostile. The problem adviser module has proved its worth in helping to address these issues.

This article is based on a talk given by Dr Constantine Goulimis, Managing Director of Greycon Ltd, www.greycon.com, to the Mathematical Programming Study Group. Greycon are the authors of DeckleBench, one of the leading packages for tackling cutting stock problems in the paper industry. Robert Simons is a director of Eudoxus Systems Ltd, www.eudoxus.com, and Secretary of the Mathematical Programming Study Group.