Near-Optimal Dynamic Scheduling for Complex Manufacturing: A Constraint-Based Method with Real-Time Adaptation

Abstract

This work addresses Dynamic Scheduling with Real-Time Order Release in Complex Manufacturing Environments. Our approach employs a constraint programming model to dynamically integrate newly released orders into existing schedules without modifying the deadlines of previously scheduled tasks. An order comprising a set of jobs is scheduled to ensure its earliest possible delivery. Our approach consists of a backtracking heuristic that initially constructs a feasible solution, which is subsequently refined using a constraint programming solver. We developed a simulator to evaluate our method and adapted static instances from the literature of the generalized flexible job shop scheduling problem for testing. Our results demonstrate that within one minute, our algorithm achieves near-optimal solutions every time a new order is released. We also assess the quality of our solutions against a deterministic approach, where job release times are known in advance. This comparison highlights the efficacy of our dynamic scheduling method in complex, constraint-rich manufacturing settings.