Journal Article

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

Rodríguez-Velásquez, Elkin, Valencia, John

2026

Overview

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.

• Publisher: MDPI AG
• Subject: Algorithms / Analysis / Artificial intelligence / blocking job shop scheduling / genetic algorithm / Genetic algorithms / Genetic research / Graph representations / Heuristic / Job shop scheduling / Job shops / Linear programming / Literature reviews / Manufacturing / no buffer job shop scheduling / Operators (mathematics) / Optimization / Scheduling / Search process / Solution space