Genetic Algorithm and Simulated Annealing for Flexible Job Shop Scheduling Problem with Time Constraints

Abstract

In this work, we investigate the Scheduling for Laboratory Automation in Biology (S-LAB) problem, which arises in time-sensitive laboratory workflows. S-LAB is an extension of the Flexible Job Shop Scheduling Problem (FJSP) with Time Constraints by Mutual Boundaries (TCMB). We proposed a hybrid Genetic Algorithm- Simulated Annealing (GASA) approach that combines the global exploration capabilities of genetic algorithms with the local refinement strength of simulated annealing. The genetic algorithm component employed a novel triple encoding scheme incorporating Operation Sequence, Machine Selection, and Operation Delay to effectively represent scheduling solutions under strict time constraints. We conducted comprehensive experiments on multiple realistic laboratory protocol datasets to compare the performance of GASA with those of the Branch and Bound (B&B) and SAGAS algorithms. The results demonstrated that GASA achieved optimal solutions in simpler scenarios and near-optimal results in complex cases with significantly reduced computational time compared to B&B. On the most complex dataset (qPCR-RNAseq×5), GASA reduced execution time by more than 96% while incurring only a 10.1% increase in makespan relative to the optimum. The proposed approach provides an effective balance between solution quality and computational efficiency, making it particularly suitable for time-sensitive laboratory automation applications.