  In this work, the online printing shop scheduling problem introduced in
(Lunardi et al., Mixed Integer Linear Programming and Constraint Programming
Models for the Online Printing Shop Scheduling Problem, Computers & Operations
Research, to appear) is considered. This challenging real scheduling problem,
that emerged in the nowadays printing industry, corresponds to a flexible job
shop scheduling problem with sequencing flexibility; and it presents several
complicating specificities such as resumable operations, periods of
unavailability of the machines, sequence-dependent setup times, partial
overlapping between operations with precedence constraints, and fixed
operations, among others. A local search strategy and metaheuristic approaches
for the problem are proposed and evaluated. Based on a common representation
scheme, trajectory and populational metaheuristics are considered. Extensive
numerical experiments with large-sized instances show that the proposed methods
are suitable for solving practical instances of the problem; and that they
outperform a half-heuristic-half-exact off-the-shelf solver by a large extent.
Numerical experiments with classical instances of the flexible job shop
scheduling problem show that the introduced methods are also competitive when
applied to this particular case.
