Engineering design may be viewed as a decision making process that supports design tradeoffs. The designer makes decisions based on information available and engineering judgment. The designer determines the direction in which the design must proceed, the procedures that need to be adopted, and develops a strategy to perform successive decisions. The design is only as good as the decisions made, which is in turn dependent on the information available. Information is time and process dependent. This thesis work focuses on developing a coherent bottom-up framework and methodology to improve information transfer and decision making while designing complex systems. The rotorcraft drive system is used as a test system for this methodology. The traditional serial design approach required the information from one discipline and/or process in order to proceed with the subsequent design phase. The Systems Engineering (SE) implementation of Concurrent Engineering (CE) and Integrated Product and Process Development (IPPD) processes tries to alleviate this problem by allowing design processes to be performed in parallel and collaboratively. The biggest challenge in implementing Concurrent Engineering is the availability of information when dealing with complex systems such as aerospace systems. The information is often incomplete, with large amounts of uncertainties around the requirements, constraints and system objectives. As complexity increases, the design process starts trending back towards a serial design approach. The gap in information can be overcome by either “softening” the requirements to be adaptable to variation in information or to delay the decision. Delayed decisions lead to expensive modifications and longer product design lifecycle. Digitization of IPPD tools for complex system enables the system to be more adaptable to changing requirements. Design can proceed with “soft” information and decisions adapted as information becomes available even at early stages. The advent of modern day computing has made digitization and automation possible and feasible in engineering. Automation has demonstrated superior capability in design cycle efficiency [1]. When a digitized framework is enhanced through automation, design can be made adaptable without the requirement for human interaction. This can increase productivity, and reduce design time and associated cost. An important aspect in making digitization feasible is having the availability of parameterized Computer Aided Design (CAD) geometry [2]. The CAD geometry gives the design a physical form that can interact with other disciplines and geometries. Central common CAD database allows other disciplines to access information and extract requirements; this feature is of immense importance while performing systems syntheses. Through database management using a Product Lifecycle Management (PLM) system, Integrated Product Teams (IPTs) can exchange information between disciplines and develop new designs more efficiently by collaborating more and from far [3]. This thesis focuses on the challenges associated with automation and digitization of design. Making more information available earlier goes jointly with making the design adaptable to new information. Using digitized sizing, synthesis, cost analysis and integration, the drive system design is brought in to early design. With modularity as the objective, information transfer is made streamlined through the use of a software integration suite. Using parametric CAD tools, a novel ‘Fully-Relational Design’ framework is developed where geometry and design are adaptable to related geometry and requirement changes. During conceptual and preliminary design stages, the airframe goes through many stages of modifications and refinement; these changes affect the sub-system requirements and its design optimum. A fully-relational design framework takes this into account to create interfaces between disciplines. A novel aspect of the fully-relational design methodology is to include geometry, spacing and volume requirements in the system design process. Enabling fully-relational design has certain challenges, requiring suitable optimization and analysis automation. Also it is important to ensure that the process does not get overly complicated. So the method is required to possess the capability to intelligently propagate change. There is a need for suitable optimization techniques to approach gear train type design problems, where the design variables are discrete in nature and the values a variables can assume is a result of cascading effects of other variables. A heuristic optimization method is developed to analyze this multimodal problem. Experiments are setup to study constraint dependencies, constraint-handling penalty methods, algorithm tuning factors and innovative techniques to improve the performance of the algorithm. Inclusion of higher fidelity analysis in early design is an important element of this research. Higher fidelity analyses such as nonlinear contact Finite Element Analysis (FEA) are useful in defining true implied stresses and developing rating modification factors. The use of Topology Optimization (TO) using Finite Element Methods (FEM) is proposed here to study excess material removal in the gear web region.

