???item.export.label??? ???item.export.type.endnote??? ???item.export.type.bibtex???

Please use this identifier to cite or link to this item: http://tede.ufam.edu.br/handle/tede/6147
???metadata.dc.type???: Tese
Title: Estratégias algorítmicas exatas e híbridas para problemas de escalonamento em máquinas paralelas com penalidades de antecipação e atraso
???metadata.dc.creator???: Amorim, Rainer Xavier de 
???metadata.dc.contributor.advisor1???: Rodrigues, Rosiane de Freitas
???metadata.dc.contributor.referee2???: Barreto, Raimundo da Silva
???metadata.dc.contributor.referee3???: Santos, Eulanda Miranda dos
???metadata.dc.contributor.referee4???: Barboza, Eduardo Uchoa
???metadata.dc.contributor.referee5???: Pio, José Luiz de Souza
???metadata.dc.description.resumo???: Esta pesquisa investiga problemas de escalonamento com penalidades de antecipação e atraso em ambiente mono e multiprocessado envolvendo máquinas paralelas. Este problema é também conhecido na literatura como escalonamento Just-in-Time, sistema amplamente utilizado em indústrias para reduzir estoques e os custos decorrentes, a fim de que o produto seja produzido de acordo com a demanda. Neste trabalho é proposta uma estratégia algorítmica híbrida exato-heurística, baseada em uma formulação de programação inteira arc-time e um algoritmo evolucionário fortemente baseado em busca local, para melhor resolver problemas clássicos de escalonamento em máquinas paralelas envolvendo penalidades de antecipação e atraso, com tarefas independentes e tempos de processamento arbitrários. Os arcos são selecionados das soluções ótimas locais obtidas pelo algoritmo genético fortemente baseado em busca local (GLS) com movimentos generalizados de troca de pares, que são fornecidos como entrada para a formulação arc-time, para gerar soluções melhores do que as obtidas por ambos os métodos quando utilizados isoladamente. Os experimentos computacionais apresentam resultados competitivos em relação à literatura. O método proposto também resolve instâncias de tamanho maior de até 500 tarefas em máquinas paralelas idênticas.
Abstract: This research investigates scheduling problems with earliness and tardiness penalties on single and parallel machine environments. This problem is also known in the literature as Just-in-Time scheduling, system widely used in industries to reduce inventories and costs, in order to lead product to be produced according to demand. In this work we present a hybrid exact-heuristic algorithmic strategy, based on an arc-time indexed integer programming formulation and a generalized evolutionary heuristic based on a strong local search, to better solve classical parallel machine scheduling problems involving weighted earliness-tardiness penalties, with independent jobs and arbitrary processing times. Selected arcs from local optima solutions generated by a genetic algorithm based on a strong local search (GLS) with generalized pairwise interchanges are given as input to the arc-time formulation, to produce better solutions than those obtained by both methods when used isolated. Computational experiments present competitive results according to the literature. Our proposed method also solves large instances up to 500 jobs in identical parallel machines.
Keywords: Algoritmos
Escalonamento Just-in-Time
Máquinas paralelas idênticas
???metadata.dc.subject.cnpq???: CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO
Language: por
???metadata.dc.publisher.country???: Brasil
Publisher: Universidade Federal do Amazonas
???metadata.dc.publisher.initials???: UFAM
???metadata.dc.publisher.department???: Instituto de Computação
???metadata.dc.publisher.program???: Programa de Pós-graduação em Informática
Citation: AMORIM, Rainer Xavier de. Estratégias algorítmicas exatas e híbridas para problemas de escalonamento em máquinas paralelas com penalidades de antecipação e atraso. 2017. 113 f. Tese (Doutorado em Informática) - Universidade Federal do Amazonas, Manaus, 2017.
???metadata.dc.rights???: Acesso Aberto
???metadata.dc.rights.uri???: http://creativecommons.org/licenses/by-nc-nd/4.0/
URI: http://tede.ufam.edu.br/handle/tede/6147
Issue Date: 6-Oct-2017
Appears in Collections:Doutorado em Informática

Files in This Item:
File Description SizeFormat 
Tese_Rainer X. Amorim.pdf6.12 MBAdobe PDFThumbnail

Download/Open Preview


This item is licensed under a Creative Commons License Creative Commons