Esta tese de Doutorado tem como objetivo apresentar uma arquitetura para metaescalonamento verde com provisão de qualidade de serviço em uma nuvem privada denominada GreenMACC. Essa nova arquitetura oferece a automatização na escolha de políticas em quatro estágios de escalonamento de uma nuvem privada, permitindo cumprir a negociação que foi estabelecida com o usuário. Devido a essa função, é possível garantir que o GreenMACC se comporte seguindo os princípios da computação verde sem deixar de se preocupar com a qualidade do serviço. Nesta tese o GreenMACC é apresentado, detalhado, discutido, validado e avaliado. Com os resultados apresentados pode-se concluir que a arquitetura proposta mostrou-se consistente, permitindo a execução dos serviços requisitados com diversas políticas de escalonamento em todos os seus estágios. Além disso, demonstrou flexibilidade em receber novas políticas, com focos verde e de qualidade de serviço, e eficiência na escolha das políticas de escalonamento de acordo com a negociação feita com o usuário. / This PhD thesis aims to present an architecture for green metascheduling with provision of quality of service in a private cloud called GreenMACC. This new architecture offers the possibility of choosing automatically the four stage scheduling policies of a private cloud, allowing to reach the users negotiation. As a result of this function, it is possible to ensure that GreenMACCs behavior follows the green computing principles and also is worried about the quality of the service. In this thesis Green- MACC is presented, particularized, discussed, validated and evaluated. The results show that the proposed architecture is consistent, allowing the execution of the requested services considering various scheduling policies in the stages. Moreover, GreenMACC proves to be flexible as allows new policies, focusing on green and quality of service, and to be efficient as chooses the scheduling policies following the users negotiation.

O Problema de Escalonamento de Médicos (Physician Scheduling Problem) consiste em atribuir tarefas a médicos num horizonte de planejamento respeitando regras laborais, contratuais e de preferências pessoais de modo a satisfazer a demanda de serviços de um hospital. O problema lida majoritariamente com o objetivo de maximizar o atendimento dos requisitos de preferência pessoal, respeitando as restrições laborais e organizacionais. Sobre esta classe de problemas, vários métodos de resolução e suas variantes têm sido propostos na literatura. Ademais, mais características têm sido agregadas ao problema, tornando-o mais complexo e deste modo fazendo-se mais necessária a aplicação de métodos mais elaborados para a sua resolução. Neste trabalho são estudados, reformulados e propostos métodos de resolução baseados em programação matemática para tratar o problema de escalonamento acíclico de médicos em departamento de emergência de hospitais. O primeiro modelo tem como objetivo a minimização da soma ponderada dos desvios das restrições de distribuição. O segundo modelo tem como objetivo, a minimização do máximo dos desvios obtidos nas restrições de distribuição, a fim de se obter escalas mais equilibradas entre os médicos. Foram também propostas heurísticas baseadas na formulação matemática cujos resultados não foram competitivos com as dos modelos. Os modelos foram testados sobre um conjunto de instâncias fictícias resultantes de uma mescla entre instâncias benchmark e características do problema. Os resultados computacionais demonstram que formulação ponderada obteve solução ótima para grande parte das instâncias, embora os limitantes inferiores tenham sido majoritariamente fracos. Em relação ao segundo modelo, soluções ótimas não foram obtidas e os limitantes inferiores foram igualmente fracos. Relativamente a qualidade das escalas, o segundo modelo teve melhor comportamento comparando ao modelo de somas ponderadas. Dada a qualidade das soluções, nota-se a viabilidade da solução baseada em técnicas de otimização em detrimento da manual, pois esta ainda é mais suscetível de erros e acarreta um alto tempo para obtenção de solução. / The Physician Scheduling Problem consists in task assignment to physicians in a planning horizon considering a set of organizational rules, work regulations and individual preferences in order to satisfy an hospital wards work demand. The aim is to find a schedule which maximizes the satisfaction of individual preferences requirements while meeting work regulations and organizational rules. A plethora of solution methods and its variants have been proposed in the literature to solve this class of problem. Moreover, more features have been aggregated to the problem turning it into a more complex and thus estimulating the application of more elaborated methods to its decision. In this work we study, reshape and propose decision methods based in mathematical programming to handle non-ciclic physician scheduling problem in emergency wards. The first formulation targets the minimization of the weighted sum of distribution constraints deviations. The second formulation targets the minimization of the maximum deviations obtained at the distribution constraints aiming more balanced schedules between the physicians. Mathematical formulation heuristics were also proposed and the findings were not satisfactory as they were not competitive with the model. Experiments with our models were performed over a set of dummy instances, as result a of a mixture of benchmark instances and the considered problems features. From our experiments we have found that optimal solutions were obtained through the weighted sum model, despite the poor lower bounds. On the other hand, for the second model, no optimal solution was found and poor lower bounds were similarly obtained. Regarding to the schedules quality, the min-max model had a better performance comparing to the weighted sum model. Given the solutions quality we can assume that optimization based techniques are sustainable comparing to manual, because the latter is prone to errors and omissions and also critical in terms of solutions achievement time.

