skip to main content
Idioma:

Minimização do atraso total ponderado na programação de máquinas diferentes em paralelo com elegibilidade.

Molke, Augusto Otto

Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Escola Politécnica 2018-10-29

Acesso online. A biblioteca também possui exemplares impressos.

  • Título:
    Minimização do atraso total ponderado na programação de máquinas diferentes em paralelo com elegibilidade.
  • Autor: Molke, Augusto Otto
  • Orientador: Santoro, Miguel Cezar
  • Assuntos: Atraso Ponderado; Scheduling; Programação; Pesquisa Operacional; Máquinas Em Paralelo; Geração De Colunas; Constructive Heuristic; Scheduling; Column Generation; Tardiness; Unrelated Parallel Machines
  • Notas: Dissertação (Mestrado)
  • Notas Locais: Programa Engenharia de Sistemas Logísticos
  • Descrição: Este trabalho trata do problema de sequenciamento e programação de atividades em máquinas diferentes em paralelo, considerando elegibilidade de máquina, e tempo de liberação das máquinas e das atividades com o objetivo de minimizar o custo de atraso total. Tal problema é descrito pela literatura como NP-hard. Foi proposto um método otimizante que envolve modelagem matemática, um algoritmo de geração de colunas e, além disso, uma heurística para tratar problemas com instancias maiores. O algoritmo de geração de colunas é baseado no método proposto por Akker, Hurkens e Savelsbergh (2000), que foi adaptado para o problema de múltiplas máquinas diferentes. Assim, o método foi aplicado em instâncias da literatura e em instâncias geradas para este trabalho de até 25 atividades e 4 máquinas. Os resultados foram analisados e observou-se que o modelo de programação inteira mista e eficiente para encontrar limitantes superiores de boa qualidade. Por outro lado, o algoritmo de geração de colunas é eficiente para encontrar limitantes inferiores para o problema. Desta forma, o método proposto utiliza o modelo MILP e o algoritmo de geração de colunas de maneira a se complementar. Assim, soluções ótimas foram encontradas para 84% das instancias geradas, sendo que o GAP médio para as instancias restantes foi de 2,1%. A heurística proposta e baseada na ideia de heurística construtiva probabilística, que foi apresentada por Arcus (1965). Ela foi executada na massa de dados gerada, resultando em um GAP médio de 10,6%.
  • DOI: 10.11606/D.3.2019.tde-04022019-092016
  • Editor: Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Escola Politécnica
  • Data de publicação: 2018-10-29
  • Formato: Adobe PDF
  • Idioma: Português
Links
Voltar para lista de resultados

  • Realização: USP

Buscando em bases de dados remotas. Favor aguardar.