Algoritmos heurísticos para solução de problemas de sequenciamento em máquinas paralelas não-relacionadas em multi-fábricas

Abstract

The sequencing problem of n independent tasks on m unrelated parallel machines aims to minimize the total completion time (makespan) of the tasks on the machines. Based on the four-phase heuristic, and initially structured for identical parallel machines and uniform parallel machines, it has the following phases: Phase 1-Initial Allocation, Phase 2-Balancing Phase, Phase 3-Double Exchanges and Phase 4-Triple Exchanges, created for the problem in question, of unrelated parallel machines in multi-plants. For the development of the 4 Phases, three heuristics based on Dispatch Rules were proposed for the initial allocation They were named as SPTtest, LPTtest and FCFStest and then compared with two other classic heuristics in the literature, the LPT (Longest Processing Time) and the Genetic Algorithm (GA). With the results obtained, it was verified that the algorithms proposed obtained better performance in the computational experiments, discussed based on the percentage relative deviation (PRD) in relation to the initial solution and the lower bounds.Therefore, for environments with unrelated parallel machines for multi-plants, the method applied proved to be advantageous for production scheduling in the manufacturing and service sector.