Zugl.: Darmstadt, Techn. University, Diss., 2007.

Zugl.: Heidelberg, Univ., Diss., 2004. - Hergestellt on demand

Zugl.: Karlsruhe, University, Diss., 2006.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Zugl.: Darmstadt, Techn. University, Diss., 2008.

Cette thèse porte sur la résolution exacte et heuristique de plusieurs problèmes ayant des applications dans le domaine de l'Informatique dématérialisé (cloud computing). L'Informatique dématérialisée est un domaine en plein extension qui consiste à mutualiser les machines/serveurs en définissant des machines virtuelles représentant des fractions des machines/serveurs. Il est nécessaire d'apporter des solutions algorithmiques performantes en termes de temps de calcul et de qualité des solutions. Dans cette thèse, nous nous sommes intéressés dans un premier temps au problème d'ordonnancement sur plusieurs machines (les machines virtuelles) avec contraintes de précédence, c.-à-d., que certaines tâches ne peuvent s'exécuter que si d'autres sont déjà finies. Ces contraintes représentent une subdivision des tâches en sous tâches pouvant s'exécuter sur plusieurs machines virtuelles. Nous avons proposé plusieurs algorithmes génétiques permettant de trouver rapidement une bonne solution réalisable. Nous les avons comparés avec les meilleurs algorithmes génétiques de la littérature et avons défini les types d'instances où les solutions trouvées sont meilleures avec notre algorithme. Dans un deuxième temps, nous avons modélisé ce problème à l'aide de la programmation linéaire en nombres entiers permettant de résoudre à l'optimum les plus petites instances. Nous avons proposé de nouvelles inégalités valides permettant d'améliorer les performances de notre modèle. Nous avons aussi comparé cette modélisation avec plusieurs formulations trouvées dans la littérature. Dans un troisième temps, nous avons analysé de manière approfondie la sous-structure du sous-graphe d'intervalle ne possédant pas de clique de taille donnée. Nous avons étudié le polytope associé à cette sous-structure et nous avons montré que les facettes que nous avons trouvées sont valides pour le problème d'ordonnancement sur plusieurs machines avec contraintes de précédence mais elles le sont aussi pour tout problème d'ordonnancement sur plusieurs machines. Nous avons étendu la modélisation permettant de résoudre le précédent problème afin de résoudre le problème d'ordonnancement sur plusieurs machines avec des contraintes disjonctives entre les tâches, c.-à-d., que certaines tâches ne peuvent s'exécuter en même temps que d'autres. Ces contraintes représentent le partage de ressources critiques ne pouvant pas être utilisées par plusieurs tâches. Nous avons proposé des algorithmes de séparation afin d'insérer de manière dynamique nos facettes dans la résolution du problème puis avons développé un algorithme de type Branch-and-Cut. Nous avons analysé les résultats obtenus afin de déterminer les inégalités les plus intéressantes afin de résoudre ce problème. Enfin dans le dernier chapitre, nous nous sommes intéressés au problème d'ordonnancement d'atelier généralisé ainsi que la version plus classique d'ordonnancement d'atelier (open shop). En effet, le problème d'ordonnancement d'atelier généralisé est aussi un cas particulier du problème d'ordonnancement sur plusieurs machines avec des contraintes disjonctives entre les tâches. Nous avons proposé une formulation à l'aide de la programmation mathématique pour résoudre ces deux problèmes et nous avons proposé plusieurs familles d'inégalités valides permettant d'améliorer les performances de notre algorithme. Nous avons aussi pu utiliser les contraintes définies précédemment afin d'améliorer les performances pour le problème d'ordonnancement d'atelier généralisé. Nous avons fini par tester notre modèle amélioré sur les instances classiques de la littérature pour le problème d'ordonnancement d'atelier. Nous obtenons de bons résultats permettant d'être plus rapide sur certaines instances / The Cloud Computing appears as a strong concept to share costs and resources related to the use of end-users. As a consequence, several related models exist and are widely used (IaaS, PaaS, SaaS. . .). In this context, our research focused on the design of new methodologies and algorithms to optimize performances using the scheduling and combinatorial theories. We were interested in the performance optimization of a Cloud Computing environment where the resources are heterogeneous (operators, machines, processors...) but limited. Several scheduling problems have been addressed in this thesis. Our objective was to build advanced algorithms by taking into account all these additional specificities of such an environment and by ensuring the performance of solutions. Generally, the scheduling function consists in organizing activities in a specific system imposing some rules to respect. The scheduling problems are essential in the management of projects, but also for a wide set of real systems (telecommunication, computer science, transportation, production...). More generally, solving a scheduling problem can be reduced to the organization and the synchronization of a set of activities (jobs or tasks) by exploiting the available capacities (resources). This execution has to respect different technical rules (constraints) and to provide the maximum of effectiveness (according to a set of criteria). Most of these problems belong to the NP-Hard problems class for which the majority of computer scientists do not expect the existence of a polynomial exact algorithm unless P=NP. Thus, the study of these problems is particularly interesting at the scientific level in addition to their high practical relevance. In particular, we aimed to build new efficient combinatorial methods for solving parallel-machine scheduling problems where resources have different speeds and tasks are linked by precedence constraints. In our work we studied two methodological approaches to solve the problem under the consideration : exact and meta-heuristic methods. We studied three scheduling problems, where the problem of task scheduling in cloud environment can be generalized as unrelated parallel machines, and open shop scheduling problem with different constraints. For solving the problem of unrelated parallel machines with precedence constraints, we proposed a novel genetic-based task scheduling algorithms in order to minimize maximum completion time (makespan). These algorithms combined the genetic algorithm approach with different techniques and batching rules such as list scheduling (LS) and earliest completion time (ECT). We reviewed, evaluated and compared the proposed algorithms against one of the well-known genetic algorithms available in the literature, which has been proposed for the task scheduling problem on heterogeneous computing systems. Moreover, this comparison has been extended to an existing greedy search method, and to an exact formulation based on basic integer linear programming. The proposed genetic algorithms show a good performance dominating the evaluated methods in terms of problems' sizes and time complexity for large benchmark sets of instances. We also extended three existing mathematical formulations to derive an exact solution for this problem. These mathematical formulations were validated and compared to each other by extensive computational experiments. Moreover, we proposed an integer linear programming formulations for solving unrelated parallel machine scheduling with precedence/disjunctive constraints, this model based on the intervaland m-clique free graphs with an exponential number of constraints. We developed a Branch-and-Cut algorithm, where the separation problems are based on graph algorithms. [...]

