Tool Switching Problems in the Context of Overlay Printing with Multiple Colours

This paper addresses problems arising in the context of overlay printing with multiple colours, where a finite set of jobs must be sequentially performed by a printing machine which can simultaneously accommodate a limited number of colours. Each job is associated with a subset of colours that the machine must have stored in its magazine before starting the execution. Thus, some colour switches may be required between the execution of two consecutive jobs. Since colour switches imply a reduction of productivity, minimizing them is desirable. In this regard, we address three distinct problems of increasing difficulty. All these problems can be seen as variants of the Tool Switching Problem, where each colour is treated as a tool. For each problem we discuss its complexity and propose a mathematical programming model. We evaluate the effectiveness of the models on several instances that have been generated with the aim of covering different scenarios of interest.