Uma abordagem de otimização utilizando Algoritmo Genético com estratégias de busca local e melhoramento genético para minimização do makespan no problema de programação da produção job shop

Abstract

Many works nowadays use metaheuristics to deal with the class of problems known in the literature as Job Shop Scheduling Problem (JSSP) due to its complexity since it consists of combinatorial problems and belongs to the set of NP-Hard computational problems. In this type of problem, one of the most discussed objectives in the literature is to minimize the makespan, which consists of the maximum production time of a series of jobs. As this is a resource allocation situation, to solve JSSP instances, metaheuristics such as the Genetic Algorithm (GA) are widely used. Although GAs present good results in the literature, it is very common that they present certain deficiencies, such as: stagnation in solutions that are local minimums; difficulty in exploring the search space satisfactorily; premature convergence; among others. To overcome these situations, the use of local search and genetic improvement strategies in GA is proposed in this work. Being the first strategy defined in the form of generalization and improvement of local search techniques existing in the literature. In detail, the concept of massive local search operator was generalized; the use of a local search strategy in the traditional mutation operator has been improved; and a new multi-crossover operator was developed. The second strategy is defined in the form of an operator specialized in directing the population to good regions in the search space. This operator makes it possible to manipulate the genetic material of individuals, adding characteristics that are frequent in well-regarded individuals, with the proposal of directing some individuals in the population who are lost in the search space for a more favorable solution without harming the diversity of the population. In this work, the joining of these strategies is proposed in order to define a framework of GA techniques that have the objective of minimizing the makespan in JSSP instances. The developed material was evaluated in well-established benchmarks in the specialized literature and is competitive and versatile compared to the methods that represent the state of the art.