Gescannte und vektorisierte technische Zeichnungen werden automatisch unter Nutzung eines Netzes von Modellen in eine hochwertige Datenstruktur migriert. Die Modelle beschreiben die Inhalte der Zeichnungen hierarchisch und deklarativ. Modelle für einzelne Bestandteile der Zeichnungen können paarweise unabhängig entwickelt werden. Dadurch werden auch sehr komplexe Zeichnungsklassen wie Elektroleitungsnetze oder Gebäudepläne zugänglich. Die Modelle verwendet der neue, sogenannte Y-Algorithmus: Hypothesen über die Deutung lokaler Zeichnungsinhalte werden hierarchisch generiert. Treten bei der Nutzung konkurrierender Modelle Konflikte auf, werden diese protokolliert. Mittels des Konfliktbegriffes können konsistente Interpretationen einer kompletten Zeichnung abstrakt definiert und während der Analyse einer konkreten Zeichnung bestimmt werden. Ein wahrscheinlichkeitsbasiertes Gütemaß bewertet jede dieser alternativen, globalen Interpretationen. Das Suchen einer bzgl. dieses Maßes optimalen Interpretation ist ein NP-hartes Problem. Ein Branch and Bound-Algorithmus stellt die adäquate Lösung dar.

The double hypernuclear systems are studied within the context of the hyperspherical approach. Possible bound states of these systems are sought as zeros of the corresponding three-body Jost function in the complex energy plane. Hypercentral potentials for the system are constructed from known potentials in order to determine bound states of the system. Calculated binding energies for double- hypernuclei having A = 4 − 20, are presented. / Physics / M.Sc. (Physics)

Depuis une vingtaine d’années, la résolution de problèmes d’optimisation globale non convexes avec contraintes a connu un formidable essor. Les algorithmes de branch and bound basée sur l’analyse d’intervalles ont su trouver leur place, car ils ont l’avantage de prouver l’optimalité de la solution de façon déterministe, avec un niveau de certitude pouvant aller jusqu’à la précision machine. Cependant, la complexité exponentielle en temps et en mémoire de ces algorithmes induit une limite intrinsèque, c’est pourquoi il est toujours nécessaire d’améliorer les techniques actuelles. Dans cette thèse, nous avons développé de nouvelles arithmétiques basées sur l’arithmétique d’intervalles et l’arithmétique affine, afin de calculer des minorants et des majorants de meilleure qualité de fonctions explicites sur un intervalle. Nous avons ensuite développé une nouvelle méthode automatique de construction de relaxations linéaires. Cette construction est basée sur l’arithmétique affine et procède par surcharge des opérateurs. Les programmes linéaires ainsi générés ont exactement le même nombre de variables et de contraintes d’inégalité que les problèmes originaux, les contraintes d’égalité étant remplacées par deux inégalités. Cette nouvelle procédure permet de calculer des minorants fiables et des certificats d’infaisabilité pour chaque sous-domaine à chaque itération de notre algorithme de branch and bound par intervalles. De nombreux tests numériques issus du site COCONUT viennent confirmer l’efficacité de cette approche. Un autre aspect de cette thèse a été l’étude d’une extension de ce type d’algorithmes en introduisant une limite sur mémoire disponible. L’idée principale de cette approche est de proposer un processus inverse de l’optimisation par le biais d’un principe métaheuristique : plutôt que d’améliorer des solutions locales à l’aide de métaheuristiques telles que les algorithmes Taboo ou VNS, nous partons d’une méthode exacte et nous la modifions en une heuristique. De cette façon, la qualité de la solution trouvée peut être évaluée. Une étude de la complexité de ce principe métaheuristique a également été effectuée. Enfin, pour finir l’étude, nous avons appliqué notre algorithme à la résolution de problème en géométrie plane, ainsi qu’à la résolution d’un problème de dimensionnement de moteur électrique. Les résultats obtenus ont permis de confirmer l’intérêt de ce type d’algorithme, en résolvant des problèmes ouverts sur les polygones convexes et proposant des structures innovantes en génie électrique. / Since about thirty years, interval Branch and Bound algorithms are increasingly used to solve constrained global optimization problems in a deterministic way. Such algorithms are reliable, i.e., they provide an optimal solution and its value with guaranteed bounds on the error, or a proof that the problem under study is infeasible. Other approaches to global optimization, while useful and often less time-consuming than interval methods, do not provide such a guarantee. However, the exponential complexity in time and memory of interval Branch and Bound algorithms implies a limitation, so it is always necessary to improve these methods. In this thesis, we have developed new arithmetics based on interval arithmetic and affine arithmetic, to compute better lower and upper bounds of a factorable function over an interval. An automatic method for constructing linear relaxations of constrained global optimization problems is proposed. Such a construction is based on affine and interval arithmetics and uses operator overloading. These linear programs have exactly the same numbers of variables and of inequality constraints as the given problems. Each equality constraint is replaced by two inequalities. This new procedure for computing reliable bounds and certificates of infeasibility is inserted into a classical interval Branch and Bound algorithm. Extensive computation experiments, made on a sample of test problems from the COCONUT database, prove its effectiveness. Another aspect is the study of an extension of such a global optimization code by limiting the available memory. The main idea of this new kind of metaheuristique is to propose a reverse process of optimization via heuristics : rather than improving local solutions by using metaheuristics such as Taboo or VNS, we begin with an exact method and we modify it into a heuristic one. In such a way, the quality of the solution could be evaluated. Moreover, a study of the complexity of this metaheurisque has been done. Finally, we applied our algorithm to solve open problem in geometry, and to solve a design problem of an electric motor. The results have confirmed the usefulness of this kind of algorithms, solving open problems on convex polygons and offering innovative structures in electrical engineering.

