Algoritmos para o problema de sequenciamento com máquinas paralelas e tempos de preparação dependentes da sequência

Abstract

Scheduling problems can be found in the most diverse areas of science. If we consider industrial applications, there are a big number of problems that can be modeled as a scheduling problem, especially those related to production planning.The production planning of a company is usually done considering two or three planning levels. Pursuing different objectives, but with a strong correlation between them. In the classic school, in a first stage the company works with families of products where the main focus is the optimization of resources and the capacity of the plants. The scheduling problems are found in the level of the immediate production planning.The aim of this dissertation is to present, discuss and solved two scheduling problems, both cases are based on a real problem from a Brazilian company. The first problem consists in a parallel machine case in which realistic constraints, as sequence dependent setups and due dates, are considered. To solve this problem, three mathematical models and a branch and bound algorithm are proposed to find the optimal solution. Two heuristics, based on the metaheuristics GRASP and VNS, are also implemented and tested. An algorithm based on a Lagrangian relaxation is also proposed, the main objective of this algorithm is to improve the problem's lower bounds and consequently the performance of the branch and bound algorithm. The second problem is the well known permutation flow shop problem. In this case, two hybrid algorithms are proposed and tested.