Métodos de busca local em problemas de escalonamento da produção em ambientes job shop

Abstract

Solving the problem of production scheduling is an important task in production planning and control. This problem consists, in short, to define a sequence of realization of the production operations for each of the resources (machines) available. This is a complex problem, especially in job shop-type production environments in which each job is defined as a single set of tasks that must be processed in a predefined order and different from that of other jobs. These are the Job Shop Scheduling Problems (JSSP). For smaller problems exact methods have been considered the most indicated because they find the optimal solution in acceptable computational times. For larger problems, which grow in a non-linear way in relation to the number of jobs and machines, heuristic solutions have been more used as a function of computational cost, although they do not guarantee to find the optimal solution. The heuristic and metaheuristic methods have gained prominence in the literature, as is the case of the Genetic Algorithm (GA), which is based on the theory of evolution of the species. However, the genetic algorithm without the application of a local search technique, which is a search in the vicinity of a solution to refine it, does not present satisfactory results for the problem specifically addressed. The objective of this work is to compare different representations in a local search method, together with GA, for the scheduling problem in the job shop environment. For the tests of this work, local search method was evaluated in instances known in the literature. Search methods with defined neighborhoods from direct and indirect representations of the solution in the Genetic Algorithm were compared. The results show that methods with indirect approach defined from indirect representations of the solution are more effective for the problems tested, compared to the direct approach, especially in relation to the computational cost.