Existem vários problemas clássicos na área de pesquisa operacional que trabalham com o tema vinculado à designação de veículos em um sistema logístico, entre eles o Problema de Escalonamento de Veículos com Múltiplas Garagens (MDVSP). Esses modelos são largamente utilizados e representam uma das etapas essenciais para o planejamento de trânsito em massa (HAGHANI e BANIHASHEMI, 2002). Tratando-se de sistemas logísticos reais, dificilmente encontra-se um ambiente onde os veículos devem partir e chegar a uma única garagem, por isso torna-se necessário o planejamento das seqüências de viagens de modo a reduzir os custos de deslocamentos com o aproveitamento das múltiplas garagens distribuídas geograficamente. Infelizmente, considerando a complexidade exponencial do MDVSP, muitas vezes sua aplicação torna-se inviável na solução de problemas reais. Por essa razão, poucos trabalhos abordam o MDVSP de modo a conseguir solucionar o problema para uma grande quantidade de viagens e garagens. A maioria das pesquisas trabalha com instâncias inferiores a 500 viagens e quatro garagens, mostrando-se pouco aplicáveis. Esse estudo refere-se a um trabalho de pesquisa operacional que aborda soluções de problemas de escalonamento de veículos com múltiplas garagens (MDVSP) considerando sua aplicabilidade em sistemas reais. Tendo em vista a complexidade exponencial do MDVSP, nesse estudo optou-se por tratar o problema através de uma abordagem baseada na redução do espaço de estados e na utilização de heurísticas. Durante essa pesquisa três procedimentos de redução do espaço de estados foram adotados. Os resultados apontam que é possível reduzir em até 98% o número de variáveis nesses problemas sem comprometer uma solução satisfatória ou ótima. Além dos procedimentos de redução do espaço de estados, foi desenvolvido um procedimento de buscar a solução do MDVSP. Através desse último procedimento foi possível resolver o MDVSP com até 3000 viagens e oito garagens. Sendo assim, nesse estudo desenvolveram-se modelos que servem para o planejamento de um sistema logístico através da aplicação de cenários, com vistas a permitir a geração e análise de alternativas de escalonamento. Objetivou-se com isso, fornecer ao sistema logístico um modelo amplo que permita a escolha da ação mais conveniente e eficiente a ser tomada em modelos compostos por diversas garagens. / There are many classics problems in operations research concerning optimal assignment vehicles in logistical system. The multiple depot vehicle scheduling problem (MDVSP) is one of them. This problem is largely used to represent and solve mass transit planning (HAGHANI e BANIHASHEMI, 2002). Considering a real logistical system, it is very difficult to find out a situation where the vehicles must leave and come to only one depot. In general, the shipping company has several depots located at different sites in a network. In this way, it is strongly necessary to reduce cost through the planning of sequence trips taking into account multiple depots geographically distributed. Unfortunately, the exponential complexity of the MDVSP reduces, in the most cases, the applicability of this problem in the real world. For this reason, few researchers address the MDVSP to solve real world problems considering a large number of trips and depots. The majority of the research dealing with the MDVSP works with instances lower than 500 trips and four depots, what can be considered a major constraint for its practical use. The main objective of this work is to solve the MDVSP for very large instances. A state space reduction approach combined with heuristic procedures are developed to obtain a realistic way of solving this complex problem. In this research, three state space reduction procedures were developed. The results appointed that is possible to reduce until 98% of variables in the MDVSP without jeopardizing an optimal solution. Furthermore, heuristic procedures were developed to obtain solutions without relaxing any realworld constraint of the problem. The solution procedure developed was compared with wellknown available instances. The method is able to solve the MDVSP with 3000 trips and eight depots in less than 11 minutes. Although the solution process does not obtain the best solution in all tested instances, it is by far the quickest.

