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.

FARIAS, Pablo Mayckon Silva. O problema de ordenação de rodadas e problemas de otimização associados. 2013. 127 f. Tese (Doutorado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2013. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-20T12:44:36Z No. of bitstreams: 1 2013_tese_pmsfarias.pdf: 1600516 bytes, checksum: afaccc349ce6f2d065494cd2601913c0 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-25T12:05:15Z (GMT) No. of bitstreams: 1 2013_tese_pmsfarias.pdf: 1600516 bytes, checksum: afaccc349ce6f2d065494cd2601913c0 (MD5) / Made available in DSpace on 2016-07-25T12:05:15Z (GMT). No. of bitstreams: 1 2013_tese_pmsfarias.pdf: 1600516 bytes, checksum: afaccc349ce6f2d065494cd2601913c0 (MD5) Previous issue date: 2013 / This thesis is composed of three well-delineated parts. In the first part, we introduce the round sorting problem (RSP), which models the minimization of the usage of buffer for the temporary storage of packets to be forwarded in TDMA communications of wireless mesh networks. We present a complete foundation for the definition of the RSP, and show that the problem is NP-hard for two theoretical models of radio interference known in the literature. A mixed integer programming formulation is also presented for a purely combinatorial and applicationindependent generalization of the RSP, the SMSP problem. In the second part of the work, we deal with problems about queries on insertions into sequences of numbers. Our main result in this part of the thesis is to show how, after a preprocessing step which runs in linear time on a sequence A of arbitrary real numbers, it is possible to compute in constant time the greatest sum of a (circular or not) contiguous subsequence of the sequence which results from the insertion of a given real number x into a given position p of A. In the third part of the thesis, we use the query algorithms from the second part to obtain an efficient implementation of the GRASP metaheuristic applied to the SMSP problem. An experimental analysis of this implementation is described, in which the values of the solutions returned by the metaheuristic are compared with those of the solutions obtained through the mixed integer formulation, in the case of small instances, and with the available lower bound, in the case of larger instances. / 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.