Em um contexto industrial, a programação da produção tem como objetivo alocar recursos para operações de forma a aumentar a eficiência operacional do processo de fabricação. Esta programação pode ser modelada na forma de problemas de sequenciamento de tarefas, que são resolvidos visando minimizar um determinado critério de desempenho. A aplicação de métodos exatos nestes problemas possibilita encontrar a solução ótima, tanto para aplicação direta como para a validação de métodos heurísticos e metaheurísticas. Entretanto, a literatura mostra que os métodos exatos, tanto a resolução do problema pela modelagem em programação linear-inteira mista como o branch-and-bound, têm sua aplicação restrita à problemas de menores tamanhos. O objetivo deste trabalho é propor novas formulações de limitantes inferiores para a aplicação do branch-and-bound em problemas de flowshop permutacional visando aumentar sua eficiência e aplicabilidade. Os limitantes propostos são avaliados em problemas de flowshop permutacional com tempos de setup dependente da sequência, tendo como critérios de desempenho o tempo de fluxo total e o atraso total. A avaliação da aplicabilidade de cada limitante é feita através do número de nós explorados e o tempo computacional gasto pelo branch-and-bound para resolver problemas de diversos tamanhos. / In an industrial context, production sequencing aims at allocating resources for job processing while increasing manufacturing efficiency. This task can be modelled in the form of scheduling problems, which are solved by minimizing a pre-determined performance criterion. The use of exact methods allows the optimal solution to be found, which can be applied directly in the manufacturing shop or used to validate heuristic and metaheuristic methods. However, the literature shows that MILP and branch-and-bound, both exact methods, are restrained to small-sized scheduling problems. The aim of this project is to propose new lower bound formulations to be used in the branch-and-bound method for permutational flowshop probems, in order to extend its efficiency and applicability. The proposed bounds are tested in permutational flowshop problems with sequence dependent setup times, and using as performance criteria the total flow time and the total tardiness. The evaluation of each lower bounds applicability is done considering the number of explored nodes and the required computational time for the branch-and-bound to solve problem instances of different sizes.

Cette thèse représente une étude d'un nouvel indicateur d'aide à la décision pour le problème d'ordonnancement d'ateliers de production sous présence d'incertitudes. Les contributions apportées dans ce travail se situent dans le contexte des groupes d'opérations permutables. Cette approche consiste à proposer une solution d'ordonnancement flexible caractérisant un ensemble fini non-énuméré d'ordonnancements. Un opérateur est ensuite censé sélectionner l'ordonnancement qui répond le mieux aux perturbations survenues dans l'atelier. Nous nous intéressons plus particulièrement à cette phase de sélection et nous mettons l'accent sur l’intérêt de l'humain pour la prise de décision. Dans un premier temps, nous présentons le meilleur des cas; indicateur d'aide à la décision pour le calcul du meilleur ordonnancement caractérisé par l'ordonnancement de groupes. Nous proposons des bornes inférieures pour le calcul des dates de début/fin des opérations. Ces bornes sont ensuite implémentées dans une méthode de séparation et d'évaluation permettant le calculer du meilleur des cas. Grâce à des simulations effectuées sur des instances de job shop de la littérature, nous mettons l'accent sur l'utilité et la performance d'un tel indicateur dans un système d'aide à la décision. Enfin, nous proposons une Interface Homme-Machine (IHM) adaptée à l'ordonnancement de groupes et pilotée par un système d'aide à la décision multicritères. L'implémentation de cette IHM sur un cas d'étude réel a permis de soulever certaines pratiques efficaces pour l'aide à la décision dans le contexte de l'ordonnancement sous incertitudes. / This thesis represents a study of a new decision-aid criterion for manufacturing scheduling under uncertainties. The contributions made in this work relate to the groups of permutable operations context. This approach consists of proposing a flexible scheduling solution characterizing a non-enumerated and finite set of schedules. An operator is then supposed to select the appropriate schedule that best copes with the disturbances occurred on the shop floor. We focus particularly on this selection phase and we emphasize the important of the human for decision making. First, we present the best-case; a decision-aid criterion for computing the best schedule characterized by the groups of permutable operations method. We propose lower bounds for computing the best starting/completion time of operations. These lower bounds are then implemented in a branch and bound procedure in order to compute the best-case. Through to several simulations carried out on literature benchmark instances, we stress the usefulness of such criterion in a decision-aid system. Finally, we propose a Human-Machine-Interface (HMI) adapted to the groups of permutable operations and driven by a multi-criteria decision-aid system. The implementation results of this HMI on a real case study provided some insight about the practice of decision-making and scheduling under uncertainties.

