The Cover Printing Problem
Home
Contact Details
David Romero
Universidad Nacional Autónoma de México (UNAM)
Email: davidr@matcuer.unam.mx
UNAM
The cover printing problem is an NP-hard problem [3] arising in a printing shop [1—15].
Let M = {1,..., m} be a set of different book covers (or
advertisements, labels, tracts, etc.) of equal size, and suppose that di
copies are to be printed of cover i, for i
M. Suppose that for each print an unlimited number of identical plates can
be
made, and that an impression grid
— also called master or template— can accommodate a specified number of t plates. The printing
process is:
1. Compose an impression grid of t plates (some of them can be identical),
and make a
certain number of imprints with it. Each imprint produces one large printed
sheet of
paper which, once properly cut into t parts, yields t copies.
2. Repeat step 1 until all the required copies are made.
The printing cost comes from two sources: a per impression cost C1, and a fixed cost C2 for composing one impression grid (or grid, for short). Thus, the problem consists in determining the number of grids, the composition of each grid (which plates?), and the number of imprints made with each grid, so as to fulfill the copies' requirement at minimum total cost.
Mathematical Formulation
Recall M = {1,..., m} and let N = {1,..., n}. Namely,
is the total number of distinct grids. Consider the integer, no-negative m-by-n matrix {aij} whose columns are all pairwise distinct, each column corresponding to a possible impression grid.
For (i, j)
M
×
N the number of plates of cover i in grid
j is represented by
aij . Obviously
Thus the cover printing problem — also referred to as advertisement printing or label printing problem or job splitting problem — can be formulated as one of integer nonlinear optimization:
Several approaches have been proposed for this difficult combinatorial optimization problem. This website contains all (known to us) instances of the cover printing problem together with their known best solutions. All the datasets can be download here.
References
[1] D. Romero, F. Alonso-Pecina, Ad hoc Heuristic for the Cover Printing Problem, submitted to Elsevier
[2] Q.-S. Hua, Y. Wang, D. Yu, and F.C.M. Lau, Dynamic programming based algorithms for set multicover and multiset multicover problems, Theoretical Computer Science 411 (2010) 2467--2474.
[3] A. Ekici, O. Ergun, P. Keskinocak, and M.G. Lagoudakis, Optimal Job Splitting on a Multi-Slot Machine with Applications in the Printing Industry, Naval Research Logistics 57 (2010) 237--251.
[4] M. Balinski, A printing shop problem, personal communication, 1974.
[5] M. Naya, Problème du mariage des couvertures posé par la S.A. Casterman, Graduate Thesis, Faculté Polytechnique de Mons, Belgium, 1986.
[6] C. Antoniadis, Problème du mariage des couvertures: Résolution par la méthode du recuit simulé, Graduate Thesis, Université de Mons-Hainaut, Belgium, 1992.
[7] C. Carrein, Problème du mariage des couvertures par la méthode tabou, Graduate Thesis, Faculté Polytechnique de Mons, Belgium, 1994.
[8] G. Fasbender, A branch and price algorithm for the book cover printing problem, Graduate Thesis, Université Libre de Bruxelles, Belgium, 2000.
[9] L.E. Carrera, Algoritmo para encontrar el óptimo a una simplificación de un problema combinatorio presente en la industria editorial, Graduate Thesis, Mathematics Department, Cinvestav, Mexico City, 2006. (in Spanish)
[10] J. Teghem, M. Pirlot, C. Antoniadis, Embedding of linear programming in simulated annealing algorithm for solving a mixed integer production planning problem, Journal of Computational and Applied Mathematics 64 (1995), 91-102.
[11] K.F.C. Yiu, K.L. Mak, H.Y.K. Lau, A heuristic for the label printing problem, Computers and Operations Research 34 (2007), 2576-2588
[12] S. Elaoud, J. Teghem, B. Bouaziz, Genetic algorithm to solve the cover printing problem, Computers & Operations Research 34 (2007), 3346-3361.
[13] S.R. Mohan, S.K. Neogy, A. Seth, N.K. Garg, S. Mittal, An optimization model to determine master designs and runs for advertisement printing, Journal of Mathematical Modelling and Algorithms 6 (2007), 259-271.
[14] D. Tuyttens, A. Vandaele, Using a greedy random adaptative search procedure to solve the cover printing problem, Computers & Operations Research, Volume 37, (2010) Issue 4, 640-648.
[15] L. Trilling, Personal Communication, 2006.