Optimizing Job Shop Scheduling with Alternative Routes: A Metaheuristic Approach

Abstract

Job shop scheduling with alternative routes (JSS-AR) presents a critical optimization challenge in modern manufacturing, where jobs can follow multiple paths through machines to enhance flexibility. This study addresses the NP-hard problem of minimizing makespan in JSS-AR by evaluating genetic algorithms (GA), simulated annealing (SA), ant colony optimization (ACO), and a novel hybrid GA-ACO. Computational experiments on benchmark instances demonstrate that the hybrid GA-ACO achieves the lowest makespan (4.1% deviation from theoretical bounds) by synergizing ACO’s exploratory routing decisions with GA’s refinement. SA offers rapid solutions for time-sensitive scenarios, while ACO excels in large-scale problems. The findings provide actionable guidelines for improving production efficiency and resource utilization in dynamic manufacturing environments.