An exact decomposition-based approach to the conflict-free-transportation-constrained flexible job-shop scheduling problem
针对无冲突运输约束的柔性作业车间调度问题，提出一种精确的逻辑Benders分解方法，结合约束规划和整数线性规划，在基准实例上找到最优或更优的完工时间，相比启发式方法改进至少10%。
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.