Submitted by Viviane Lima da Cunha (viviane@biblioteca.ufpb.br) on 2016-02-17T11:41:50Z No. of bitstreams: 1 arquivototal.pdf: 1276201 bytes, checksum: 9dd8fad80c483276a40101ee6a782d5b (MD5) / Made available in DSpace on 2016-02-17T11:41:50Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 1276201 bytes, checksum: 9dd8fad80c483276a40101ee6a782d5b (MD5) Previous issue date: 2015-07-21 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work deals with the p-Cluster Editing Problem (p-CEP), which consists in performing a minimum number of editions (additions or removals of edges) in a graph G in order to transform it in a disjoint union of p cliques (clusters), where G and p are input data. p-CEP is a NP-Hard problem with applications in areas such as computational biology and machine learning. To solve this problem, we propose two new mathematical formulations and improvements in a formulation from the literature, as well as new valid inequalities. The three formulations were studied both theoretically, by comparing their linear relaxations, and practically, by implementing three exact algorithms: two based on Branch-and-Cut (BC) and one based on Branch-and-Price (BP). The proposed algorithms were tested in instances with up to 211 vertices. The results show the performance of the algorithms according to the graph density and the ratio between p and the number of vertices. Overall, the BC algorithms were superior to the BP algorithm. However, the latter obtained the best dual bounds in some instances. / Este trabalho trata do Problema de Edi¸c˜ao de p-Clusters (p-PEC), o qual consiste em realizar um n´umero m´ınimo de edi¸c˜oes (adi¸c˜oes ou remo¸c˜oes de arestas) em um grafo G de modo a transform´a-lo em uma uni˜ao disjunta de p cliques (ou clusters), sendo G e p dados de entrada. O p-PEC ´e um problema NP-Dif´ıcil que possui aplica¸c˜oes em ´areas como biologia computacional e aprendizagem de m´aquina. Para resolvˆe-lo, foram propostas duas novas formula¸c˜oes matem´aticas e melhorias em uma formula¸c˜ao proveniente da literatura, bem como novas desigualdades v´alidas. As trˆes formula¸c˜oes consideradas foram estudadas tanto teoricamente, atrav´es da compara¸c˜ao entre as relaxa¸c˜oes lineares, quanto empiricamente, atrav´es do desenvolvimento de trˆes algoritmos exatos: dois baseados em Branch-and-Cut (BC) e um baseado em Branch-and-Price (BP). Os algoritmos foram testados em instˆancias com at´e 211 v´ertices. Os resultados mostram o impacto da raz˜ao entre p e o n´umero de v´ertices, da densidade do grafo e das desigualdades nos desempenhos dos algoritmos. No geral, os algoritmos BC foram superiores ao algoritmo BP. Por´em, em algumas instˆancias, os melhores limites duais foram obtidos pelo algoritmo BP.

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-17T07:58:08Z (GMT). No. of bitstreams: 1 Porto_ClaudiaAkemiFurushima_M.pdf: 1805902 bytes, checksum: 15341772d15a37d8642fa403d27fbd6a (MD5) Previous issue date: 2010 / Resumo: O resumo poderá ser visualizado no texto completo da tese digital / Abstract: The abstract is available with the full electronic digital document / Mestrado / Teoria da Computação / Mestre em Ciência da Computação

