An exact decomposition-based approach to the conflict-free-transportation-constrained flexible job-shop scheduling problem

Automated material handling and transportation of semi-finished products has great potential to enhance the efficiency of Flexible Manufacturing Systems (FMSs). The resulting optimization problems for finding the shortest-makespan manufacturing schedules are complex and often hard to solve. Automated vehicles used for transportation must avoid colliding with one another while completing all required transports in the shortest possible time. The Conflict-Free-Transportation-constrained Flexible Job-Shop Scheduling Problem (CFTFJSSP) is the combination of flexible job-shop scheduling with conflict-free vehicle routing. To solve the CFTFJSSP, we propose an exact Logic-Based Benders Decomposition (LBBD) using both Constraint Programming (CP) and Integer Linear Programming (ILP) techniques. This LBBD-based approach is proven to outperform existing approaches to solving the CFTFJSSP in terms of solution quality on benchmark instances currently available in the literature. For most benchmark instances, our LBBD-based approach finds optimal makespan values. Because of time boxing, only in a few cases, the optimality of the found solution cannot be guaranteed. The solutions found by our LBBD-based approach show a makespan improvement of at least 10% for about half of the benchmarks instances, up to a 35% improvement in the best case, when compared to the heuristic solution approaches from the literature.