Darbo pradžioje supažindinsiu su gamybinių tvarkaraščių sudarymo uždaviniu. Jo tikslas rasti tvarkaraštį tam tikrai gamybinei situacijai. Uždavinys turi pilnai nusakyti kas ir kur turi įvykti ir apibrėžti visus apribojimus, o gautas sprendinys turi tenkinti šiuos reikalavimus ir vienareikšmiškai nusakyti operacijų vykdymą. Ši problema aktuali gamyklose, personalo valdyme, krovinių gabenime, oro uostuose, traukinių stotyse ir daugelyje kitų. Kadangi matematinis gamybinių tvarkaraščių sudarymo apibūdinimas sudaromas atsižvelgiant į realaus pasaulio problemas, egzistuoja daug šio uždavinio variantų. Dėl to teko pasirinkti kurį konkretų uždavinį nagrinėti. Pirmajame skyriuje supažindinu su šiuo konkrečiu uždaviniu, pateikiu apibrėžimus, s��vokas ir egzistuojančias problemas sprendžiant gamybinių tvarkaraščių uždavinį. Galiausiai parodysiu, kad tai yra sunkiai sprendžiamas ir dėl to vienas iš aktualių kombinatorinio optimizavimo uždavinių. Tuomet plačiau apibūdinu genetinį ir skruzdžių kolonijos optimizavimo algoritmus. Šie algoritmai ir naudojami sprendžiant mano konkret�� gamybinių tvarkaraščių sudarymo uždavinį. Aš apibūdinu visus parametrus ir koeficientus. Vėliau aš pristatau sukurtą programinę įrangą, skirtą rasti spręsti gamybinių tvarkaraščių sudarymo uždavinį ir vaizdžiai pateikti gautus sprendinius. Taip pat grafikų lentelių ir kitų priemonių pagalba pateikiu atliktų eksperimentų rezultatus. Tuomet apžvelgiu gautus rezultatus ir aptariu pastebėtas tendencijas ir... [toliau žr. visą tekstą] / At the begining of this work introduction to the scheduling problem and its basics is given. The goal of a scheduling problem is to make a schedule for a certain production situation. In the problem it is stated what must take place, and the solution describes exactly what should happen at what time. These problems occur in factories, personnel planning, transportation, airfields, railroad stations etcetera. Since mathematical descriptions of scheduling problems are often distilled from practical situations there are many variants of scheduling problems. A selection had to be made which problem is going to be a target of the study. The job shop scheduling problem was chosen. In the first chapter there is definitions of the problems we are trying to solve, introduction of important concepts (properties, bounds, definitions) from the field of scheduling. The last section takes a small detour into theoretical computer science in order to make precise that scheduling problems are hard to solve. In the second chapter introduction of genetic and ant colony optomization algorithms and its basius is given. It is used to solve scheduling problem, which was mentioned before. Introduction of all genetic and ant colony optimization algorithm operators and settings are given here. Then follows the introduction to software witch was made to solve and visualize solutions of scheduling problem. A great number of plots and figures are used in the experimental chapter to explain what... [to full text]

Darbo tikslas – sukurti bendrą prieigos tinklo modeliavimo metodiką bei jos programinę realizaciją, atitinkančią šiuos reikalavimus: • n užduotų prieigos tinklo parametrų reikšmių optimalus nustatymas pagal m užduotų prieigos tinklo kokybės apribojimų, kai n ≥ 1, o m ≥ 0; • optimalus stočių koordinačių nustatymas mobiliojo telefono ryšio tinklui; • optimalus stočių koordinačių nustatymas laidinio telefono ryšio tinklui; Darbo pradžioje apžvelgiamos telekomunikacijų sektoriaus užduotys, kurios gali būti sprendžiamos kombinatorinio optimizavimo metodais. Taipogi pristatomi ir suklasifikuojami galimi šių užduočių sprendimo metodai. Tiriamojoje darbo dalyje pristatomas daugiaparametrinis prieigos tinklo optimizavimo algoritmas integruotas su stočių išdėstymo algoritmais. Stočių išdėstymui pateikiami du meta-euristiniai algoritmai: • Skruzdžių kolonijos algoritmas, papildytas lokalios paieškos procedūra; • Genetinis algoritmas, papildytas lokalios paieškos procedūra. Minėtų algoritmų realizacijos skirstomos pagal šias prieigos tinklo ryšio topologijas: • Mobiliojo telefono ryšio tinklui; • Fiksuoto telefono ryšio tinklui. Esminiai darbe pasiekti rezultatai: • Sukurta universali metodika, leidžianti kurti realius prieigos tinklo modelius; • Sukurta šios metodikos programinė realizacija. Darbe nagrinėjamų uždavinių ir algoritmų pagrindu buvo paskelbti ir pristatyti šie straipsniai: • „Prieigos tinklo parametrų optimalaus... [toliau žr. visą tekstą] / The objective of this work is creation of telecommunication network approach algorithm and its realization. The created algorithm must fulfill following requirements: • optimal values evaluation of n given network approach parameters with m given network approach quality constrains, where n ≥ 1, o m ≥ 0; • optimal solution for transmitters placement problem in mobile phone network; • optimal solution for transmitters placement problem in fixed phone network; In the beginning of this paper we present a set of telecommunication segment problems which can be solved using combinatorial optimization methods. Also we present a set of combinatorial optimization methods which can be used for solving these problems. Finally we present a graphical classification of analyzed problems and connect it with algorithms which are capable for solving it. In the research part of this paper we present a multi parametric network approach optimization algorithm united with algorithms for placing transmitters. Next we present two Meta heuristics based optimization algorithms: • Ant Colony Optimization algorithm with local search procedure; • Genetic algorithm with local search procedure. The realization of these two algorithms depends on the topology of the network approach being analyzed. In this paper we analyze two most common types of network approaches: • Mobile phone network approach; • Fixed phone network approach. The two main achievements of... [to full text]