To date the majority of research in the area of cooperative communications focuses on maximizing throughput and reliability while assuming perfect channel state information (CSI) and synchronization. This thesis, seeks to address performance enhancement and system parameter estimation in cooperative networks while relaxing these idealized assumptions. In Chapter 3 the thesis mainly focuses on training-based channel estimation in multi-relay cooperative networks. Channel estimators that are capable of determining the overall channel gains from source to destination antennas are derived. Next, a new low feedback and low complexity scheme is proposed that allows for the coherent combining of signals from multiple relays. Numerical and simulation results show that the combination of the proposed channel estimators and optimization algorithm result in significant performance gains. As communication systems are greatly affected by synchronization parameters, in Chapter 4 the thesis quantitatively analyzes the effects of timing and frequency offset on the performance of communications systems. The modified Cramer-Rao lower bound (MCRLB) undergoing functional transformation, is derived and applied to determine lower bounds on the estimation of signal pulse amplitude and signal-to-noise ratio (SNR) due to timing offset and frequency offset, respectively. In addition, it is shown that estimation of timing and frequency offset can be decoupled in most practical settings. The distributed nature of cooperative relay networks may result in multiple timing and frequency offsets. Chapters 5 and 6 address multiple timing and frequency offset estimation using periodically inserted training sequences in cooperative networks with maximum frequency reuse, i.e., space-division multiple access (SDMA) networks. New closed-form expressions for the Cramer-Rao lower bound (CRLB) for multiple timing and multiple frequency offset estimation for different cooperative protocols are derived. The CRLBs are then applied in a novel way to formulate training sequence design guidelines and determine the effect of network protocol and topology on synchronization parameter estimation. Next, computationally efficient estimators are proposed. Numerical results show that the proposed estimators outperform existing algorithms and reach or approach the CRLB at mid-to-high SNR. When applied to system compensation, simulation results show that application of the proposed estimators allow for synchronized cooperation amongst the nodes within the network. / Thesis (Ph.D, Electrical & Computer Engineering) -- Queen's University, 2010-07-29 16:52:50.272

The current scenario of the Brazilian electricity sector, through the constant and recent regulatory changes imposed by ANEEL in recent years, aims to ensure continuous improvement in quality standards in the provision of electricity, significantly increased surveillance on the power quality delivered to consumers. Following this guideline, ANEEL established X Factor, which set the minimum volume of investments required to electricity distribution companies. In 2010, through the PRORET ANEEL established a new methodology for the calculation of the X Factor, including the Q component, relating to quality of service, setting a milestone in the recent regulatory history of the Brazilian electricity sector, as it allows for the first time gains the annual tariff adjustment or loss according to the performance measured in the year. In this context of regulatory innovations and increasing demands with performance standards and levels of investment made on the electrical system, the correct and efficient use of increasingly scarce resources to improve and expand the electrical system are presented as a vital challenge to financial health of companies. This paper presents a methodology for prioritizing investments in primary networks of electricity distribution, involving two consolidated methodologies aid to decision-making high complexity (AHP and PROMETHEE) and operations research methods to optimize the planning of improvement works to be held in short-term horizon, with direct reflection on regulatory issues, seeking still accommodate regional characteristics of the company and the ability to execute works of each region. / O atual cenário do setor elétrico brasileiro, através das constantes e recentes alterações regulatórias impostas pela ANEEL nos últimos anos, tem como objetivo garantir a melhoria contínua nos padrões de qualidade no fornecimento de energia elétrica, aumentado significativamente a fiscalização sobre a qualidade da energia entregue aos consumidores. Seguindo esta diretriz, a ANEEL instituiu o Fator X, que define o volume de investimentos mínimos exigidos às empresas de distribuição de energia elétrica. Em 2010, através do PRORET a ANEEL estabeleceu uma nova metodologia para o cálculo do Fator X, incluindo o componente Q, referente à qualidade do serviço prestado, configurando como um marco no recente histórico regulatório do setor elétrico brasileiro, pois permite pela primeira vez ganhos no reajuste tarifário anual ou perdas de acordo com o desempenho medido no ano. Neste contexto de inovações regulatórias e exigências cada vez maiores com os padrões de desempenho e níveis de investimentos realizados no sistema elétrico, a aplicação correta e eficiente dos cada vez mais escassos recursos disponíveis para melhoria e ampliação do sistema elétrico se apresentam como um desafio vital à saúde financeira das empresas do setor elétrico. Este trabalho apresenta uma metodologia para priorização de investimentos em redes primárias de distribuição de energia elétrica, associando duas consolidadas metodologias de auxílio à tomada de decisões de elevada complexidade (AHP e PROMETHEE) e métodos de pesquisa operacional para otimização no planejamento de obras de melhoria a serem realizadas no horizonte de curto prazo, com reflexo direto nas questões regulatórias, buscando ainda contemplar características regionais da empresa e a capacidade de execução de obras de cada região.

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.

