Reference : A Real-World Flexible Job Shop Scheduling Problem With Sequencing Flexibility: Mathem...
Dissertations and theses : Doctoral thesis
Physical, chemical, mathematical & earth Sciences : Mathematics
Engineering, computing & technology : Computer science
A Real-World Flexible Job Shop Scheduling Problem With Sequencing Flexibility: Mathematical Programming, Constraint Programming, and Metaheuristics
Tessaro Lunardi, Willian mailto [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > >]
University of Luxembourg, ​Luxembourg, ​​Luxembourg
Docteur en Informatique
[en] Scheduling ; Metaheuristics ; Constraint Programming ; Job shop scheduling ; Flexible job shop scheduling ; Production scheduling
[en] 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.

File(s) associated to this reference

Fulltext file(s):

Open access
a-real-world-flexible-job-shop-scheduling-problem.pdfPublisher postprint2.7 MBView/Open

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.