Genetic algorithm with forward-backward scheduling for job-shop problems

When the standard genetic algorithm is applied into job-shop scheduling problems,it has the common defects of early convergence and easily falling into local minimization.A dynamic double-population genetic algorithm based on domain knowledge is applied into job-shop scheduling problems.Since the optimal schedule is active,the active scheduling technique is used to reduce the search space.Moreover,the forward and backward scheduling strategies are adopted to improve the population diversity by the two subpopulations,respectively.A new chromosome encoding is used to represent the active schedule.With this coding scheme,the initialization strategy,the genetic operations of every subpopulation and the crossover operator between the two subpopulations are proposed.Experimental results of the Benchmark instances taken from literatures indicate that it outperforms current approaches in computational time and quality of the solutions.