Improved Genetic Algorithm for Single Machine Scheduling Problems with Deteriorating Jobs

To reduce the computational load of the existing algorithms for solving the large-size single machine scheduling problem, an analysis was made of the scheduling rule of the problem with stepwise deteriorating jobs, and an improved genetic algorithm (IGA) based on local search was proposed to minimize the makespan. In the IGA, a linear order crossover operator and a mutation operator based on the property of deteriorating jobs sequencing were designed for the chromosome using job-based encoding. Moreover, a local search technique was incorporated to enhance the local search ability and speed up the convergence of the proposed algorithm. The experimental results show that the makespan of the IGA is averagely about 56.6% lower than that of the simulated annealing algorithm in the case of 40 jobs. The proposed algorithm can avoid the local optimal solutions and accelerate the convergence rate.