Tese

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

• Authors:
  • Molke, Augusto Otto
  • Santoro, Miguel (Orientador)
• Autor USP: MOLKE, AUGUSTO OTTO - EP
• Unidade: EP
• Sigla do Departamento: PTR
• Subjects: SCHEDULING; PESQUISA OPERACIONAL
• Agências de fomento:
  • Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
• Language: Português
• Abstract: 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%.
• Imprenta:
  • Publisher place: São Paulo
  • Date published: 2018
• Data da defesa: 29.10.2018


---

How to cite

A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

• ABNT

  MOLKE, Augusto Otto. Minimização do atraso total ponderado na programação de máquinas diferentes em paralelo com elegibilidade. 2018. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2018. Disponível em: http://www.teses.usp.br/teses/disponiveis/3/3148/tde-04022019-092016/. Acesso em: 21 maio 2024.

• APA

  Molke, A. O. (2018). Minimização do atraso total ponderado na programação de máquinas diferentes em paralelo com elegibilidade (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/3/3148/tde-04022019-092016/

• NLM

  Molke AO. Minimização do atraso total ponderado na programação de máquinas diferentes em paralelo com elegibilidade [Internet]. 2018 ;[citado 2024 maio 21 ] Available from: http://www.teses.usp.br/teses/disponiveis/3/3148/tde-04022019-092016/

• Vancouver

  Molke AO. Minimização do atraso total ponderado na programação de máquinas diferentes em paralelo com elegibilidade [Internet]. 2018 ;[citado 2024 maio 21 ] Available from: http://www.teses.usp.br/teses/disponiveis/3/3148/tde-04022019-092016/

Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI: