Evolutionary Optimization for Job Shop Scheduling with Blocking: A Genetic Algorithm Approach

The Blocking Job Shop Scheduling Problem (BJSSP) is a variant of the classical Job Shop Scheduling Problem in which a job completed on one machine cannot be transferred to the next machine until the latter becomes available, causing the current machine to remain blocked. Numerous real-world applications have been modeled as the BJSSP, which is classified as a strongly NP-hard problem. Previous studies indicate that several proposed approaches fail to guarantee the generation of feasible solutions during the search process, thereby requiring a solution reconstruction. In this study, we propose a Genetic Algorithm (GA) designed to operate strictly within the feasible solution space of the BJSSP, where the objective function is the minimization of the makespan. Experimental results show that no specific factor levels significantly influenced the solution quality obtained by the GA across all problem sets. On the other hand, incorporating an assignment operator into the solution representation enhanced the diversity of the population. The proposed GA yields solutions that outperform some of the best-known makespan values for the Lawrence benchmark problems. The runtime of the GA ranged from 20 s for instances with 10 jobs and five machines to 600 s for instances with 30 jobs and 10 machines.