Finding Pattern Configurations for Bank Cheque Printing

The problem we address in this paper arises in large-scale manufacturing of bank cheques. Due to security reasons, the cheques must be printed on special (expensive) paper. The first step in the printing process is to prepare the plates that will be used by the composing machine. If the imprint (image) of a particular cheque is on a plate, each time the composing machine uses this plate a new cheque of this type is produced. Each plate has a predefined number of positions to be impressed. Due to delivery due dates, there is an additional constraint requiring each cheque not to be present in more than a predefined number of different plates. There are two different production costs that have to be considered: overproduction costs and printing costs. Each overproduced cheque can be either destroyed or stored in a proper location under surveillance. Both these alternatives have a huge environmental impact, indeed, on the one hand, paper waste is produced, while, on the other hand there is a huge energy consumption. The problem consists in defining the pattern (i.e. the configuration of cheque images) of each plate to be used and the corresponding frequency, such that total costs are minimized. We study this real world problem that is strictly related to the cutting stock problem with pattern minimization. Such a problem is addressed actually by a large cheque manufacturer in Southern part of Italy. We define a very efficient heuristic to solve it. The proposed solution methodology is currently used by the above mentioned manufacturer to define the cheque allocation of the plates.