Abstract: To address the Flexible Job shop Batch Scheduling Problem with Variable Sublots (FJBSP-VS) aiming at minimizing the maximum completion time,an improved Sparrow Search Algorithm combined with Tabu Search (Tabu Search-Sparrow Search Algorithm,TS-SSA) was proposed for the integrated optimization of job batching,machine selection,and sublot sequencing.Firstly,a two-layer encoding method was designed to represent job batching,machine selection information,and sublot sequencing information,along with a decoding method that integrates no-delay scheduling to effectively improve the machine utilization. The Sparrow Search Algorithm (SSA) was discretized while retaining the producers-scroungers structure by introducing a crossover operator to solve discrete problems.Additionally,the choice of the target close to the scrounger was improved to enhance the global search ability of the algorithm.Furthermore,the combination of Tabu Search (TS) with the improved SSA enhances the local search ability of the algorithm.Finally,experiments were conducted using 27 existing public examples to verify the effectiveness and superiority of the TS-SSA algorithm.

Key words: flexible job shop problem, batch scheduling, Sparrow Search Algorithm (SSA), Tabu Search (TS)