The advent of new technology enhance the speed and reduce the cost for sequencing biological data. Making biological sense of this genomic data is a big challenge to the algorithm design as well as the high performance computing society. There are many problems in Bioinformatics, such as how new functional genes arise, why genes are organized into chromosomes, how species are connected through the evolutionary tree of life, or why arrangements are subject to change. Phylogenetic analyses have become essential to research on the evolutionary tree of life. It can help us to track the history of species and the relationship between different genes or genomes through millions of years. One of the fundamentals for phylogenetic construction is the computation of distances between genomes. Since there are much more complicated combinatoric patterns in rearrangement events, the distance computation is still a hot topic as much belongs to mathematics as to biology. For the distance computation with input of two genomes containing unequal gene contents (with insertions/deletions and duplications) the problem is especially hard. In this thesis, we will discuss about our contributions to the distance estimation for unequal gene order data. The problem of finding the median of three genomes is the key process in building the most parsimonious phylogenetic trees from genome rearrangement data. For genomes with unequal contents, to the best of our knowledge, there is no algorithm that can help to find the median. In this thesis, we make our contributions to the median computation in two aspects. 1) Algorithm engineering aspect, we harness the power of streaming graph analytics methods to implement an exact DCJ median algorithm which run as fast as the heuristic algorithm and can help construct a better phylogenetic tree. 2) Algorithmic aspect, we theoretically formulate the problem of finding median with input of genomes having unequal gene content, which leads to the design and implementation of an efficient Lin-Kernighan heuristic based median algorithm. Inferring phylogenies (evolutionary history) of a set of given species is the ultimate goal when the distance and median model are chosen. For more than a decade, biologists and computer scientists have studied how to infer phylogenies by the measurement of genome rearrangement events using gene order data. While evolution is not an inherently parsimonious process, maximum parsimony (MP) phylogenetic analysis has been supported by widely applied to the phylogeny inference to study the evolutionary patterns of genome rearrangements. There are generally two problems with the MP phylogenetic arose by genome rearrangement: One is, given a set of modern genomes, how to compute the topologies of the according phylogenetic tree; Another is, given the topology of a model tree, how to infer the gene orders of the ancestor species. To assemble a MP phylogenetic tree constructor, there are multiple NP hard problems involved, unfortunately, they organized as one problem on top of other problems. Which means, to solve a NP hard problem, we need to solve multiple NP hard sub-problems. For phylogenetic tree construction with the input of unequal content genomes, there are three layers of NP hard problems. In this thesis, we will mainly discuss about our contributions to the design and implementation of the software package DCJUC (Phylogeny Inference using DCJ model to cope with Unequal Content Genomes), that can help to achieve both of these two goals. Aside from the biological problems, another issue we need to concern is about the use of the power of parallel computing to assist accelerating algorithms to handle huge data sets, such as the high resolution gene order data. For one thing, all of the method to tackle with phylogenetic problems are based on branch and bound algorithms, which are quite irregular and unfriendly to parallel computing. To parallelize these algorithms, we need to properly enhance the efficiency for localized memory access and load balance methods to make sure that each thread can put their potentials into full play. For the other, there is a revolution taking place in computing with the availability of commodity graphical processors such as Nvidia GPU and with many-core CPUs such as Cray-XMT, or Intel Xeon Phi Coprocessor with 60 cores. These architectures provide a new way for us to achieve high performance at much lower cost. However, code running on these machines are not so easily programmed, and scientific computing is hard to tune well on them. We try to explore the potentials of these architectures to help us accelerate branch and bound based phylogenetic algorithms.

