Two-Stage Ant Colony Optimization in the Job Shop Scheduling Problem
We address the Job Shop Scheduling Problem (JSSP), a well-known NP-hard problem, often requiring heuristic approaches. Motivated by a real-world case study of a soda manufacturer, we introduce a novel mathematical formulation tailored to industrial scheduling complexities. Given that exact methods struggle with large-scale instances, we propose a Two-Stage Ant Colony Optimization (TS- ACO) algorithm to generate high-quality schedules efficiently.
Our approach extends existing ant-colony-optimization techniques by integrating a combined perfor- mance measure into TS-ACO. The method effectively handles unrelated parallel machines, precedence constraints, preemption, and sequence-dependent setup times, making it adaptable to complex job shop environments. Moreover, we incorporate industry-relevant objectives, including makespan, total setup time, and a special version of tardiness, which we coin the term of order tardiness. This metric measures the lateness in number of days and inflates it by the size of the production order.
Empirical evaluations demonstrate that TS-ACO matches the exact solutions provided by (Cplex) for small instances within 7%. For the real-life setting of 6 mixing machines, 12 bottling machines, and around 900 jobs, TS-ACO produces high-quality schedules within minutes. In contrast, exact solvers struggle to provide feasible solutions within practical time limits, even with 2 mixing and 4 bottling machines and 224 jobs. These results highlight the scalability and applicability of our TS-ACO to real-world production scheduling problems.