Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2017-02-02T15:07:51Z
No. of bitstreams: 1
texto completo.pdf: 2920159 bytes, checksum: 01255d0b5bb511ed365f7e524b38366c (MD5) / Made available in DSpace on 2017-02-02T15:07:51Z (GMT). No. of bitstreams: 1
texto completo.pdf: 2920159 bytes, checksum: 01255d0b5bb511ed365f7e524b38366c (MD5)
Previous issue date: 2016-07-06 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho aborda o problema de sequenciamento de tarefas em máquinas pa- ralelas não-relacionadas em que as tarefas causam desgastes nas máquinas. Este fator diminui o desempenho das máquinas levando ao aumento do tempo de pro- cessamento das tarefas ao longo do tempo. O objetivo do problema é encontrar as sequências de processamento de tarefas em cada máquina de tal maneira que os desgastes das máquinas sejam reduzidos e, consequentemente, minimizar o tempo máximo de conclusão de todas as tarefas, conhecido como makespan. Neste traba- lho, inicialmente, é proposto um novo modelo de Programação Inteira Mista baseado na geração de padrões (conjuntos de tarefas) para cada máquina, com objetivo de obter soluções ótimas para o problema. Dado que o problema é NP-Difícil para mais de uma máquina, dois algoritmos heurísticos são propostos para obter solu- ções de alta qualidade em baixo tempo computacional. Os algoritmos são baseados nas meta-heurísticas Iterated Local Search (ILS) e Iterated Greedy (IG), respecti- vamente. Também, as heurísticas ILS e IG são combinadas com uma variante do método Variable Neighborhood Descent (VND), que utiliza uma ordenação aleatória das vizinhanças (RVND) na fase da busca local, obtendo dois algoritmos híbridos denominados ILS-RVND e IG-RVND. O benchmark usado nos experimentos compu- tacionais usa 900 instâncias de médio porte disponíveis na literatura, e 900 instâncias de grande porte geradas neste trabalho. Os algoritmos são comparados entre si e também com um algoritmo Simulated Annealing (SA) proposto na literatura para o mesmo problema. Os testes realizados mostram que os desempenhos dos algoritmos propostos são significativamente superiores em relação ao algoritmo SA. / This work addresses an unrelated parallel machine scheduling problem in which the jobs cause deterioration of the machines. This factor decreases the performance of the machines, causing an increasing of the jobs over time. The problem is to find the processing sequence of jobs on each machine in order to reduce the deterioration of the machines and consequently minimize the maximum completion time of jobs (makespan). In this work, initially, we propose a new Mixed-Integer Programming model based on patterns (sets of jobs) generation to find optimal solution of the pro- blem. Since the problem is NP-hard when the number of machines is greater than one, two heuristic algorithms are proposed to obtain near-optimal solutions in reaso- nable computational time. The algorithms are based on the meta-heuristics Iterated Local Search (ILS) and Iterated Greedy (IG), respectively. Also, the algorithms ILS and IG are coupled with a variant of the Variable Neighborhood Descent (VND) method that uses a random ordering of neighborhoods (RVND) in local search phase, obtaining two hybrid algorithms called ILS-RVND and IG-RVND. The benchmark used in computational experiments uses 900 medium-size instances available in the literature, and 900 large-size instances generated in this work. The algorithms are compared against each other and are also compared with a Simulated Annealing (SA) algorithm proposed in the literature for the problem under study. The tests show that the proposed algorithms have superior performances compared to the SA algorithm.
| Identifer | oai:union.ndltd.org:IBICT/oai:localhost:123456789/9402 |
| Date | 06 July 2016 |
| Creators | Santos, Vívian Ludmila Aguiar |
| Contributors | Santos, André Gustavo dos, Arroyo, José Elias Claudio |
| Publisher | Universidade Federal de Viçosa |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UFV, instname:Universidade Federal de Viçosa, instacron:UFV |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0017 seconds