Metaheurísticas para a minimização do atraso total no problema de sequenciamento em máquinas paralelas com divisão de tarefas

Imagem de Miniatura

Data

2013-02-28

Título da Revista

ISSN da Revista

Título de Volume

Editor

Universidade Federal de Viçosa

Resumo

Este trabalho aborda o problema de escalonar n tarefas independentes em m máquinas paralelas idênticas com o objetivo de minimizar o atraso total das tarefas. Assume-se que uma tarefa possa ser dividida em sub-tarefas e estas possam ser processadas independentemente nas máquinas paralelas idênticas. Este problema é considerado NP-difícil, o que significa que, encontrar a solução ótima para este problema, levará um tempo computacional não aceitável. Por tal razão, métodos alternativos, como heurísticas, são utilizados para que boas soluções sejam obtidas em tempo razoável. Algumas heurísticas baseadas nas metaheurísticas GRASP (Greed Randomized Adaptive Search procedure) e no Algoritmo Genético são propostas. Além disso, três regras de dominâncias são utilizadas para melhorar as soluções. São comparados os resultados destes algoritmos com os resultados de outros dois algoritmos propostos na literatura.
This work focuses on the problem of scheduling n independently jobs on m identical parallel machines with the objective of minimizing the total tardiness. It is assumed that a job can be split in sub-jobs and they can be processed independently in the identical machines. This problem is considered NP-Hard, what means that, finding an optimal solution will take an unacceptable computational time. For such reason, alternative methods, as heuristics, are used for good solutions to be gotten in reasonable time. Some heuristics based on metaheuristics GRASP (Greed Randomized Adaptive Search Procedure) and on Genetic Algorithm are proposed. Futhermore, three dominance rules are used in order to improve the solutions. The results of these algorithms are compared with the results of two others proposed in the literature.

Descrição

Palavras-chave

Sequenciamento em máquinas paralelas, Atraso total, GRASP, Algoritmo genético, Simulated Annealing, Busca tabu, Busca local, Path Relinking, Sequencing on parallel machines, Total tardiness, GRASP, Genetic Algorithm, Simulated Annealing, Tabu Search, Local Search, Path Relinking

Citação

OLIVEIRA JÚNIOR, Paulo Lúcio de. Metaheuristics to minimize total tardiness on scheduling of sub-jobs in parallel machines with splitting jobs. 2013. 89 f. Dissertação (Mestrado em Metodologias e técnicas da Computação; Sistemas de Computação) - Universidade Federal de Viçosa, Viçosa, 2013.

Avaliação

Revisão

Suplementado Por

Referenciado Por