Job Shop Scheduling Problem Based on an Improved Genetic Algorithm

Abstract

The Job Shop Scheduling Problem (JSP) is a core decision-making issue for improving production efficiency in discrete manufacturing industries. Traditional genetic algorithms (GAs) used to solve JSP suffer from bottlenecks such as a high number of invalid solutions and difficulty in balancing solution accuracy and convergence speed. To address large-scale JSP under dynamic machine fault disturbances, this study proposes an improved genetic algorithm integrating hybrid encoding and customized operators. Specifically, a hybrid encoding strategy combining job sequences and machine sequences is adopted to naturally satisfy the process and equipment constraints of JSP. The evolutionary process is optimized using tournament selection, Position-based Order Crossover (POX), and mutation within the valid domain, while a fault identification and machine switching mechanism is integrated to adapt to dynamic disturbance scenarios. Experimental results show that the improved algorithm achieves an optimal Makespan value of 190 in dynamic disturbance scenarios and exhibits strong robustness, providing an efficient and feasible solution for job shop scheduling in complex production environments.