Enhancing Search Efficiency of Evolutionary Algorithm for Job Shop Scheduling Problem via Predetermined Sub-optimal Solutions

This paper introduces a novel evolutionary algorithm for the Job Shop Scheduling Problem (JSSP) using Genetic Algorithm (GA). The methodology incorporates a new fitness function that aligns with the intrinsic nature of JSSP, improving search efficiency for makespan optimization. The study proposes three enhancement methods for GA, based on analyzing Machine Input Order (MIO) Score derived from Machine-Job Sequence (MJS) and Machine-Operation Sequence (MOS). These methods intuitively leverage JSSP's structure, initiating searches from near-optimal solutions regardless of problem size. This approach is expected to significantly improve GA's efficiency, especially for larger problems.