Made available in DSpace on 2016-12-23T14:33:39Z (GMT). No. of bitstreams: 1 Dissertacao_CRAVO_G_L_2009.pdf: 1278828 bytes, checksum: ebab7f313edc64bb51241b5c7d587d33 (MD5) Previous issue date: 2009-06-25 / This master s thesis presents an implementation of the GRASP meta-heuristic for solving the Multi-mode Resource constrained Problem of Scheduling Project (MRCPSP). The MRCPSP belongs to the class NP-Hard and therefore has received attention of many researchers. In this thesis, a case study problem of Scheduling Industrial Maintenance is viewed as a MRCPSP. The GRASP was tested with a set of benchmark tests obtained from PSPLIB (Project Scheduling Library). The results showed that the GRASP is a good strategy for solving MRCPSP instances. / Esse trabalho apresenta uma implementação da meta-heurística GRASP para a resolução do Problema de Escalonamento de Projetos com Restrições de Recursos e Múltiplos Modos de Processamento (MRCPSP). O MRCPSP é um problema da classe NP Difícil e por isso vem recebendo atenção dos pesquisadores. Nessa dissertação, também é apresentado um estudo de caso cujo problema de Programação de Manutenção Industrial é visto como um problema de escalonamento de projeto. O GRASP foi testado com o conjunto de instâncias do MRCPSP disponíveis na PSPLIB (Project Scheduling Problem Library). Os resultados obtidos mostraram que o GRASP proposto se configura como uma boa estratégia de solução para o MRCPSP.

Orientador: Eduardo Candido Xavier / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-18T10:12:53Z (GMT). No. of bitstreams: 1 Peixoto_RobsonRobertoSouza_M.pdf: 1268588 bytes, checksum: ff8a093aa133696dcd5bbe31bc4d6e78 (MD5) Previous issue date: 2011 / Resumo: Nesta dissertação estudamos algoritmos para resolver problemas de escalonamento de tarefas em grades computacionais. Dado um conjunto de tarefas submetidas a uma grade computacional, deve-se definir em quais recursos essas tarefas serão executadas. Algoritmos de escalonamento são empregados com o objetivo de minimizar o tempo necessário para executar todas as tarefas (makespan) que foram submetidas. Nosso foco é estudar os atuais algoritmos de escalonamento usados em grades computacionais e comparar estes algoritmos. Nesta dissertação apresentamos algoritmos onlines, aproximados e heurísticas para o problema. Como resultados novos, provamos fatores de aproximação para o algoritmo RR quando utilizado para resolver os problemas R; sit|Tj|Cmax, R; sit|Tj|TPCC, R; sit|Tj = L| Cmax e R; sit|Tj = L|TPCC é justo. Por fim, definimos uma interface que adiciona replicação de tarefas a qualquer algoritmo de escalonamento, onde nós mostramos a aproximação desta interface, e apresentamos uma comparação via simulação dos algoritmos sem e com replicação. Nossas simulações mostram que, com a utilização de replicação, houve a redução no makespan de até 80% para o algoritmo Min-min. Nas nossas análises também fazemos uso da métrica RTPCC que calcula exatamente a quantidade de instruções que foram usadas para executar todas as tarefas / Abstract: In this dissertation, we studied algorithms to solve task scheduling problems in computational grids. Given a task set that was submitted to a computational grid, the problem is to define in which resources these tasks will be executed and the order they will be executed. Scheduling algorithms are used in order to minimize the time required to execute all tasks (makespan). We studied the most recent scheduling algorithms proposed to be used in computational grids, and then compare them using simulations. In this dissertation we also present approximate algorithms and new heuristics for the problem. As new results, we proved approximation factors to the RR algorithm when applied to solve the problems R; sit|Tj|Cmax, R; sit|Tj|TPCC, R; sit|Tj = L| Cmax and R; sit|Tj = L|TPCC. Finally, we defined an interface that adds task replication capability to any scheduling algorithm. We then show approximation results for algorithms using this interface, and present a comparison of well know algorithms with and without replication. This comparison is done via simulation. Our simulations show that, with replication, there was up to 80% of reduction in the makespan to some algorithms like the Min-min / Mestrado / Teoria da Computação / Mestre em Ciência da Computação

