Este trabalho apresenta proposta de modelo matemático para o problema de expansão do sistema de transmissão baseado no fluxo de carga CC considerando a utilização de links CC e FACTS resolvido através de metodologia de solução que considera a primeira e a segunda lei de Kirchhoff em processo enumerativo de branch-and-bound adaptado. A abordagem possui dois pontos em destaque: i) apresenta uma proposta de modelo matemático com possibilidade da utilização direta em problemas de expansão de linhas de transmissão que possuem tanto linhas de transmissão CA, transformadores, links CC e dispositivos FACTS e ii) é um método exato de solução do problema que garante a otimalidade da resposta e traz uma contribuição ao tradicional método branch-and-bound por incluir relaxações adicionais. O método aplicado aos sistemas de 6 barras de Garver e sistema Sul sudeste Brasileiro de 46 barras apresenta respostas adequadas e o modelo matemático testado em um sistema Garver modificado apresenta novas configurações possíveis com redução do custo total do investimento. / This work proposes a mathematical model to the transmission expansion system problem based on the DC power flow model considering the use of DC links and FACTS that is solved using a solution method considering the first and second Kirchhoff’s Law in an enumerative adapted branch-and-bound process. It is possible to highlight two key aspects of the proposed approach: i) presents a mathematical model that can be directly used on expansion transmission systems problems that have AC transmission lines, transformers, DC links and FACTS and ii) is an exact solution method that guarantees the optimum problems’s solutions and contributes to the traditional branch-and-bound method bringing additional relaxations. The solution method applied to Garver’s six-bus network and southeast Brazilian 46 bus network provides correct answers and the mathematical model tested on a modified Garver’s six-bus network presents new possible configurations that enables overall cost reduction to the problem.

Dans cette thèse, nous étudions trois problèmes d'ordonnancement de la chaîne logistique dans le modèle de production à la demande. Le premier problème est un problème d'ordonnancement de production et de distribution intermédiaire dans une chaîne logistique avec un producteur et un prestataire logistique. Le deuxième problème est un problème d'ordonnancement de production et de distribution aval avec des dates de début au plus tôt et des dates limites de livraison dans une chaîne logistique avec un producteur, un prestataire logistique et un client. Le troisième problème est un problème d'ordonnancement de production et de distribution aval avec des temps de réglage et des fenêtres de temps de livraison dans une chaîne logistique avec un producteur, un prestataire logistique et plusieurs clients. Pour les trois problèmes, nous étudions les problèmes d'ordonnancement individuels et les problèmes d'ordonnancement coordonnés. Nous proposons des algorithmes polynomiaux ou prouvons la NP-Complétude de ces problèmes, et développons des algorithmes exacts ou heuristiques pour résoudre les problèmes NP-Difficiles. Nous proposons des mécanismes de coordination et évaluons le bénéfice de la coordination. / In this dissertation, we aim at investigating three supply chain scheduling problems in the make-To-Order business model. The first problem is a production and interstage distribution scheduling problem in a supply chain with a manufacturer and a third-Party logistics (3PL) provider. The second problem is a production and outbound distribution scheduling problem with release dates and deadlines in a supply chain with a manufacturer, a 3PL provider and a customer. The third problem is a production and outbound distribution scheduling problem with setup times and delivery time windows in a supply chain with a manufacturer, a 3PL provider and several customers. For the three problems, we study their individual scheduling problems and coordinated scheduling problems: we propose polynomial-Time algorithms or prove the intractability of these problems, and develop exact algorithms or heuristics to solve the NP-Hard problems. We establish mechanisms of coordination and evaluate the benefits of coordination.