Orientador: Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T12:28:53Z (GMT). No. of bitstreams: 1 Lopes_MauroCardoso_M.pdf: 3797752 bytes, checksum: c82bee131ad99d747e42150908135190 (MD5) Previous issue date: 2014 / Resumo: Investigamos uma variante do problema de localização e roteamento com relação de muitos-para-muitos concentradores que consiste em particionar o conjunto de vértices de um grafo em ciclos contendo exatamente um concentrador cada e determinar um ciclo adicional interligando todos os concentradores. Qualquer vértice do grafo pode ser um concentrador; faz parte do problema determinar quais vértices devem ser concentradores. Esse problema tem aplicações práticas relevantes em áreas como transporte urbano e redes de computadores. Desenvolvemos uma heurística baseada em busca local com operações de inserção, remoção e troca de vértices. Soluções iniciais são geradas de maneira aleatória, e suas vizinhanças são exploradas a fim de obter melhores soluções. Além disso, elaboramos um algoritmo exato com estrutura de branch-and-cut para a formulação em Programação Linear Inteira proposta. Restrições de capacidade e eliminação de caminhos são adicionadas como planos de corte, com algoritmos de separação baseados em árvores de corte mínimo e nas componentes conexas de um grafo suporte. Diversos experimentos computacionais mostram a capacidade de resolução do algoritmo exato para instâncias pequenas e da heurística para instâncias pequenas e médias. São comparados também os desempenhos para outras variantes do problema / Abstract: We investigate a variant of the many-to-many hub location-routing problem which consists in partitioning the set of vertices of a graph into cycles containing exactly one hub each and determining an extra cycle interconnecting all hubs. Any vertex of the graph can be a hub; it is part of the problem to determine which vertices should be hubs. This problem has relevant practical applications in areas such as urban transportation and computer networks. A local search based heuristic that considers add/remove and swap operations is developed. Initial solutions can be generated at random, and their neighborhoods are explored in order to get better solutions. Also a branch-and-cut approach that solves an integer formulation is investigated. Capacity and path elimination constraints are added in a cutting plane way, so the separation algorithms are based on the computation of min-cut trees and in the connected components of a support graph. Many computational experiments over several instances adapted from literature show the problem-solving capability of the exact algorithm for small instances and of the heuristic for small to medium-sized instances. We also compare the performance of other variants of the problem / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

[pt] A propagação de influências tem sido objeto de extensos estudos devido a seu importante impacto em redes sociais, epidemiologia e muitas outras áreas. A compreensão do mecanismo de propagação é crítica, por exemplo, para controlar a disseminação de notícias falsas ou controlar uma epidemia. Neste trabalho, seguimos uma perspectiva de otimização e identificamos o menor grupo de usuários que precisam ser convertidos para atingir um certo nível de influência em toda a rede. Portanto, estudamos formalmente o problema de influência de menor custo generalizado, propondo algoritmos de programação matemática para resolver este problema. Introduzimos novos algoritmos de planos de corte e separação, e os incorporamos em um algoritmo de branch-and-cut. Nossos resultados experimentais em instâncias da literatura demonstram a capacidade do método de resolver pequenas e médias instâncias, bem como diminuir o gap da melhor solução conhecida e inclusive encontrando também soluções ótimas para alguns problemas em aberto. / [en] Influence propagation has been the subject of extensive study due to its important role in social networks, epidemiology, and many other areas. Understanding the propagation mechanism is critical, e.g., to control the spread of fake news or to control an epidemic. In this work, we follow an optimization perspective, and attempt to identify the smallest group of users that needs to be converted to achieve an certain influence level over the entire network. We therefore formally study the generalized least cost influence problem, proposing mathematical programming algorithms to solve the challenging problem. We introduce new cutting plane and separation algorithms and embed them into a branch-and-cut algorithm. Our experimental results on classical benchmark instances demonstrates the method ability to solve small-to medium-scale benchmark instances, also finding optimal solutions for some open problems.