Submitted by Nadir Basilio (nadirsb@uninove.br) on 2017-03-01T20:45:26Z No. of bitstreams: 1 Christiane Garrido Schwach.pdf: 1899108 bytes, checksum: 9b2c0c03535e3bd98c46eb138b1cc179 (MD5) / Made available in DSpace on 2017-03-01T20:45:26Z (GMT). No. of bitstreams: 1 Christiane Garrido Schwach.pdf: 1899108 bytes, checksum: 9b2c0c03535e3bd98c46eb138b1cc179 (MD5) Previous issue date: 2016-11-29 / With the opening of the Brazilian market of hospitals for foreign direct investment, authorized from January 2015, some challenges of the private hospitals and the healthcare market is to understand what the investors seek in hospitals to make financial contributions. Some issues as macroeconomic outlook of the market; growth potential of the health sector; knowledge of the risks; existence of attractive hospitals available and Corporate Governance (CG), are essential for the analysis of investors. The need to professionalize the management of hospitals and train more qualified professionals is because, of mergers and acquisitions in health operations, be preceded by a thorough study of economic and financial viability and the assessment of the hospital that will receive the contribution. In this way, openness to foreign capital, brings new concepts to the health sector, particularly as the need for adjustments in current management models, mainly as good CG practices. In this sense, the objective of this study is to analyze the CG practices grip level in hospitals of the National Association of the Private Hospitals (ANAHP), and its indicators of economic and financial performance, which make them attractive to foreign investment. In addition, it elaborated the following research question: What is the relationship between the principles of corporate governance and financial indicators of the hospitals associated with ANAHP within the multidimensional perspective. The methodology is a study of exploratory nature, using a nearly-experimental research strategy, classified as ex post facto. Given a quantitative assessment the research has a multivariate approach, using descriptive analysis, multidimensional scaling (MDS) and application of cluster model. It was found that the group with the highest percentage of member hospitals CG (75%) showed better indicators. This result showed a positive relationship between the economic and financial performance indicators and CG practices and illustrated that the greater transparency of information, the better the economic and financial analysis of hospitals who wish to seek foreign investment. / Com a abertura do mercado brasileiro de hospitais ao investimento estrangeiro direto, autorizada a partir de janeiro de 2015, um dos desafios dos hospitais privados e do mercado de saúde é entender o que os investidores buscarão nas instituições hospitalares para realizar os aportes financeiros. Algumas questões como, perspectivas macroeconômicas do mercado; potencial de crescimento do setor de saúde; conhecimento dos riscos; existência de hospitais atrativos disponíveis e Governança Corporativa (GC), são essenciais para a análise dos investidores. A necessidade de profissionalizar a gestão dos hospitais e formar profissionais mais qualificados, se deve ao fato das operações de fusões e aquisições na saúde, serem precedidas de profundo estudo de viabilidade econômico-financeira e avaliação do hospital que receberá o aporte. Desta maneira, a abertura ao capital estrangeiro traz novos conceitos ao setor da saúde, sobretudo quanto a necessidade de adequações nos atuais modelos de gestão, principalmente quanto as boas práticas de GC. Neste sentido, o objetivo deste trabalho é analisar o nível de aderência as práticas de GC nos hospitais da Associação Nacional dos Hospitais Privados (ANAHP) e seus indicadores de desempenho econômico-financeiros, que os tornam atraentes ao investimento estrangeiro. Ademais, elaborou-se a seguinte questão de pesquisa: Qual é a relação entre os princípios de Governança Corporativa e os indicadores econômico-financeiros dos hospitais associados a ANAHP, dentro da ótica multidimensional. Trata-se de um estudo de natureza exploratório, por meio de uma estratégia de pesquisa quase-experimental, classificada como ex post facto. Perante uma avaliação quantitativa a pesquisa adotou uma abordagem multivariada, por meio da análise descritiva, da técnica de escalonamento multidimensional (EMD) e da aplicação do modelo de agrupamentos. Verificou-se que, o agrupamento com maior percentual de hospitais aderentes as práticas de GC (75%), apresentou os melhores indicadores. Este resultado evidenciou uma relação positiva entre os indicadores de desempenho econômico-financeiros e as práticas de GC e ilustrou que, quanto maior a transparência das informações, melhor a análise econômico-financeira das instituições hospitalares que desejam buscar o investimento estrangeiro.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2015-10-22T10:13:08Z No. of bitstreams: 2 Dissertação - Diego Cruz Abrahão - 2015.pdf: 9765017 bytes, checksum: 6f29592215e8451edda4aa5ad24238f4 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-10-22T10:15:40Z (GMT) No. of bitstreams: 2 Dissertação - Diego Cruz Abrahão - 2015.pdf: 9765017 bytes, checksum: 6f29592215e8451edda4aa5ad24238f4 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-10-22T10:15:40Z (GMT). No. of bitstreams: 2 Dissertação - Diego Cruz Abrahão - 2015.pdf: 9765017 bytes, checksum: 6f29592215e8451edda4aa5ad24238f4 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2015-03-19 / In this paper we propose two schemes for allocating resource blocks for transmission LTE downlink to maximize the throughput of the system, to guarantee QoS (Quality of Service) parameters for the users and reduce the data loss rate of network. The first proposed scheme uses the Max-min criterion and the second employs a fuzzy inference system to calculate the priorities of users and make scheduling decisions. Both schemes use an estimated effective bandwidth of traffic flows of users. The effective bandwidth of a traffic flow is the rate required to meet a criterion of probability of data loss rate. In this work, the effective bandwidth is estimated adaptively by the parameters of multifractal modeling βMWM (β-Multifractal Wavelet Mode). Are made simulations of the algorithms proposed, considering different propagation models with multipath fading and with different numbers of users in the network. The simulation results are compared with other algorithms presented in the literature, using parameters such as: throughput of the system, data loss rate and fairness index. It is also proposed to use predict of the SNR (Signal-to-Noise Ratio) of users, in the scheduling algorithms, using linear prediction of multi-step filter, in view of the delay in receipt of the channel quality information of the users in the base station and the variation of the signal propagation conditions. The multi-step prediction filter is used with the algorithms of allocation of resource blocks proposed in this work to estimate the signal-to-noise-ratio of users and set well, modulation schemes and code to be used in the LTE network. / Neste trabalho são propostos dois esquemas de alocação de blocos de recurso para a transmissão de downlink LTE, visando maximizar a vazão de dados total do sistema, garantir parâmetros de QoS (Quality of Service) dos usuários e diminuir a taxa de perda de dados da rede. O primeiro esquema proposto utiliza o critério Max-min e o segundo emprega um sistema de inferência fuzzy para calcular as prioridades dos usuários e tomar decisões de escalonamento. Ambos os esquemas utilizam estimações de banda efetiva dos fluxos de tráfego dos usuários. A banda efetiva de um fluxo de tráfego é a taxa necessária para atender a um critério de probabilidade de perda de dados. Neste trabalho, a banda efetiva é estimada de forma adaptativa, através dos parâmetros da modelagem multifractal βMWM (β-Multifractal Wavelet Mode). São realizadas simulações dos algoritmos propostos de alocação de blocos de recurso, considerando diferentes modelos de propagação com desvanecimento de multipercursos e com diferentes quantidades de usuários na rede. Os resultados das simulações são comparados com outros algoritmos apresentados na literatura, através de parâmetros, como: vazão de dados do sistema, taxa de perda de dados e índice de justiça. É proposta ainda, a utilização da predição da relação sinalruído (SNR - Signal-to-Noise Ratio) dos usuários nos algoritmos de escalonamento, utilizando filtro de predição linear de multi-passos, tendo em vista o atraso no recebimento da informação da qualidade do canal dos usuários na estação base e a variação das condições de propagação do sinal. O filtro de predição de multi-passos é utilizado junto com os algoritmos de alocação de blocos de recurso propostos neste trabalho, para estimar a relação sinal-ruído dos usuários e definir, assim, os esquemas de modulação e código a serem utilizados na rede LTE.

