Análise da influência das soluções inicias no desempenho dos algoritmos genéticos em problemas de sequenciamento da produção em ambientes job shop

Abstract

In this work was used the genetic algorithms metaheuristic technique together with FIFO heuristics; LPT and SPT to handle the problem of sequencing of production orders in job shop environments. These heuristics were applied to the initial populations and submitted to the genetic algorithm for solution convergence. Were used test exemplaries, available in OR-Library, an operational research library commonly used by researchers to conduct studies on the operational area. Such exemplaries have like the characteristic of the availability of production orders for zero-time allocation and fixed processing times. All development was done in C ++ language, coupled with a genetic algorithm library called GALib, besides the development of the function of evaluation of the solutions generated by the genetic algorithm. Each experiment was performed starting from an initial solution ordered according to FIFO heuristics; FIFO + SPT and FIFO + LPT, besides an initial seed not feasible and another with an adaptation of the NEH heuristic developed by Nawas; Enscore and HAM, whose initials gave rise to the name of heuristic. The results section shows that with the use of the NEH heuristic adaptation, there were gains in the average gap reached in the iterations and in the average processing time of the genetic algorithm, as well as a gain in the average number of non-feasible solutions generated by the genetic algorithm.