The Vehicle Routing Problem (VRP) is a classical problem in logistics that has been well studied by the operations research and transportation science communities. VRPs are defined as follows. Given a transportation network with a depot, a set of pickup or delivery locations, and a set of vehicles to service these locations: find a collection of routes starting and ending at the depot, such that (i) the customer's demand at a node is satisfied by exactly one vehicle, (ii) the total demand satisfied by a vehicle does not exceed its capacity, and (iii) the total distance traveled by the vehicles is minimized. This problem is especially hard to solve because of the presence of sub--tours, which can be exponential in number. In this dissertation, a special case of the VRP is considered -- where the underlying network has a tree structure (TVRP). Such tree structures are found in rural areas, river networks, assembly lines of manufacturing systems, and in networks where the customer service locations are all located off a main highway. Solution techniques for TVRPs that explicitly consider their tree structure are discussed in this dissertation. For example, TVRPs do not contain any sub-tours, thereby making it possible to develop faster solution methods. The variants that are studied in this dissertation include TVRPs with Backhauls, TVRPs with Heterogeneous Fleets, TVRPs with Duration Constraints, and TVRPs with Time Windows. Various properties and observations that hold true at optimality for these problems are discussed. Integer programming formulations and solution techniques are proposed. Additionally, heuristic methods and conditions for lower bounds are also detailed. Based on the proposed methodology, extensive computational analysis are conducted on networks of different sizes and demand distributions. / text

Neste trabalho foi analisada a influência de um evento sobre o mercado de ações brasileiro a partir das redes, e suas árvores geradoras mínimas, obtidas de medidas de dependência baseadas nas correlações de Pearson, de Spearman e de Kendall. O evento considerado foi a notícia da noite de 17 de maio de 2017 em que o dono da empresa brasileira JBS, Joesley Batista, gravou o então Presidente da República Michel Temer autorizando a compra do silêncio de um Deputado Federal. O dia seguinte a notícia, 18 de maio de 2017, foi definido como o dia do evento. Foram coletados dados de alta frequência de 58 ações do Ibovespa no período de 11 a 25 de maio de 2017. As alterações nas redes das ações do mercado foram analisadas comparando-se o período anterior e posterior ao evento em duas escalas de tempo: (1) Redes diárias: cinco pregões antes do evento, o dia do evento e, cinco pregões depois do evento, com cotações a cada 15 minutos; (2) Agrupadas em antes e depois: agrupando os dados dos 5 dias antes e dos 5 dias depois do evento. O estudo das redes diárias indicou mudança de tendência nas suas propriedades no decorrer do período que contém o evento, com cotações a cada 15 minutos. Isto sugeriu que análise do efeito médio contido nos dados agrupados antes de depois do evento poderiam tornar mais evidente as mudanças na estrutura de rede das ações. As redes antes e depois do evento apresentaram mudanças significativas nas suas métricas que ficaram mais evidenciadas nas árvores geradoras mínimas. As redes geradas pelas correlações de Kendall e Spearman apresentaram um número maior de agrupamentos antes e depois do evento e, após o evento, as árvores geradoras mínimas apresentaram uma redução do número de agrupamentos de ações para todos os tipos de correlação. As distribuições de grau ponderado após o evento indicam uma probabilidade maior de vértices com graus distante da média. As métricas das árvores geradoras mínimas por correlação de Spearman sofreram a maior variação, seguidas pelas de Kendall e Pearson, e também, indicaram que as redes após o evento ficaram mais robustas, ou seja, mais rígidas. A maior robustez das redes após o evento indica maior conectividade do mercado, tornando-o, como um todo, mais suscetível ao impacto de novos acontecimentos. / In this work the influence of an event on the Brazilian stock market was analyzed from networks and its minimum spanning trees obtained from measures of dependence based on the Pearson, Spearman, and Kendall\'s correlations. The event considered was the news in the evening of May 17, 2017 in which the owner of the Brazilian company JBS, Joesley Batista, recorded the Brazilian President Michel Temer authorizing the purchase of the silence of a congress member. The day just after the news, May 18, 2017, was defined as the event day. High-frequency data from 58 Ibovespa shares were collected from 11 to 25 May 2017. Changes in the stocks networks were analyzed comparing the period before and after the event in two time scales: (1) Daily networks: five trade sections before the event, the day of the event and, five trade sections after the event, with price every 15 minutes; (2) Grouped before and after do evento: grouping data from 5 days before and 5 days after event. The study of the daily networks indicated a change of trend in their properties during the period that contains the event, with quotations every 15 minutes. The study of daily networks indicated a change of trend in their properties during the period containing the event. This suggested that analysis of the mean effect of grouped data before and after the event could highlight the changes in the network structure. The networks before and after the event showed significant changes in their metrics, which became more evident from the minimum spanning trees. After the event, the minimum spanning trees for grouped data got a smaller number of clusters in the networks for all kind of correlations. The networks generated by Kendall and Spearman correlations presented a larger number of clusters before and after the event. The weighted degree distributions after the event suggest a power law decay tail for all the correlations considered and indicates a higher probability of vertices with weighted degrees far away from the mean weighted degree. The minimum spanning tree metrics generated by Spearman correlation suffered the greatest variation, followed by those of Kendall and Pearson; and their values indicates that after the event the networks became more robust, that is, more rigid. The increase in the networks robustness after the event indicates a higher market connectivity, making it as a whole, more susceptible to the impact of new events.

