To improve the Makespan of a Standard Job Shop Scheduling problem incorporating GA by using Python

Abstract

Effective job scheduling is crucial in industrial manufacturing planning, where each job, consisting of multiple operations, must be allocated to the machines that are available machines for processing. Each job has a specific interval, and every machine can only handle one operation at a time. Efficient job allocation is essential to minimise the makespan and reduce machine idle time. In Job Shop Scheduling (JSS), job operations follow a specified order. Genetic Algorithms (GA) have emerged as a popular heuristic for tackling various scheduling problems. This study introduces a Genetic Algorithm Integrating Python (GAIP) with feasibility-preserving solution representation, initialization, and operators tailored for the JSS problem. The proposed GAIP achieves the best-known results with high success rates on the Muth and Thomson and Lawrence benchmark datasets. Experimental results demonstrate the GA's rapid convergence towards optimal solutions. Incorporating GA with local search and two selection methods at the same time is done to further enhance solution quality and success rates.