Algoritmos genéticos adaptativos para solucionar problemas de sequenciamento do tipo job-shop flexível

Abstract

Scheduling is a combinatorial optimization problem, in which one tries ordering the tasks to be performed in the processing units. The objective is to achieve the best values with respect to the performance indicators chosen by the decision-maker, such as, minimize the makespan and minimize the total lateness. The Flexible Job-Shop Scheduling Problem (FJSP) belongs to this category, and its characteristics are the different technological routes for the tasks and that each stage may consist of more than one machine. This is the technological core of the production management, as better schedules may reduce the manufacturing time, reduce the inventory, deliver the order in the right time, and raise the reliability of the process and the company. Exact methods, as they are computationally expensive, are usually employed for small scheduling problems, then heuristic and metaheuristic methods become interesting techniques for this type of problem. Metaheuristics are important to solve FJSPs as they are faster than the exact methods, and among then, Genetic Algorithms (GAs) are one of the most used techniques to solve FJSPs and, currently, they have been hybridized with local search and heuristics to initialize their population. However, to set up GAs is a hard-work and often generates another optimization problem. Adaptive Genetic Algorithms (AGAs) were introduced to work around this problem as they adapt the parameters of the GAs during the search process. Therefore, the objective of this dissertation is to analyze different adaptive techniques developed for AGAs with the purpose of reducing the setup time of GAs when they are applied to FJSPs. In addition, modifications will be proposed for the operator selection techniques and for credit assignment schemes. The studies were performed in instances of different sizes, and the AGAs are compared with traditional GAs. Two different analyzes were performed based on scenarios in which the decision maker does not has to much time to configure the algorithms. In Analysis I, some AGAs performed similarly to the traditional GAs, but they are more interesting as they have a smaller number of parameters, thus a shorter configuration time. In Analysis II, some AGAsgeneratedbetterresultsthanthoseobtainedbyGAs, whichmakesthemappropriate for the case when there is uncertainty in the production process and the decision maker does not have too much time to configure the algorithm.