Um estudo sobre formulações matemáticas e estratégias algorítmicas para problemas de escalonamento em máquinas paralelas com penalidades de antecipação e atraso

• Ano de defesa: 2013
• Autor(a) principal: Amorim, Rainer Xavier de
• Outros Autores: http://lattes.cnpq.br/6851610498599368
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal do Amazonas; Instituto de Computação; BR; UFAM; Programa de Pós-graduação em Informática
• Palavras-chave em Português: Algoritmos; Otimização combinatória; Penalidades de antecipação e atraso; Programação linear inteira; Teoria de escalonamento; Algorithms; Combinatorial optimization; Earliness and tardiness penalties; Integer linear programming; Scheduling theory; CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO
• Link de acesso: http://tede.ufam.edu.br/handle/tede/2898

Esta dissertação apresenta um estudo sobre problemas de escalonamento com penalidades de antecipação e atraso em máquinas paralelas, considerando tarefas independentes, ponderadas e de tempos de execução arbitrários. Uma análise sobre as principais formulações matemáticas em programação inteira é dada, bem como apresentados os principais resultados da literatura. Uma formulação matemática de programação inteira baseada no modelo de fluxo em redes também foi proposta para o problema, que pode ser aplicada em ambientes mono e multiprocessado sem tempo ocioso. Métodos de enumeração implícita foram estudados e aplicados aos problemas em questão através do resolvedor de programação linear inteira CPLEX e da biblioteca UFFLP, principalmente, estratégias algorítmicas aproximadas de otimização global baseadas em heurísticas de busca local e técnica de reconexão de caminhos foram desenvolvidas. Os experimentos computacionais mostram que as estratégias propostas são competitivas em relação aos resultados existentes na literatura para ambientes de escalonamento monoprocessados, envolvendo instâncias baseadas no benchmark da OR-Library para 40, 50, 100, 150, 200 e 300 tarefas, onde todos os ótimos foram encontrados, e, principalmente, sendo a melhor estratégia apresentada para ambientes multiprocessados, envolvendo 2, 4 e 10 máquinas paralelas idênticas.