Um estudo sobre a aplicação de heurísticas no problema de job shop

Abstract

The Job Shop Problem is classified as an NP-hard problem, there is no algorithm that finds the ideal solution in polynomial time. The resolution of the task sequencing problem is fundamental in strategic management that directly affects all the guidelines of a company, in addition to fitting into the classic problems within production planning and control. The present work study where it is necessary to develop and implement a mathematical model capable of determining the optimal sequencing of production, which will return the optimal solution referring to the best combination and proportion of production and supply of certain products or services, but it takes time high to return such a solution. The study is based on the formulation of the mathematical model, the use of optimization techniques for solving the model and analysis of the results obtained, with the aim of seeking to maximize profits from the logistics operation, that is, to seek to fill certain gaps in the market. The present work compares a new constructive heuristic and a refinement heuristic that aims to improve the results obtained by the ILS and VNS meta-heuristics for Job Shop problems implemented in the C++ programming language. This research began with the resolution of the problem through linear programming with the objective of this result serving as a parameter for the quality of the response obtained with the meta-heuristics ILS and VNS. Subsequently, the ILS and VNS meta-heuristics were implemented using Baker and Trietsch's constructive heuristic and these results were analyzed together with the responses obtained by linear programming. It was possible to conclude that jobs with greater total time had execution priority, resulting in the proposition of a different way of setting up the constructive heuristic and for certain instances of larger dimensions of the problem to use a refinement heuristic. This method aims to achieve an optimized response in a shorter execution time, in order to assist in decision making in sequencing work on machines.