Modelos e algoritmos para o flowshop híbrido com tempos de preparaçãodependentes da sequência e da máquina

Abstract

This work focuses the Hybrid Flow Shop scheduling problem with sequence-dependent setup time, as well as machine, considering initially three performance criteria: Minimize makespan, time processing and the number of overdue tasks. For contextualization of the problem studied, are shown techniques used to solve similar problems.Initially, models of mixed integer linear programming (MILP) are adapted to represent the problem addressed. These models were implemented using a modeling tool and solved by a commercial software, being test instances generated randomly. The computational experiments provide the optimal solution in a time limit. However, the solutions are going away from the optimum for large instances. In addition, are proposedalgorithms based on "Relax and Fix"heuristic which are worked on outperformed MILP model, is developed a heuristic that determines some features of the problem and finally,is developed a ILS metaheuristic, this time considering only one performance criterion: Minimize makespan. The results of these algorithms are reported andcompared evaluating the performance criterion behavior.