Made available in DSpace on 2015-04-11T14:02:41Z (GMT). No. of bitstreams: 1 rainer.pdf: 3537323 bytes, checksum: 46bd81628ce774393ea9334f7287a55f (MD5) Previous issue date: 2013-03-27 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This dissertation presents a study on scheduling problems with earliness and tardiness penalties on identical parallel machines, considering independent and weighted jobs with arbitrary processing times. An analysis of the major mathematical formulations in integer programming is given, and presented the main results from the literature. An integer mathematical formulation based on network flow model was also proposed for the problem, which can be applied on single and parallel machines without idle time. Exact methods of implicit enumeration were studied and applied for the problem through the integer linear programming solver CPLEX and the UFFLP library and, mainly, algorithmic strategies of global optimization based on local search heuristic and path-relinking technique were developed. The computational experiments shows that the proposed algorithmic strategies are competitive in relation to existing results from the literature for single-machine scheduling, involving instances based on OR-Library benchmark for 40, 50, 100, 150, 200 and 300 jobs, where all the optimal values were found, and, mainly, being the best algorithmic strategy for multiprocessor environments, involving 2, 4 and 10 identical parallel machines. / Esta dissertação apresenta um estudo sobre problemas de escalonamento com penalidades de antecipação e atraso em máquinas paralelas, considerando tarefas independentes, ponderadas e de tempos de execução arbitrários. Uma análise sobre as principais formulações matemáticas em programação inteira é dada, bem como apresentados os principais resultados da literatura. Uma formulação matemática de programação inteira baseada no modelo de fluxo em redes também foi proposta para o problema, que pode ser aplicada em ambientes mono e multiprocessado sem tempo ocioso. Métodos de enumeração implícita foram estudados e aplicados aos problemas em questão através do resolvedor de programação linear inteira CPLEX e da biblioteca UFFLP, principalmente, estratégias algorítmicas aproximadas de otimização global baseadas em heurísticas de busca local e técnica de reconexão de caminhos foram desenvolvidas. Os experimentos computacionais mostram que as estratégias propostas são competitivas em relação aos resultados existentes na literatura para ambientes de escalonamento monoprocessados, envolvendo instâncias baseadas no benchmark da OR-Library para 40, 50, 100, 150, 200 e 300 tarefas, onde todos os ótimos foram encontrados, e, principalmente, sendo a melhor estratégia apresentada para ambientes multiprocessados, envolvendo 2, 4 e 10 máquinas paralelas idênticas.

