The genetic algorithm with search area adaptation (GSA) has a capacity for adapting to the structure of solution space and controlling the tradeoff balance between global and local searches, even if we do not adjust the parameters of the genetic algorithm (GA), such as crossover and/or mutation rates. But, GSA needs the crossover operator that has ability for characteristic inheritance ratio control. In this paper, we propose the modified genetic algorithm with search area adaptation (mGSA) for solving the Job-shop scheduling problem (JSP). Unlike GSA, our proposed method does not need such a crossover operator. To show the effectiveness of the proposed method, we conduct numerical experiments by using two benchmark problems. It is shown that this method has better performance than existing GAs.
Scheduling problems exist almost everywhere in real-world situations (Gen & Cheng, 1997), especially in the industrial engineering world. Many real scheduling problems in the manufacturing industries are quite complex and very difficult to be solved by conventional optimization techniques. Usually, these difficult-to-solve problems are characterized as combinatorial optimization problems subject to highly complex constraints.
Stochastic optimization methods, such as the Genetic Algorithm (GA), have been applied to many difficult combinatorial optimization problems (Tamaki & Sannomiya, 1998). Those methods have to be equipped with both global and local search abilities for good performance. Since it is often hard to satisfy the requirements of both global and local optimization simultaneously, the methods have to consider the tradeoff between these two goals. Although there are some existing methods that conquer this difficulty by the adjustment of several parameters, it is not so easy to adjust them properly (Someya and Yamamura, 1999a and Someya and Yamamura, 1999b).
GA has shown a good performance regarding its ability to search globally. It starts searching with population and multiple points in the search space. It also and has an operator called crossover, which enables to search over wide region. However, for the proper tradeoff balance, adjusting parameters, such as crossover rate and mutation rate, is necessary for GA.
A genetic algorithm with search area adaptation (GSA) was proposed by Someya and Yamamura, 1999a, Someya and Yamamura, 1999b and Someya and Yamamura, 2001. It is developed from GA, considering the roles of genetic operators. GSA has capacity for adapting to the structure of solution space and controlling the tradeoff balance between global and local search abilities dynamically. It had been confirmed that GSA shows good performance for several Floorplan-design-problem instances (Someya and Yamamura, 1999a and Someya and Yamamura, 1999b). But, GSA needs a crossover operator with an ability of characteristic inheritance ratio control.
In this paper, we propose the modified GSA (mGSA) for solving the job-shop scheduling problem (JSP) that does not need such crossover operator. It is shown that this method has better performance than existing GAs. This paper is organized as follows: in Section 2, we introduce scheduling problem. GSA is introduced in Section 3. In Section 4, we propose mGSA for solving job-shop scheduling problems. In Section 5, we show several experimental results in comparison to those of existing GAs.
In this paper, we proposed the modified GSA and reported several experimental results on job-shop scheduling problems. We observed the improved performance of mGSA in comparison with GA. In the future, we shall choose the instances from which the structure of the solution space differs clearly, and shall conduct more numerical experiments.
