Programação da produção utilizando heurísticas no ambiente de máquinas paralelas não relacionadas

Abstract

The problem of scheduling production in an unrelated parallel machine environment is recurrent in manufacturing companies with machines that can produce the same products at different and unrelated times. Optimization criteria are used to select the best programming, however, the mathematical programming method, which results in the best solution to the problem, has a high computational execution time the more tasks and machines are involved in the problem. Efficient methods for scheduling tasks were developed in this work, starting with the analysis and adaptation of heuristics, aiming at minimizing the sum of the makespan and the total delay, with priority for the makespan, and the comparison was made with the method of mathematical programming. The bibliographic research, an initial part of the work, contributed to the mathematical modeling of the mixed integer programming method that was implemented in the Lingo software. Two constructive heuristics and three improvement heuristics were developed, resulting in twelve different methods by combining the heuristics. The heuristic methods could be compared to the mathematical model for small instances. For larger instances the mathematical model was not able to find a solution within the stipulated time limit due to the increase in the complexity of the problem. Among the heuristic methods, the resulting combination of Constructive Heuristic 1, Improvement Heuristic 1 and Improvement Heuristic 3 obtained 67% of possible successes, thus being the most satisfactory method.