Exportar este item: EndNote BibTex

Use este identificador para citar ou linkar para este item: https://tede.ufam.edu.br/handle/tede/6147
Tipo do documento: Tese
Título: Estratégias algorítmicas exatas e híbridas para problemas de escalonamento em máquinas paralelas com penalidades de antecipação e atraso
Autor: Amorim, Rainer Xavier de 
Primeiro orientador: Rodrigues, Rosiane de Freitas
Segundo membro da banca: Barreto, Raimundo da Silva
Terceiro membro da banca: Santos, Eulanda Miranda dos
Quarto membro da banca: Barboza, Eduardo Uchoa
Quinto membro da banca: Pio, José Luiz de Souza
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.
Palavras-chave: Algoritmos
Escalonamento Just-in-Time
Máquinas paralelas idênticas
Área(s) do CNPq: CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO
Idioma: por
País: Brasil
Instituição: Universidade Federal do Amazonas
Sigla da instituição: UFAM
Departamento: Instituto de Computação
Programa: Programa de Pós-graduação em Informática
Citação: 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.
Tipo de acesso: Acesso Aberto
Endereço da licença: http://creativecommons.org/licenses/by-nc-nd/4.0/
URI: http://tede.ufam.edu.br/handle/tede/6147
Data de defesa: 6-Out-2017
Aparece nas coleções:Doutorado em Informática

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
Tese_Rainer X. Amorim.pdf6,12 MBAdobe PDFThumbnail

Baixar/Abrir Pré-Visualizar


Este item está licenciada sob uma Licença Creative Commons Creative Commons