Nous abordons dans cette thèse des problèmes de flowshop de permutation soumis des contraintes de délais minimaux et maximaux avec deux types de travaux principaux : 1. Nous avons modélisé, en utilisant l'algèbre MaxPlus, des problèmes de flowshop de permutation m-machines soumis une famille de contraintes : de délais minimaux, de délais maximaux, de sans attente, de délais fixes, de temps de montage indé- pendant de la séquence, de temps de démontage indépendant de la séquence, de blocage, de dates de début au plus tæt ainsi que de durées de latence. Des matrices caractérisant complètement leurs travaux associés ont été élaborées. Nous avons fait apparaître un problème central soumis des contraintes de délais minimaux et maximaux. 2. Nous avons élaboré des bornes inférieures pour le makespan et pour la somme (pondérée ou non) des dates de fin. Ces bornes inférieures ont été incorporées dans des procédures par séparation et évaluation. Nous avons généralisé les bornes inférieures de Lageweg et al. pour des contraintes quelconques et amélioré une borne inférieure de la littérature. L'utilisation de chacune de ces bornes inférieures ainsi que de leurs combinaisons ont été testées. Une famille de bornes inférieures pour la somme (pondérée ou non) des dates de fin a été élaborée basée sur la résolution d'un problème une machine et sur la résolution d'un problème de voyageur de commerce. Une politique de sélection de bornes inférieures a été proposée pour combiner les bornes inférieures. Bien qu'il s'agisse d'un problème de NP-difficile, l'efficacité de ces bornes inférieures a été vérifiée l'aide de tests. / In this thesis, permutation flowshop problems with minimal and maximal delay constraints were considered through two following principal tasks were particularly tackled. 1. In the first task, m-machine permutation flowshop problems with a family of constraints (minimal delays, maximal delays, no-wait, fixed delays, sequence-independent setup times, sequence-independent removal times, blocking, ready dates, duration of latency) were modeled using MaxPlus algebra. Job associated matrices which totally characterize these jobs were elaborated. The modeling led to reveal a central problem with constraints of minimal and maximal delays. 2. In the second task, lower bounds for makespan and for total (weighted or unweighted) completion times were elaborated. These lower bounds were incorporated in branchand-bound procedures. The lower bounds of Lageweg et al. were generalized for any constraint and a existed lower bound was improved. The usage of each of these lower bounds as well as that of their combinations was tested. A family of lower bounds for total (weighted or non-weighted) completion times was elaborated thanks to the solution of a one-machine problem and the solution of a traveling salesman problem. A lower bound selection strategy was proposed in order to combine these lower bounds. Despite necessity to solve a NP-hard problem, the effectiveness of these lower bounds was verified by numerical tests.

SANTOS, Marcio Costa. Experimentos computacionais com implementações de conjunto por endereçamento direto e o problema de conjunto independente máximo. 2013. 78 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2013. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-11T19:04:45Z No. of bitstreams: 1 2013_dis_mcsantos.pdf: 1370695 bytes, checksum: f82fbf8bcae3901a15066e6d39ac2720 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-20T11:59:49Z (GMT) No. of bitstreams: 1 2013_dis_mcsantos.pdf: 1370695 bytes, checksum: f82fbf8bcae3901a15066e6d39ac2720 (MD5) / Made available in DSpace on 2016-07-20T11:59:49Z (GMT). No. of bitstreams: 1 2013_dis_mcsantos.pdf: 1370695 bytes, checksum: f82fbf8bcae3901a15066e6d39ac2720 (MD5) Previous issue date: 2013 / The use of bit vectors is a usual practice for represent sets by direct addressing with the aim of reduce memory consumed and improve efficiency of applications with the use of bit parallel techniques. In this text, we study implementations for represent sets by direct addressed. The basic structure in this implementations is the bit vector. Besides that basic implementation, we implement two variations also. The first one is a stratification of the bit vector, while the second uses a hash table. The operations linked to the implemented structure are include and remove an element and the union and intersection of two sets. Especial attention is given to the use of bit parallel in this condition. The implementation of the different structures in this work use an base interface and a base abstract class, where the operations are defined and the bit parallel is used. An experimental comparative between this structures is carry out using enumerative algorithms for the maximum stable set problem. Two approaches are used in the implementation of the enumerative algorithms for the maximum stable set problem, both using the bit parallel in the representation of the graph and on the operations with subsets of vertices. The first one is a known branch-and-bound algorithm and the second uses the Russian dolls method. In both cases, the use of bit parallel improve efficiency when the lower bounds are calculated based in a clique cover of the vertices. The results of computational experiments are presented as comparison between the two algorithms and as an assessment of the structures implemented. These results show that the algorithm based on the method Russian Dolls is more efficient regarding runtime and the memory consumed. Furthermore, the experimental results also show that the use stratification and hash tables also allow more efficiency in the case of sparse graphs. / A utilização de vetores de bits é prática corrente na representação de conjuntos por endereçamento direto com o intuito de reduzir o espaço de memória necessário e melhorar o desempenho de aplicações com uso de técnicas de paralelismo em bits. Nesta dissertação, examinamos implementações para representação de conjuntos por endereçamento direto. A estrutura básica nessas implementações é o vetor de bits. No entanto, além dessa estrutura básica, implementamos também duas variações. A primeira delas consiste em uma estratificação de vetores de bits, enquanto a segunda emprega uma tabela de dispersão. As operações associadas às estruturas implementadas são a inclusão ou remoção de um elemento do conjunto e a união ou interseção de dois conjuntos. Especial atenção é dada ao uso de paralelismo em bits nessas operações. As implementações das diferentes estruturas nesta dissertação utilizam uma interface e uma implementação abstrata comuns, nas quais as operações são especificadas e o paralelismo em bits é explorado. A diferença entre as implementações está apenas na estrutura utilizada. Uma comparação experimental é realizada entre as diferentes estruturas utilizando algoritmos enumerativos para o problema de conjunto independente máximo. Duas abordagens são utilizadas na implementação de algoritmos enumerativos para o problema de conjunto independente máximo, ambas explorando o potencial de paralelismo em bits na representação do grafo e na operação sobre subconjuntos de vértices. A primeira delas é um algoritmo do tipo {em branch-and-boound} proposto na literatura e a segunda emprega o método das bonecas russas. Em ambos os casos, o uso de paralelismo em bits proporciona ganhos de eficiência quando empregado no cálculo de limites inferiores baseados em cobertura por cliques. Resultados de experimentos computacionais são apresentados como forma de comparação entre os dois algoritmos e como forma de avaliação das estruturas implementadas. Esses resultados permitem concluir que o algoritmo baseado no método das bonecas russas é mais eficiente quanto ao tempo de execução e quanto ao consumo de memória. Além disso, os resultados experimentais mostram também que o uso de estratificação e tabelas de dispersão permitem ainda maior eficiência no caso de grafos com muito vértices e poucas arestas.

