Improved genetic algorithm for the job-shop scheduling problem

摘要

In this paper, an improved genetic algorithm, called the hybrid Taguchi-genetic algorithm (HTGA), is proposed to solve the job-shop scheduling problem (JSP). The HTGA approach is a method of combining the traditional genetic algorithm (TGA), which has a powerful global exploration capability, with the Taguchi method, which can exploit the optimal offspring. The Taguchi method is inserted between crossover and mutation operations of a TGA. Then, the systematic reasoning ability of the Taguchi method is incorporated in the crossover operations to systematically select the better genes to achieve crossover, and consequently enhance the genetic algorithm. Therefore, the proposed HTGA approach possesses the merits of global exploration and robustness. The proposed HTGA approach is effectively applied to solve the famous Fisher-Thompson benchmarks of 10 jobs to 10 machines and 20 jobs to 5 machines for the JSP. In these studied problems, there are numerous local optima so that these studied problems are challenging enough for evaluating the performances of any proposed GA-based approaches. The computational experiments show that the proposed HTGA approach can obtain both better and more robust results than other GA-based methods reported recently.