A Real-World Flexible Job Shop Scheduling Problem With Sequencing Flexibility: Mathematical Programming, Constraint Programming, and Metaheuristics

In this work, the online printing shop scheduling problem 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 that includes several complicating specificities such as resumable operations, periods of unavailability of the machines, sequence-dependent setup times, partial overlapping between operations with precedence constraints, fixed operations, among others. In the present work, a mixed integer linear programming model, a constraint programming model, and heuristic methods such as local search and metaheuristics for the minimization of the makespan are presented. Modeling the problem is twofold. On the one hand, the problem is precisely defined. On the other hand, the capabilities and limitations of a commercial software for solving the models are analyzed. Numerical experiments show that the commercial solver is able to optimally solve only a fraction of the small-sized instances when considering the mixed integer linear programming formulation. While considering the constraint programming formulation of the problem, medium-sized instances are optimally solved, and feasible solutions for large-sized instances of the problem are found. Ad-hoc heuristic methods, such as local search and metaheuristic approaches that fully exploit the structure of the problem, are proposed and evaluated. Based on a common representation scheme and neighborhood function, trajectory and populational metaheuristics are considered. Extensive numerical experiments with large-sized instances show that the proposed metaheuristic methods are suitable for solving practical instances of the problem; and that they outperform the half-heuristic-half-exact off-the-shelf constraint programming solver. 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.