Este trabalho apresenta proposta de modelo matemático para o problema de expansão do sistema de transmissão baseado no fluxo de carga CC considerando a utilização de links CC e FACTS resolvido através de metodologia de solução que considera a primeira e a segunda lei de Kirchhoff em processo enumerativo de branch-and-bound adaptado. A abordagem possui dois pontos em destaque: i) apresenta uma proposta de modelo matemático com possibilidade da utilização direta em problemas de expansão de linhas de transmissão que possuem tanto linhas de transmissão CA, transformadores, links CC e dispositivos FACTS e ii) é um método exato de solução do problema que garante a otimalidade da resposta e traz uma contribuição ao tradicional método branch-and-bound por incluir relaxações adicionais. O método aplicado aos sistemas de 6 barras de Garver e sistema Sul sudeste Brasileiro de 46 barras apresenta respostas adequadas e o modelo matemático testado em um sistema Garver modificado apresenta novas configurações possíveis com redução do custo total do investimento. / This work proposes a mathematical model to the transmission expansion system problem based on the DC power flow model considering the use of DC links and FACTS that is solved using a solution method considering the first and second Kirchhoff’s Law in an enumerative adapted branch-and-bound process. It is possible to highlight two key aspects of the proposed approach: i) presents a mathematical model that can be directly used on expansion transmission systems problems that have AC transmission lines, transformers, DC links and FACTS and ii) is an exact solution method that guarantees the optimum problems’s solutions and contributes to the traditional branch-and-bound method bringing additional relaxations. The solution method applied to Garver’s six-bus network and southeast Brazilian 46 bus network provides correct answers and the mathematical model tested on a modified Garver’s six-bus network presents new possible configurations that enables overall cost reduction to the problem.

Este trabalho apresenta proposta de modelo matemático para o problema de expansão do sistema de transmissão baseado no fluxo de carga CC considerando a utilização de links CC e FACTS resolvido através de metodologia de solução que considera a primeira e a segunda lei de Kirchhoff em processo enumerativo de branch-and-bound adaptado. A abordagem possui dois pontos em destaque: i) apresenta uma proposta de modelo matemático com possibilidade da utilização direta em problemas de expansão de linhas de transmissão que possuem tanto linhas de transmissão CA, transformadores, links CC e dispositivos FACTS e ii) é um método exato de solução do problema que garante a otimalidade da resposta e traz uma contribuição ao tradicional método branch-and-bound por incluir relaxações adicionais. O método aplicado aos sistemas de 6 barras de Garver e sistema Sul sudeste Brasileiro de 46 barras apresenta respostas adequadas e o modelo matemático testado em um sistema Garver modificado apresenta novas configurações possíveis com redução do custo total do investimento. / This work proposes a mathematical model to the transmission expansion system problem based on the DC power flow model considering the use of DC links and FACTS that is solved using a solution method considering the first and second Kirchhoff’s Law in an enumerative adapted branch-and-bound process. It is possible to highlight two key aspects of the proposed approach: i) presents a mathematical model that can be directly used on expansion transmission systems problems that have AC transmission lines, transformers, DC links and FACTS and ii) is an exact solution method that guarantees the optimum problems’s solutions and contributes to the traditional branch-and-bound method bringing additional relaxations. The solution method applied to Garver’s six-bus network and southeast Brazilian 46 bus network provides correct answers and the mathematical model tested on a modified Garver’s six-bus network presents new possible configurations that enables overall cost reduction to the problem.

