An application of combinatorial optimization in the printing industry

Offset printing is a common method to produce large amounts of
printed matter. We consider a real-world offset printing process that is
used to imprint customer-specific designs on napkin pouches. The print-
ing technology used yields a number of specific constraints. The planning
problem consists of allocating designs to printing-plate slots such that
the given customer demand for each design is fulfilled, all technologi-
cal and organizational constraints are met and the total overproduction
and setup costs are minimized. We formulate this planning problem as a
mixed-binary linear program, and we develop a multi-pass matching-based
savings heuristic. We report computational results for a set of problem
instances devised from real-world data.