Within the wide scope of logistics management,transportation plays a central role and is a crucialactivity in both production and service industry.Among others, it allows for the timely distributionof goods and services between suppliers, productionunits, warehouses, retailers, and final customers.More specifically, Vehicle Routing Problems(VRPs) deal with the design of a set of minimal costroutes that serve the demand for goods orservices of a set of geographically spread customers,satisfying a group of operational constraints.While it was traditionally a static problem, recenttechnological advances provide organizations withthe right tools to manage their vehicle fleet in realtime. Nonetheless, these new technologies alsointroduce more complexity in fleet managementtasks, unveiling the need for decision support systemsdedicated to dynamic vehicle routing. In thiscontext, the contributions of this Ph.D. thesis arethreefold : (i) it presents a comprehensive reviewof the literature on dynamic vehicle routing ; (ii)it introduces flexible optimization frameworks thatcan cope with a wide variety of dynamic vehiclerouting problems ; (iii) it defines a new vehicle routingproblem with numerous applications.

M.Sc. University of KwaZulu-Natal, Durban 2013.

The work presented in this PhD studies and proposes cellular computation parallel models able to address different types of NP-hard optimization problems defined in the Euclidean space, and their implementation on the Graphics Processing Unit (GPU) platform. The goal is to allow both dealing with large size problems and provide substantial acceleration factors by massive parallelism. The field of applications concerns vehicle embedded systems for stereovision as well as transportation problems in the plane, as vehicle routing problems. The main characteristic of the cellular model is that it decomposes the plane into an appropriate number of cellular units, each responsible of a constant part of the input data, and such that each cell corresponds to a single processing unit. Hence, the number of processing units and required memory are with linear increasing relationship to the optimization problem size, which makes the model able to deal with very large size problems.The effectiveness of the proposed cellular models has been tested on the GPU parallel platform on four applications. The first application is a stereo-matching problem. It concerns color stereovision. The problem input is a stereo image pair, and the output a disparity map that represents depths in the 3D scene. The goal is to implement and compare GPU/CPU winner-takes-all local dense stereo-matching methods dealing with CFA (color filter array) image pairs. The second application focuses on the possible GPU improvements able to reach near real-time stereo-matching computation. The third and fourth applications deal with a cellular GPU implementation of the self-organizing map neural network in the plane. The third application concerns structured mesh generation according to the disparity map to allow 3D surface compressed representation. Then, the fourth application is to address large size Euclidean traveling salesman problems (TSP) with up to 33708 cities.In all applications, GPU implementations allow substantial acceleration factors over CPU versions, as the problem size increases and for similar or higher quality results. The GPU speedup factor over CPU was of 20 times faster for the CFA image pairs, but GPU computation time is about 0.2s for a small image pair from Middlebury database. The near real-time stereovision algorithm takes about 0.017s for a small image pair, which is one of the fastest records in the Middlebury benchmark with moderate quality. The structured mesh generation is evaluated on Middlebury data set to gauge the GPU acceleration factor and quality obtained. The acceleration factor for the GPU parallel self-organizing map over the CPU version, on the largest TSP problem with 33708 cities, is of 30 times faster.

The tree-width and branch-width of a graph are two well-studied examples of parameters that measure how well a given graph can be decomposed into a tree structure. In this thesis we give several results and applications concerning these concepts, in particular if the graph is embedded on a surface. In the first part of this thesis we develop a geometric description of tangles in graphs embedded on a fixed surface (tangles are the obstructions for low branch-width), generalizing a result of Robertson and Seymour. We use this result to establish a relationship between the branch-width of an embedded graph and the carving-width of an associated graph, generalizing a result for the plane of Seymour and Thomas. We also discuss how these results relate to the polynomial-time algorithm to determine the branch-width of planar graphs of Seymour and Thomas, and explain why their method does not generalize to surfaces other than the sphere. We also prove a result concerning the class C_2k of minor-minimal graphs of branch-width 2k in the plane, for an integer k at least 2. We show that applying a certain construction to a class of graphs in the projective plane yields a subclass of C_2k, but also show that not all members of C_2k arise in this way if k is at least 3. The last part of the thesis is concerned with applications of graphs of bounded tree-width to the Traveling Salesman Problem (TSP). We first show how one can solve the separation problem for comb inequalities (with an arbitrary number of teeth) in linear time if the tree-width is bounded. In the second part, we modify an algorithm of Letchford et al. using tree-decompositions to obtain a practical method for separating a different class of TSP inequalities, called simple DP constraints, and study their effectiveness for solving TSP instances.