Neste trabalho foi analisada a influência de um evento sobre o mercado de ações brasileiro a partir das redes, e suas árvores geradoras mínimas, obtidas de medidas de dependência baseadas nas correlações de Pearson, de Spearman e de Kendall. O evento considerado foi a notícia da noite de 17 de maio de 2017 em que o dono da empresa brasileira JBS, Joesley Batista, gravou o então Presidente da República Michel Temer autorizando a compra do silêncio de um Deputado Federal. O dia seguinte a notícia, 18 de maio de 2017, foi definido como o dia do evento. Foram coletados dados de alta frequência de 58 ações do Ibovespa no período de 11 a 25 de maio de 2017. As alterações nas redes das ações do mercado foram analisadas comparando-se o período anterior e posterior ao evento em duas escalas de tempo: (1) Redes diárias: cinco pregões antes do evento, o dia do evento e, cinco pregões depois do evento, com cotações a cada 15 minutos; (2) Agrupadas em antes e depois: agrupando os dados dos 5 dias antes e dos 5 dias depois do evento. O estudo das redes diárias indicou mudança de tendência nas suas propriedades no decorrer do período que contém o evento, com cotações a cada 15 minutos. Isto sugeriu que análise do efeito médio contido nos dados agrupados antes de depois do evento poderiam tornar mais evidente as mudanças na estrutura de rede das ações. As redes antes e depois do evento apresentaram mudanças significativas nas suas métricas que ficaram mais evidenciadas nas árvores geradoras mínimas. As redes geradas pelas correlações de Kendall e Spearman apresentaram um número maior de agrupamentos antes e depois do evento e, após o evento, as árvores geradoras mínimas apresentaram uma redução do número de agrupamentos de ações para todos os tipos de correlação. As distribuições de grau ponderado após o evento indicam uma probabilidade maior de vértices com graus distante da média. As métricas das árvores geradoras mínimas por correlação de Spearman sofreram a maior variação, seguidas pelas de Kendall e Pearson, e também, indicaram que as redes após o evento ficaram mais robustas, ou seja, mais rígidas. A maior robustez das redes após o evento indica maior conectividade do mercado, tornando-o, como um todo, mais suscetível ao impacto de novos acontecimentos. / In this work the influence of an event on the Brazilian stock market was analyzed from networks and its minimum spanning trees obtained from measures of dependence based on the Pearson, Spearman, and Kendall\'s correlations. The event considered was the news in the evening of May 17, 2017 in which the owner of the Brazilian company JBS, Joesley Batista, recorded the Brazilian President Michel Temer authorizing the purchase of the silence of a congress member. The day just after the news, May 18, 2017, was defined as the event day. High-frequency data from 58 Ibovespa shares were collected from 11 to 25 May 2017. Changes in the stocks networks were analyzed comparing the period before and after the event in two time scales: (1) Daily networks: five trade sections before the event, the day of the event and, five trade sections after the event, with price every 15 minutes; (2) Grouped before and after do evento: grouping data from 5 days before and 5 days after event. The study of the daily networks indicated a change of trend in their properties during the period that contains the event, with quotations every 15 minutes. The study of daily networks indicated a change of trend in their properties during the period containing the event. This suggested that analysis of the mean effect of grouped data before and after the event could highlight the changes in the network structure. The networks before and after the event showed significant changes in their metrics, which became more evident from the minimum spanning trees. After the event, the minimum spanning trees for grouped data got a smaller number of clusters in the networks for all kind of correlations. The networks generated by Kendall and Spearman correlations presented a larger number of clusters before and after the event. The weighted degree distributions after the event suggest a power law decay tail for all the correlations considered and indicates a higher probability of vertices with weighted degrees far away from the mean weighted degree. The minimum spanning tree metrics generated by Spearman correlation suffered the greatest variation, followed by those of Kendall and Pearson; and their values indicates that after the event the networks became more robust, that is, more rigid. The increase in the networks robustness after the event indicates a higher market connectivity, making it as a whole, more susceptible to the impact of new events.

No description available.