Submitted by Franciele Moreira (francielemoreyra@gmail.com) on 2017-12-12T16:13:05Z No. of bitstreams: 2 Tese - Thiago Borges de Oliveira - 2017.pdf: 1684209 bytes, checksum: f64b32084ca6b13a58109e4d2cffe541 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-12-13T09:33:57Z (GMT) No. of bitstreams: 2 Tese - Thiago Borges de Oliveira - 2017.pdf: 1684209 bytes, checksum: f64b32084ca6b13a58109e4d2cffe541 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-12-13T09:33:57Z (GMT). No. of bitstreams: 2 Tese - Thiago Borges de Oliveira - 2017.pdf: 1684209 bytes, checksum: f64b32084ca6b13a58109e4d2cffe541 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-11-29 / Multiway spatial join is an important type of query in spatial data processing, and its efficient execution is a requirement to move spatial data analysis to scalable platforms as has already happened with relational and unstructured data. In this thesis, we provide a set of comprehensive models and methods to efficiently execute multiway spatial join queries in distributed systems. We introduce a cost-based optimizer that is able to select a good execution plan for processing such queries in distributed systems taking into account: the partitioning of data based on the spatial attributes of datasets; the intra-operator level of parallelism, which enables high scalability; and the economy of cluster resources by appropriately scheduling the queries before execution. We propose a cost model based on relevant metadata about the spatial datasets and the data distribution, which identifies the pattern of costs incurred when processing a query in this environment. We formalized the distributed multiway spatial join plan scheduling problem as a bi-objective linear integer model, considering the minimization of both the makespan and the communication cost as objectives. Three methods are proposed to compute schedules based on this model that significantly reduce the resource consumption required to process a query. Although targeting multiway spatial join query scheduling, these methods can be applied to other kinds of problems in distributed systems, notably problems that require both the alignment of data partitions and the assignment of jobs to machines. Additionally, we propose a method to control the usage of resources and increase system throughput in the presence of constraints on the network or processing capacity. The proposed cost-based optimizer was able to select good execution plans for all queries in our experiments, using public datasets with a significant range of sizes and complex spatial objects. We also present an execution engine that is capable of performing the queries with near-linear scalability with respect to execution time. / A multi-junção espacial é um tipo importante de consulta usada no processamento de dados espaciais e sua execução eficiente é um requisito para mover a análise de dados espaciais para plataformas escaláveis, assim como aconteceu com dados relacionais e não estruturados. Nesta tese, propomos um conjunto de modelos e métodos para executar eficientemente consultas de multi-junção espacial em sistemas distribuídos. Apresentamos um otimizador baseado em custos que seleciona um bom plano de execução levando em consideração: o particionamento de dados com base nos atributos espaciais dos datasets; o nível de paralelismo intra-operador que proporciona alta escalabilidade; e o escalonamento das consultas antes da execução que resulta em economia de recursos computacionais. Propomos um modelo de custo baseado em metadados dos datasets e da distribuição de dados, que identifica o padrão de custos incorridos no processamento de uma consulta neste ambiente. Formalizamos o problema de escalonamento de planos de execução da multi-junção espacial distribuída como um modelo linear inteiro bi-objetivo, que minimiza tanto o custo de processamento quanto o custo de comunicação. Propomos três métodos para gerar escalonamentos a partir deste modelo, os quais reduzem significativamente o consumo de recursos no processamento das consultas. Embora projetados para o escalonamento da multi-junção espacial, esses métodos podem também ser aplicados a outros tipos de problemas em sistemas distribuídos, que necessitam do alinhamento de partições de dados e da distribuição de tarefas a máquinas de forma balanceada. Além disso, propomos um método para controlar o uso de recursos e aumentar a vazão do sistema na presença de restrições nas capacidades da rede ou de processamento. O otimizador proposto foi capaz de selecionar bons planos de execução para todas as consultas em nossos experimentos, as quais usaram datasets públicos com uma variedade significativa de tamanhos e de objetos espaciais complexos. Apresentamos também uma máquina de execução, capaz de executar as consultas com escalabilidade próxima de linear em relação ao tempo de execução.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / A evoluÃÃo no desenvolvimento de novos dispositivos, cada vez mais baratos e eficientes, expandiu o uso das Redes Sensores Sem Fio (RSSF) e incentivou a criaÃÃo de novas aplicaÃÃes, no cenÃrio contemporÃneo da ComputaÃÃo UbÃqua e Pervasiva. No entanto, a limitaÃÃo de energia continua sendo um desafio na Ãrea de RSSF. Essa situaÃÃo à agravada ainda mais pela a inviabilidade de recarga de energia jà que, em muitos casos, as RSSF sÃo utilizadas em ambientes inacessÃveis. Com o barateamento dos dispositivos utilizados nas RSSFs, ficou mais fÃcil empregar redes muito densas e de larga escala nos ambientes a serem monitorados. O emprego de redes densas, que apresentam alto grau de redundÃncia dos nÃs, permite que a rede continue funcional mesmo com a exaustÃo de alguns nÃs. AlÃm de oferecer tolerÃncia a falhas, o uso de redes muito densas oferece a oportunidade da implementaÃÃo de mecanismos de escalonamento dos nÃs redundantes, de forma que o tempo de vida da rede seja ainda melhor otimizado. Assumindo um cenÃrio com rede muito densas, este trabalho descreve a implementaÃÃo de um mecanismo de escalonamento autonÃmico, simples, robusto e escalÃvel, com o objetivo de melhorar ainda mais os resultados jà apresentados pelo BiO4SeL, um protocolo de roteamento baseado em ColÃnia de Formigas e desenvolvido para maximizar o tempo de vida da rede. Os resultados mostram que o novo esquema de escalonamento efetivamente melhora o tempo de vida de uma RSSF baseada no BiO4SeL em cenÃrios densos. / he evolution and development of new devices, increasingly cheaper and more efficient, expanded the use of Wireless Sensor Networks (WSN) and encouraged the creation of new applications in the contemporary scenery of Ubiquitous and Pervasive Computing. However, energy limitation remains a challenge in the field of WSN. This situation is aggravated even more by the infeasibility of energy recharge since, in many cases, WSN are used in inaccessible enviroments. With cheapness devices used in WSN, became easier to employ dense and large-scale networks in environments that will be monitored. The use of dense networks, which have a high degree redundancy of nodes, allows the network remains functional even with the exhaustion of some nodes. In addition to provide fault tolerance, the use of very dense networks offer the opportunity of implementing scheduling mechanisms for redundant nodes, in a way that the network lifetime is even better optimized. Assuming a scenery with very dense networks, this dissertation describes the implementation of an autonomic scheduling mechanism, simple, robust and scalable, in order to further improve the results already presented by BiO4SeL, which is a routing protocol based on Ant Colony and designed to maximize the network lifetime. The results show that the new scheduling scheme effectively improves the WSN lifetime based on BiO4SeL in dense scenarios.