Tese

Estratégias algorítmicas exatas e híbridas para problemas de escalonamento em máquinas paralelas com penalidades de antecipação e atraso

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 esto...

ver descrição completa

Autor principal: Amorim, Rainer Xavier de
Outros Autores: http://lattes.cnpq.br/6851610498599368
Grau: Tese
Idioma: por
Publicado em: Universidade Federal do Amazonas 2018
Assuntos:
Algoritmos
Escalonamento Just-in-Time
Máquinas paralelas idênticas
CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO
Acesso em linha: http://tede.ufam.edu.br/handle/tede/6147
id oai:https:--tede.ufam.edu.br-handle-:tede-6147
recordtype dspace
spelling oai:https:--tede.ufam.edu.br-handle-:tede-61472018-02-08T05:03:47Z Estratégias algorítmicas exatas e híbridas para problemas de escalonamento em máquinas paralelas com penalidades de antecipação e atraso Amorim, Rainer Xavier de Rodrigues, Rosiane de Freitas http://lattes.cnpq.br/6851610498599368 http://lattes.cnpq.br/8358219976594707 Barreto, Raimundo da Silva Santos, Eulanda Miranda dos Algoritmos Escalonamento Just-in-Time Máquinas paralelas idênticas CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO 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. 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. FAPEAM - Fundação de Amparo à Pesquisa do Estado do Amazonas 2018-02-07T19:00:25Z 2017-10-06 Tese 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. http://tede.ufam.edu.br/handle/tede/6147 por Acesso Aberto http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Universidade Federal do Amazonas Instituto de Computação Brasil UFAM Programa de Pós-graduação em Informática
institution TEDE - Universidade Federal do Amazonas
collection TEDE-UFAM
language por
topic Algoritmos
Escalonamento Just-in-Time
Máquinas paralelas idênticas
CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO
spellingShingle Algoritmos
Escalonamento Just-in-Time
Máquinas paralelas idênticas
CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃ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
topic_facet Algoritmos
Escalonamento Just-in-Time
Máquinas paralelas idênticas
CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO
description 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.
author_additional Rodrigues, Rosiane de Freitas
author_additionalStr Rodrigues, Rosiane de Freitas
format Tese
author Amorim, Rainer Xavier de
author2 http://lattes.cnpq.br/6851610498599368
author2Str http://lattes.cnpq.br/6851610498599368
title Estratégias algorítmicas exatas e híbridas para problemas de escalonamento em máquinas paralelas com penalidades de antecipação e atraso
title_short Estratégias algorítmicas exatas e híbridas para problemas de escalonamento em máquinas paralelas com penalidades de antecipação e atraso
title_full Estratégias algorítmicas exatas e híbridas para problemas de escalonamento em máquinas paralelas com penalidades de antecipação e atraso
title_fullStr Estratégias algorítmicas exatas e híbridas para problemas de escalonamento em máquinas paralelas com penalidades de antecipação e atraso
title_full_unstemmed Estratégias algorítmicas exatas e híbridas para problemas de escalonamento em máquinas paralelas com penalidades de antecipação e atraso
title_sort estratégias algorítmicas exatas e híbridas para problemas de escalonamento em máquinas paralelas com penalidades de antecipação e atraso
publisher Universidade Federal do Amazonas
publishDate 2018
url http://tede.ufam.edu.br/handle/tede/6147
_version_ 1831969581538738176
score 11.753735

Registros relacionados