Algoritmo genético híbrido baseado na análise de componentes principais do fitness landscape para o problema de job shop scheduling

Abstract

This work deals with the scheduling problem in a job shop environment, known in the international literature as Job Shop Scheduling Problem (JSSP). Due to their computational complexity, metaheuristics have been commonly employed in their solution, but performance comparable to the state-of-the-art depends on upon an e cient exploration of the solution space characteristics of this problem, through the tness landscape analysis. Brie y, the tness landscape represents a space landscape of the generated solutions - formed by the solutions in space, their tness values, and a notion of neighborhood - and its analysis provides relevant information for improving the optimization method. Thus the objective of this work is the development of a Hybrid Genetic Algorithm (HGA) with diversi cation and intensi cation strategies based on the tness landscape Principal Component Analysis for the Job Shop Scheduling Problem. Therefore, a method based on Principal Component Analysis (PCA) is proposed to evaluate diversity characteristics of solutions of a population, classifying each individual based on their similarity to the others. This classi cation determines an individual contribution rate that is used to select similar solutions that can be substituted in the diversi cation stage. When dealing with suboptimal solutions, the replacement of the selected individual is done considering the best solution found in the intensi cation step. In this case, a Bidimensional Binary Genetic Algorithm (GAB) is used to extend the search region beyond the neighborhood of the selected individual in search of a better solution. Finally, the initial and nal solutions are reconnected and the best solution in the path between them is inserted into the population instead of the one selected by the PCA. Comparing the HGA with a local search method the results show that there was improvement in several instances both in reducing the makespan value and in the number of generations of the algorithm. In relation to other approaches referenced in the literature, HGA obtained competitive results for some instances, but it is still necessary to re ne the method for larger problems, which is dependent on the adequate choice of HGA parameters and the selection of initial solutions for intensification application.