Submitted by Marlene Santos (marlene.bc.ufg@gmail.com) on 2016-06-09T18:00:24Z No. of bitstreams: 2 Dissertação - Rebeca Freitas Vasconcelos - 2014.pdf: 2286500 bytes, checksum: 175252a3e36474a01ded5d6943e2492f (MD5) license_rdf: 19874 bytes, checksum: 38cb62ef53e6f513db2fb7e337df6485 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2016-06-10T12:34:58Z (GMT) No. of bitstreams: 2 Dissertação - Rebeca Freitas Vasconcelos - 2014.pdf: 2286500 bytes, checksum: 175252a3e36474a01ded5d6943e2492f (MD5) license_rdf: 19874 bytes, checksum: 38cb62ef53e6f513db2fb7e337df6485 (MD5) / Made available in DSpace on 2016-06-10T12:34:58Z (GMT). No. of bitstreams: 2 Dissertação - Rebeca Freitas Vasconcelos - 2014.pdf: 2286500 bytes, checksum: 175252a3e36474a01ded5d6943e2492f (MD5) license_rdf: 19874 bytes, checksum: 38cb62ef53e6f513db2fb7e337df6485 (MD5) Previous issue date: 2014-08-26 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work presents the application of optimization techniques for the design of hollow core slabs and beams with precast and prestressed straight cable, considering the calculation of both the immediate losses as the time-dependent. For the slabs formulation allows the designer to obtain the optimal dimensions of the height of the panel, the diameters of the cables and the alveoli, and the number of cables. The beams are obtained beam height, diameter and the number of cables. Are still subject to the conditions of service for bending stresses, constructive limitations and failure conditions. Illustrative examples are presented using the Branch and Bound algorithm and Lingo (PLS), further comparison is made between the weight and the cost of the panel, and from the results of the algorithm and sizing Munte tables that follow Brazilian standards. We conclude that the optimal design has many advantages compared to conventional design, methods of discrete variation that best characterize the optimal variables of the problem, restrictions on the normal stresses ELS are crucial in obtaining the optimal dimensions of the structures and lower panels weight does not necessarily represent the lowest cost. / Este trabalho apresenta a aplicação de técnicas de otimização para o dimensionamento de lajes alveolares e vigas com cabo reto pré-moldadas e protendidas, considerando o cálculo tanto das perdas imediatas quanto das dependentes do tempo. Para as lajes, a formulação permite que o projetista obtenha as dimensões ótimas da altura do painel, dos diâmetros dos alvéolos e dos cabos, e do número de cabos. Nas vigas, são obtidas a altura da viga, o diâmetro e o número dos cabos. São, ainda, observadas as condições de serviço para esforços de flexão, limitações construtivas e condições de falha. Exemplos ilustrativos são apresentados usando o algoritmo de Branch and Bounde o Lingo(PLS). São feitos, ainda, comparativos entre o peso e o custo do painel e entre os resultados obtidos pelo algoritmo e tabelas de dimensionamento encontradas na literatura que seguem normas brasileiras. Conclui-se que o projeto ótimo apresenta inúmeras vantagens se comparado ao projeto convencional, que os métodos de variação discreta caracterizam melhor as variáveis ótimas do problema, que as restrições relativas às tensões normais do ELS são determinantes na obtenção das dimensões ótimas das estruturas e que painéis de menor peso não necessariamente representam o menor custo.

