An Adaptive Genetic Algorithm for Solving Job-Shop Scheduling Problems

Guilherme de Souza Ferreira¹; Heder Soares Bernardino¹

¹ Universidade Federal de Juiz de Fora

doi:10.20906/CPS/CILAMCE2017-1128

Resumo

Flexible Job-Shop Scheduling Problem (FJSP) is a problem of the manufacturing environment where jobs are scheduled with the objective of optimizing the key performance indicators chosen by the decision-maker. In the literature, metaheuristics are normally applied to this kind of problem due to their ability on finding right solutions. However, the selection of suitable parameters can be a hard task, as they are problem-dependent. In fact, right parameter settings are usually obtained by a trial and error process. This work proposes an adaptive genetic algorithm for solving FJSPs with identical parallel machines with the objective of reducing the makespan. The use of this type of algorithm is a trend in the evolutionary computation as they automatically choose the movement operators (such as crossover and mutation) and their respective parameters, reducing the time of setup and test of an algorithm. Also, our proposal includes a well-known heuristic to initialize the individuals, three crossover operators and two mutation operators. The proposed adaptive technique was tested using instances of different sizes, such as 10 X 10, 20 X 10, 20 X 20, 50 X 10, and 50 X 50 (jobs X stages). A genetic algorithm is considered to evaluate the quality of the obtained solutions comparatively. The results indicate that the use of adaptation improves the reliability of the search method when solving a large number of instances of FJSP.

Palavras-chave: Genetic algorithms; Adaptive operator selection; Adaptive parameter control; Adaptive pursuit; Job-shop scheduling