The template design problem is a constrained optimization problem usually modeled as a bi-objective optimization problem (Proll & Smith, 1998). Here, the aims are to minimize both the number of stencils and the overproduction of prints of a particular kind. These are conflicting objectives, and for most problem instances, there will be no ideal solution which accommodates both objectives. Despite its seeming simplicity, template design is a hard problem to solve.
2.1. Problem Description
Template design optimization has its application in the printing industry, where product flyers or product containers have to be printed on paper or thin cardboard, depending on the delivery ordered. The printing press uses “stencil” sheets which accommodate the templates or blueprints of the items to be printed. The flyers or containers may be needed in different colors and with different descriptions, according to slight product variations, but they are usually of identical size. A practical example is a commercial order for cat food cartons, where the cat food comes in several different flavors. The size of the template dictates the number of “slots” available for templates on a stencil sheet.
Orders for prints, such as cat food containers, may contain different quantities for each variation of the print, as shown in Figure 1. Each variation of the print has to be represented by at least one template on one or more of the stencil sheets. As stencil sheets are expensive to produce, one of the optimization criteria is minimizing the number of sheets used. To satisfy a customer, print variations have to be created in at least the ordered quantities. Depending on the layout of the stencils and the types of templates included, it is likely that the minimal number of pressings per stencil, given by the ordered quantities, will cause overproduction of one or more of the print variations, such as different cat food cartons. Minimizing this overproduction is the second criterion, for which it becomes necessary to optimize the number of prints per stencil.
Figure 1. Templates for different variations of prints laid out on a stencil sheet. Given the size of the templates, this stencil has five slots.