Die Tourenbildung beschäftigt sich mit der Konstruktion kostengünstiger Transportrouten zur Belieferung von Verbrauchern. Sie ist eine der weitreichensten Erfolgsgeschichten des Operations Research. Das starke Interesse an diesen Problemen durch Industrie und Forschung liegt zum einen am wirtschaftlichen Potenzial der Tourenbildung und -optimierung, zum anderen macht ihr Reichtum an Struktur sie zu einem faszinierenden Forschungsgebiet. In der vorliegenden Arbeit soll ein Überblick über einige, u. a. auch neuere mathematische Modell- und Lösungsansätze gegeben werden. Auf Grund der hohen Anzahl der Veröffentlichungen auf diesem Gebiet wird nicht zwingend ein Anspruch auf die vollständige Darlegung aller möglichen Problemstellungen im Zusammenhang mit dem TSP sowie dem VRP und deren Lösungsansätze erhoben. An den gegebenen Stellen wird statt dessen auf weiterführende Literatur verwiesen.

Dans ce travail, nous présentons trois nouveaux algorithmes pour le problème de la clique de poids maximum. Les trois algorithmes dépendent d'un ordre initial des sommets. Deux ordres sont considérés, l'un en fonction de la pondération des sommets et l'autre en fonction de la taille voisinage des sommets. Le premier algorithme, que nous avons appelé BITCLIQUE, est une algorithme de séparation et évaluation. Il réunit efficacement plusieurs idées déjà utilisées avec succès pour résoudre le problème, comme l'utilisation d'une heuristique de coloration pondérée en nombres entiers pour l'évaluation ; et l'utilisation de vecteurs de bits pour simplifier les opérations sur le graphe. L'algorithme proposé surpasse les algorithmes par séparation et évaluation de l'état de l'art sur la plupart des instances considérées en terme de nombre de sous-problèmes énumérés ainsi que en terme de temps d'exécution. La seconde version est un algorithme des poupées russes, BITRDS, qui intègre une stratégie d'évaluation et de ramification de noeuds basée sur la coloration pondérée. Les simulations montrent que BITRDS réduit à la fois le nombre de sous-problèmes traités et le temps d'exécution par rapport à l'algorithme de l'état de l'art basée sur les poupées russes sur les graphes aléatoires avec une densité supérieure à 50%. Cette différence augmente à la mesure que la densité du graphe augmente. D'ailleurs, BITRDS est compétitif avec BITCLIQUE avec une meilleure performance sur les instances de graphes aléatoires avec une densité comprise entre 50% et 80%. Enfin, nous présentons une coopération entre la méthode poupées russes et la méthode de ``Resolution Search''. L'algorithme proposé, appelé BITBR, utilise au même temps la coloration pondérée et les limites supérieures donnés par les poupées pour trouver un ``nogood''. L'algorithme hybride réduit le nombre d'appels aux heuristiques de coloration pondérée, atteignant jusqu'à 1 ordre de grandeur par rapport à BITRDS. Plusieurs simulations sont réalisées avec la algorithmes proposés et les algorithmes de l'état de l'art. Les résultats des simulations sont rapportés pour chaque algorithme en utilisant les principaux instances disponibles dans la littérature. Enfin, les orientations futures de la recherche sont discutées. / In this work, we present three new exact algorithms for the maximum weight clique problem. The three algorithms depend on an initial ordering of the vertices. Two ordering are considered, as a function of the weights of the vertices or the weights of the neighborhoods of the vertices. This leads to two versions of each algorithm. The first one, called BITCLIQUE, is a combinatorial Branch & Bound algorithm. It effectively combines adaptations of several ideas already successfully employed to solve the problem, such as the use of a weighted integer coloring heuristic for pruning and branching, and the use of bitmap for simplifying the operations on the graph. The proposed algorithm outperforms state-of-the-art Branch & Bound algorithms in most instances of the considered in terms of the number of enumerated subproblems as well in terms of computational time The second one is a Russian Dolls, called BITRDS, which incorporates the pruning and branching strategies based on weighted coloring. Computational tests show that BITRDS reduces both the number of enumerated subproblems and execution time when compared to the previous state-of-art Russian Dolls algorithm for the problem in random graph instances with density above 50%. As graph density increases, this difference increases. Besides, BITRDS is competitive with BITCLIQUE with better performance in random graph instances with density between 50% and 80%. Finally, we present a cooperation between the Russian Dolls method and the Resolution Search method. The proposed algorithm, called BITBR, uses both the weighted coloring and upper bounds given by the dolls to find a nogood. The hybrid algorithm reduces the number of coloring heuristic calls, reaching up to 1 order of magnitude when compared with BITRDS. However, this reduction decreases the execution time only in a few instances. Several computational experiments are carried out with the proposed and state-of-the-art algorithms. Computational results are reported for each algorithm using the main instances available in the literature. Finally, future directions of research are discussed.

No description available.