Return to search

O Problema de OrdenaÃÃo de Rodadas e Problemas de OtimizaÃÃo Associados

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / Esta tese à composta de trÃs partes bem-delineadas. Na primeira parte, nÃs introduzimos o "problema de ordenaÃÃo de rodadas" (POR), que modela a minimizaÃÃo do uso de memÃria ("buffer") para o armazenamento temporÃrio de pacotes a serem repassados em comunicaÃÃes TDMA de redes de rÃdio em malha. NÃs apresentamos uma fundamentaÃÃo completa para a definiÃÃo do POR, e mostramos que o problema à NP-difÃcil para dois modelos teÃricos de interferÃncia de rÃdio conhecidos na literatura. Uma formulaÃÃo de programaÃÃo inteira mista à tambÃm apresentada para uma generalizaÃÃo puramente combinatÃria e independente de aplicaÃÃo do POR, o problema SMSP. Na segunda parte do trabalho, nÃs abordamos problemas de consulta sobre inserÃÃes em sequÃncias de nÃmeros. O nosso principal resultado nesta parte da tese à mostrar como, apÃs um passo de prÃ-processamento que executa em tempo linear sobre uma sequÃncia "A" de nÃmeros reais quaisquer, à possÃvel computar em tempo constante a maior soma de uma subsequÃncia contÃgua (circular ou nÃo) da sequÃncia que resulta da inserÃÃo de dado um nÃmero real "x" numa dada posiÃÃo "p" de "A". Na terceira parte da tese, nÃs utilizamos os algoritmos de consulta da segunda parte para obter uma implementaÃÃo eficiente da meta-heurÃstica GRASP aplicada ao problema SMSP. Uma anÃlise experimental dessa implementaÃÃo à descrita, onde os valores das soluÃÃes retornadas pela meta-heurÃstica sÃo comparados com os das soluÃÃes obtidas pela formulaÃÃo inteira mista, no caso de instÃncias pequenas, e com o limite inferior disponÃvel, no caso de instÃncias maiores.

Identiferoai:union.ndltd.org:IBICT/oai:www.teses.ufc.br:7588
Date01 November 2013
CreatorsPablo Mayckon Silva Farias
ContributorsRicardo Cordeiro CorrÃa, Manoel Bezerra Campelo Neto, CrÃston Pereira de Souza, Thiago Ferreira de Noronha, FÃbio Protti
PublisherUniversidade Federal do CearÃ, Programa de PÃs-GraduaÃÃo em CiÃncia da ComputaÃÃo, UFC, BR
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguagePortuguese
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis
Formatapplication/pdf
Sourcereponame:Biblioteca Digital de Teses e Dissertações da UFC, instname:Universidade Federal do Ceará, instacron:UFC
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0017 seconds