Sequenciamento de máquinas paralelas não relacionadas com tempo de preparação dependentes da sequência e da máquina

Abstract

Parallel machine scheduling researches are mostly concentrated on heuristics, because of their theoretical and challenging feature. Only few papers present exact approaches, and most of them are restricted to environment about identical parallel machine scheduling. This work studies a scheduling problem with unrelated parallel machines, sequence and machine dependent setup times. The objective function is minimize the total weighted completion times. This problem is not very explored in literature. There is a limited number of researches that study the problem from a heuristic point of view. Works that analyse the problem utilizing exact methods were not found. In this context, six mixed integer programing (MIP) scheduling formulations of the literature were adapted to the problem. This paper presents a new mathematical model. Due to the characteristics of the formulation developed, an algorithm variants based on the Benders decomposition method are presented to solve the problem. A logic-based Benders decomposition approach of the literature was adapted and compared with the algorithm previously mentioned. Computational results show that the new formulation have a better behavior than five of the six formulations found in the literature. About the two algorithms implemented, the first has a more attractive and behavior and both point out for the need of the more research involving exact methods.