A Novel Extremal Optimization Approach for the Template Design Problem

A Novel Extremal Optimization Approach for the Template Design Problem

Thomas Weise (University of Science and Technology of China, China) and Raymond Chiong (Swinburne University of Technology, Australia)
DOI: 10.4018/joci.2011040101
OnDemand PDF Download:
No Current Special Offers


This paper presents a novel algorithm based on extremal dynamics for tackling the template design problem, a constrained optimization problem that originated in the printing industry. The template design problem involves printing several variations of a design onto one or more stencil sheets, where the aims are to minimize the number of stencils as well as the overproduction of prints of a particular design. In this paper, the authors introduce several search operators to be used in conjunction with the proposed algorithm. Different combinations of these search operators are tested via extensive numerical experiments. The solutions indicate that the algorithm is a feasible approach for template design optimization. In particular, hybridizing it with a deterministic local search has proven to be very effective.
Article Preview

2. The Template Design Problem

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.


Complete Article List

Search this Journal:
Open Access Articles
Volume 12: 4 Issues (2022): 2 Released, 2 Forthcoming
Volume 11: 4 Issues (2021)
Volume 10: 4 Issues (2020)
Volume 9: 4 Issues (2019)
Volume 8: 4 Issues (2018)
Volume 7: 4 Issues (2017)
Volume 6: 4 Issues (2016)
Volume 5: 4 Issues (2015)
Volume 4: 4 Issues (2014)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing