Heurísticas para o problema de minimização da soma de adiantamentos e atrasos no ambiente de máquinas paralelas não relacionadas

Abstract

Production scheduling is widely used by industry planning and production control because it allows defining the best ordering of tasks to optimize some objective. This work brings the development of resolution methods for the problem of minimizing the sum of advances and delays in the unrelated parallel machines environment. These methods must be able to bypass the computational effort encountered in solving the problem by exact methods considering that delays and advances have the same proportion of importance. For the accomplishment of the work a bibliographical research was made and, from it, a mathematical model was implemented using software of mathematical programming - Lingo. In addition, constructive heuristic methods were used to provide an initial solution to a proposed improvement heuristic. Such heuristic methods, implemented using the programming language C, aim to obtain satisfactory results in the resolution of the problem, consuming low processing time. In some cases it was possible to compare the solutions obtained by the heuristic methods with the optimal solution, while for others it was not possible to obtain any solution with the mathematical model because of the complexity of the problem. Among the constructive heuristics, it can be considered that Constructive Heuristic 2 obtained better results for the objective function, while the other two obtained satisfactory results. As for the heuristic of improvement, it can be said that it reached its goal, achieving improvements of up to 63%.