An Improved Ant Colony Optimization Algorithm for the Flexible Job Shop Scheduling Problem

Abstract

The Flexible Job Shop Scheduling Problem (FJSP) is a critical combinatorial optimization problem in modern manufacturing systems, characterized by multiple constraints, dynamic requirements, and NP-hard complexity. This paper presents an improved Ant Colony Optimization (ACO) algorithm specifically designed to address the FJSP by minimizing makespan. The proposed algorithm incorporates enhanced pheromone update mechanisms, dual-level solution encoding for operation sequencing and machine assignment, and adaptive search strategies. Experimental results on a benchmark problem with 4 jobs, 3 processes per job, and 6 machines demonstrate that the improved ACO achieves superior performance compared to traditional metaheuristics, reducing makespan by approximately 8.7% compared to genetic algorithms. The convergence analysis shows stable optimization behavior within 40 iterations, validating the effectiveness and practical applicability of the proposed approach.