We study the facial structure of the independent set polytope using the concept of conflict hypergraphs. A conflict hypergraph is a hypergraph whose vertices correspond to the binary variables, and edges correspond to covers in the constraint matrix of the independent set polytope. Various structures such as cliques, odd holes, odd anti-holes, webs and anti-webs are identified on the conflict hypergraph. These hypergraph structures are shown to be generalization of traditional graph structures. Valid inequalities are derived from these hypergraph structures, and the facet defining conditions are studied. Chvatal-Gomory ranks are derived for odd hole and clique inequalities. To test the hypergraph cuts, we conduct computational experiments on market-share (also referred to as market-split) problems. These instances consist of 100% dense multiple-knapsack constraints. They are small in size but are extremely hard to solve by traditional means. Their difficult nature is attributed mainly to the dense and symmetrical structure. We employ a special branching strategy in combination with the hypergraph inequalities to solve many of the particularly difficult instances. Results are reported for serial as well as parallel implementations.

CNPq / A Transgenética Computacional é uma metáfora para o desenvolvimento de algoritmos evolucionários com base na teoria de evolução endossimbiótica e em outras interações do fluxo intracelular. Diversos algoritmos foram desenvolvidos com base nesta metáfora para problemas de Otimização Combinatória, em sua maioria com um único objetivo, obtendo bons resultados. Uma vez que a consideração de mais de um objetivo leva, em geral, a representações mais realistas de problemas práticos complexos, neste trabalho investiga-se o desenvolvimento de Algoritmos Transgenéticos para problemas multiobjetivo. Tais algoritmos são examinados em versões que utilizam elementos de outros algoritmos evolucionários multiobjetivo sendo eles o NSGA-II (Non-Dominated Sorting Genetic Algorithm-II) e o MOEA/D (Multi-objective Evolutionary Algorithm based on Decomposition). Diante disso, este trabalho propõe duas novas metodologias utilizando a Transgenética Computacional acoplada ao NSGA-II e ao MOEA/D, denominadas NSTA (Non-Dominated Sorting Transgenetic Algorithm) e MOTA/D (Multi-objective Transgenetic Algorithm based on Decomposition), respectivamente. Para avaliar o desempenho das técnicas propostas, os algoritmos desenvolvidos foram aplicados a dois problemas de Otimização Combinatória, NP-difíceis,em versões com mais de um objetivo. O primeiro problema é o Caixeiro Comprador Biobjetivo e o segundo o Quadrático de Alocação multiobjetivo. Foram realizados experimentos com casos de teste disponíveis em bancos utilizados comumente por outros trabalhos da literatura. Os resultados dos algoritmos propostos foram comparados com os resultados obtidos com os algoritmos evolucionários multiobjetivo que os inspiraram. A análise dos dados obtidos com os experimentos computacionais mostram que a versão MOTA/D é a mais eficiente dentre os algoritmos do experimento com relação a qualidade da aproximação da fronteira de Pareto. / The Computational Transgenetic is a metaphor for the development of evolutionary algorithms based on the theory of evolution endosymbiotic and other intracellular interactions flow. Several algorithms have been developed based on this metaphor for combinatorial optimization problems, mostly with a single objective, obtaining good results. Once the account of more than one objective provides, in general, more realistic representations of complex practical problems, this work investigates the development of Transgenetic Algorithms for multiobjective problems. Such algorithms are examined in versions that use elements of other multiobjective evolutionary algorithms such as the NSGA-II (Non-Dominated Sorting Genetic Algorithm-II) and the MOEA/D (Multi-objective Evolutionary Algorithm based on Decomposition). Therefore, this work proposes two new methods using Computational Transgenetic attached to NSGA-II and MOEA/D, named NSTA (Non-Dominated Sorting Transgenetic Algorithm) and MOTA/D (Multi-objective Transgenetic Algorithm based on Decomposition), respectively. To evaluate the proposed techniques performance, the experiments consider two NP-hard combinatorial optimization problems, in versions with more than one objective. The first problem is the Traveling Purchaser Problem and the second the Quadratic Assignment Problem. Experiments were performed with test cases available in benchmarks commonly used by other studies in the literature. The proposed algorithms' results were compared with those obtained by the multiobjetive evolutionary algorithms that inspired them. The analysis of data obtained by the computational experiment shows that the version MOTA/D is among the most efficient algorithms of the experiment with respect to the quality of the Pareto front approximation.