Submitted by Lara Oliveira (lara@ufersa.edu.br) on 2018-03-15T21:26:01Z No. of bitstreams: 1 JonathanLS_DISSERT.pdf: 6143092 bytes, checksum: 68ad13bf204320bdcea5907ddb8d2102 (MD5) / Approved for entry into archive by Vanessa Christiane (referencia@ufersa.edu.br) on 2018-06-18T16:59:44Z (GMT) No. of bitstreams: 1 JonathanLS_DISSERT.pdf: 6143092 bytes, checksum: 68ad13bf204320bdcea5907ddb8d2102 (MD5) / Approved for entry into archive by Vanessa Christiane (referencia@ufersa.edu.br) on 2018-06-18T16:59:51Z (GMT) No. of bitstreams: 1 JonathanLS_DISSERT.pdf: 6143092 bytes, checksum: 68ad13bf204320bdcea5907ddb8d2102 (MD5) / Made available in DSpace on 2018-06-18T16:59:58Z (GMT). No. of bitstreams: 1 JonathanLS_DISSERT.pdf: 6143092 bytes, checksum: 68ad13bf204320bdcea5907ddb8d2102 (MD5) Previous issue date: 2017-08-23 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / 2018-03-15 / Os problemas de corte de materiais são recorrentes no cotidiano da indústria, sendo encontrados nas mais diferentes formas.Oproblema de corte bidimensional guilhotinado é uma dessas formas. Ele surge pelas restrições da ferramenta de corte, tipicamente a guilhotina. Este trabalho apresenta três abordagens para solucionar o problema em questão: uma abordagem matemática, uma abordagem exata computacional e uma abordagem heurística. A abordagem matemática consiste em um modelo de programação linear baseado em listas de itens e montagem do arranjo de corte partindo dos itens, unindo-os dois a dois, tentando maximizar o número de uniões sem ultrapassar as dimensões da placa. A abordagem exata computacional tratá-se de um algoritmo Branch-and-Bound modificado para permitir que estados mais promissores possam ser analisados antes, comportando-se como um algoritmo de busca em profundidade com uma pequena etapa em largura, na qual ordena os filhos na árvore de decisão pelo desperdício gerado. Por fim, a abordagem heurística é composta das metaheurísticas GRASP, Busca Tabu, Algoritmo Genético, BRKGA e Religação de Caminhos combinados com uma heurística de montagem baseada nos algoritmos propostos por Nascimento, Longo e Aloise (1999). Essas metaheurísticas foram combinadas em um time assíncrono para alcançar melhores resultados que os já encontrados na literatura. Além de melhorar os resultados conhecidos, a pesquisa também tinha como objetivo apresentar um modelo viável, em número de variáveis, e resultados ótimos para instâncias comumente utilizadas para o problema supracitado e novas opções de obtê-los em instâncias que venham a surgir no futuro. Testes mostraram a competividade dos algoritmos propostos frente aos melhores resultados encontrados, reduzindo inclusive o número total de placas, bem como a capacidade dos métodos exatos propostos de encontrar as soluções ótimas para as instâncias testadas. Cerca de de 25% dos resultados ótimos foram encontrados, passando esse número para 75%, quando considerados os resultados dos algoritmos metaheurísticos que atingiram o limite inferior das instâncias

The double hypernuclear systems are studied within the context of the hyperspherical approach. Possible bound states of these systems are sought as zeros of the corresponding three-body Jost function in the complex energy plane. Hypercentral potentials for the system are constructed from known potentials in order to determine bound states of the system. Calculated binding energies for double- hypernuclei having A = 4 − 20, are presented. / Physics / M.Sc. (Physics)