• 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
 
 
Mémoire de Maîtrise
DOI
10.11606/D.3.2019.tde-04022019-092016
Document
Auteur
Nom complet
Augusto Otto Molke
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2018
Directeur
Jury
Santoro, Miguel Cezar (Président)
Mesquita, Marco Aurélio de
Morabito Neto, Reinaldo
Titre en portugais
Minimização do atraso total ponderado na programação de máquinas diferentes em paralelo com elegibilidade.
Mots-clés en portugais
Atraso ponderado
Geração de colunas
Máquinas em paralelo
Pesquisa operacional
Programação
Scheduling
Resumé en portugais
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%.
Titre en anglais
Scheduling unrelated parallel machines with eligibility for minimizing total weighted tardiness.
Mots-clés en anglais
Column generation
Constructive heuristic.
Scheduling
Tardiness
Unrelated parallel machines
Resumé en anglais
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%.
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
Date de Publication
2019-02-20
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
CeTI-SC/STI
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2020. Tous droits réservés.