In this thesis we have tackled a few scheduling problems under energy constraint, since the energy issue is becoming crucial, for both economical and environmental reasons. In the first chapter, we exhibit tight bounds on the energy metric of a classical algorithm that minimizes the makespan of independent tasks. In the second chapter, we schedule several independent but concurrent pipelined applications and address problems combining multiple criteria, which are period, latency and energy. We perform an exhaustive complexity study and describe the performance of new heuristics. In the third chapter, we study the replica placement problem in a tree network. We try to minimize the energy consumption in a dynamic frame. After a complexity study, we confirm the quality of our heuristics through a complete set of simulations. In the fourth chapter, we come back to streaming applications, but in the form of series-parallel graphs, and try to map them onto a chip multiprocessor. The design of a polynomial algorithm on a simple problem allows us to derive heuristics on the most general problem, whose NP-completeness has been proven. In the fifth chapter, we study energy bounds of different routing policies in chip multiprocessors, compared to the classical XY routing, and develop new routing heuristics. In the last chapter, we compare the performance of different algorithms of the literature that tackle the problem of mapping DAG applications to minimize the energy consumption.

Over the past decade, the explosive growth of the Internet has led to a surge of interest to understand and predict aggregate behavior of large number of people or agents, particularly when they are connected through an underlying network structure. Numerous Internet-based applications have emerged that are as diverse as getting micro-tasks executed through online labor markets (also known as crowd sourcing) to acquiring new skills through massively open online courses (also known as MOOCs). However, there has been a major inadequacy in existing studies with respect to evaluating the impact of strategic behavior of the agents participating in such networks, crowds, and classrooms. The primary focus of this doctoral work is to understand the equilibrium behaviour emerging from these real-world, strategic environments by blending ideas from the areas of game theory, graph theory, and optimization, to derive novel solutions to these new-age economic models. In particular, we investigate the following three research challenges: (1) How do strategic agents form connections with one another? Will it ever happen that strategically stable networks are social welfare maximizing as well? (2) How do we design mechanisms for eliciting truthful feedback about an object (perhaps a new product or service or person) from a crowd of strategic raters? What can we tell about these mechanisms when the raters are connected through a social network? (3) How do we incentivize better participation of instructors and students in online edu-cation forums? Can we recommend optimal strategies to students and instructors to get the best out of these forums?

Dans cette thèse, nous nous sommes intéressés à des problèmes d'ordonnancement sous contrainte d'énergie, puisque la réduction de l'énergie est devenue une nécessité, tant sur le plan économique qu'écologique. Dans le premier chapitre, nous exhibons des bornes strictes sur l'énergie d'un algorithme classique qui minimise le temps d'exécution de tâches indépendantes. Dans le second chapitre, nous ordonnançons plusieurs applications chaînées de type « streaming », et nous étudions des problèmes contraignant l'énergie, la période et la latence. Nous effectuons une étude de complexité exhaustive, et décrivons les performances de nouvelles heuristiques. Dans le troisième chapitre, nous étudions le problème de placement de répliques dans un réseau arborescent. Nous nous plaçons dans un cadre dynamique, et nous bornons à minimiser l'énergie. Après une étude de complexité, nous confirmons la qualité de nos heuristiques grâce à un jeu complet de simulations. Dans le quatrième chapitre, nous revenons aux applications « streaming », mais sous forme de graphes série-parallèles, et nous tentons de les placer sur un processeur multi-cœur. La découverte d'un algorithme polynomial sur un problème simple nous permet la conception d'heuristiques sur le problème le plus général dont nous avons établi la NP-complétude. Dans le cinquième chapitre, nous étudions des bornes énergétiques de politiques de routage dans des processeurs multi-cœurs, en comparaison avec le routage classique XY, et développons de nouvheuristiques de routage. Dans le dernier chapitre, nous étudions expérimentalement le placement d'applications sous forme de DAG sur des machines réelles. / In this thesis we have tackled a few scheduling problems under energy constraint, since the energy issue is becoming crucial, for both economical and environmental reasons. In the first chapter, we exhibit tight bounds on the energy metric of a classical algorithm that minimizes the makespan of independent tasks. In the second chapter, we schedule several independent but concurrent pipelined applications and address problems combining multiple criteria, which are period, latency and energy. We perform an exhaustive complexity study and describe the performance of new heuristics. In the third chapter, we study the replica placement problem in a tree network. We try to minimize the energy consumption in a dynamic frame. After a complexity study, we confirm the quality of our heuristics through a complete set of simulations. In the fourth chapter, we come back to streaming applications, but in the form of series-parallel graphs, and try to map them onto a chip multiprocessor. The design of a polynomial algorithm on a simple problem allows us to derive heuristics on the most general problem, whose NP-completeness has been proven. In the fifth chapter, we study energy bounds of different routing policies in chip multiprocessors, compared to the classical XY routing, and develop new routing heuristics. In the last chapter, we compare the performance of different algorithms of the literature that tackle the problem of mapping DAG applications to minimize the energy consumption.