A Hybrid Constrained Programming with Genetic Algorithm for the Job Shop Scheduling Problem

The Job Shop Scheduling Problem (JSSP) is a widely studied NP-hard optimization problem with significant academic and industrial relevance, particularly in the context of Industry 4.0, where efficient scheduling algorithms are crucial for improving decision-making in increasingly automated production systems. Despite extensive theoretical advancements, a gap remains between academic research and real-world implementation, as most studies either focus on theoretical aspects or emphasize numerical advantages while neglecting practical deployment challenges, including those related to computational constraints. To fill this gap, we propose a hybrid optimization approach, hcpga, which integrates a state-of-the-art Constraint Programming (CP) solver, cp-sat, with a custom Genetic Algorithm (ga). The CP solver generates feasible solutions, which are then used to initialize the ga’s population. The ga further optimizes the schedule, minimizing the makespan. Our experimental evaluation on 74 J...