Desenvolvimento de um algoritmo de busca em vizinhança variável para o problema de sequenciamento de produção em job shops flexíveis

Abstract

The growing competitiveness in the organizational environment has stimulated the increase in the flexibility of process and machines by manufacturing industries. In order to comply with this, industrial environment characterized as Flexible Job Shop, wich have production orders with different production routings and machines capable of process different operations, has become more common. The flexible job shop scheduling is an important decision making process for factories, which consists of assign the operations to machines and define a sequence in which they will be processed on each machine. This decision making process, called Flexible Job Shop Problem (FJSP), is a problem classified as NP-hard in the scientific literature, with high resolution complexity in short computational times. To solve this problem, this paper proposes an algorithm based on a metaheuristc called Variable Neighborhood Search. Therefore, four local search procedures with systematic neighborhood changes were developed in four different configurations in order to solve the FJSP minimizing the makespan. For algorithm tests, 198 benchmark problems were used, besides the application in an illustrative case, in order to analyze the feasibility of application in real companies. The results obtained demonstrate the ability of the algorithm to reach competitive solutions when compared to the best known solutions in the literature. Furthermore, the illustrative case exemplifies how the proposed method could be appropriate for a real situation with better results than random solutions.