• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Dissertação de Mestrado
DOI
10.11606/D.3.2019.tde-04022019-092016
Documento
Autor
Nome completo
Augusto Otto Molke
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2018
Orientador
Banca examinadora
Santoro, Miguel Cezar (Presidente)
Mesquita, Marco Aurélio de
Morabito Neto, Reinaldo
Título em português
Minimização do atraso total ponderado na programação de máquinas diferentes em paralelo com elegibilidade.
Palavras-chave em português
Atraso ponderado
Geração de colunas
Máquinas em paralelo
Pesquisa operacional
Programação
Scheduling
Resumo em português
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%.
Título em inglês
Scheduling unrelated parallel machines with eligibility for minimizing total weighted tardiness.
Palavras-chave em inglês
Column generation
Constructive heuristic.
Scheduling
Tardiness
Unrelated parallel machines
Resumo em inglês
This paper deals with the problem of scheduling activities in unrelated parallel parallel, considering machine eligibility, and machine and activity release time in order to minimize total weighted tardiness.Such a problem is described in the literature as NPhard. It has been proposed an optimizing method that involves mathematical modeling and a column generation algorithm, in addition, it is proposed a heuristic to treat problems with larger instances. The column generation algorithm was based on the method proposed by Akker, Hurkens e Savelsbergh (2000), which has been adapted to the problem of multiple diferent machines. Thus, the method was applied in instances of the literature and in instances generated for this paper up to 25 jobs and 4 machines. The results were analyzed and it was noted that the mixed integer programming model is eficient to find good quality upper bounds. On the other hand, the column generation algorithm is eficient to find lower bounds for the problem. Therefore, the proposed method uses the MILP model and the column generation algorithm to complement each other. Thus, optimal solutions were found for 84 % of the generated instances, with the mean GAP for the remaining instances being 2.1 %. The proposed heuristic is based on the idea of probabilistic constructive heuristics, which was presented by Arcus (1965). It was run on the mass of data generated, resulting in an average GAP of 10,6%.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Data de Publicação
2019-02-20
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2020. Todos os direitos reservados.