Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Diallel are important to predict the best combinations between different heterotic groups of maize inbred lines, as well as knowledge of the associations between traits. The aim of this study is to estimate the combining ability among inbred lines by partial diallel analysis for identification of gene action involved in the expression of traits and prediction and identification of the best combinations of direct and indirect relations between genetic and phenotypic morphological traits on yield components . The strains used in partial diallel cross of the two heterotic groups are from the company KSP Seeds Ltda.. The tests were conducted based on crosses with partial diallel mating scheme, using 15 strains as the female parent and eight strains as male parent. The tests were conducted in five environments, in randomized complete block design with three replications. The variables analyzed were: stem diameter (DC), leaf angle (AF), tassel length (CP), distance from the last node of the stem to the first branch of the tassel (DUN), distance from the flag leaf to the first branch tassel (CFB), number of primary branches on the main stem of the tassel (NR), number of secondary branches in the tassel (NRS), leaf area (AFT), thousand grain weight (MMG) and grain yield. Group I estimates of lineages 15 and 4, 3 and 4 group II are favorable grain yield by CGC. The traits tassel length, distance from the last node of the flag leaf and the first branch of the tassel, the best combinations for CPB are 1-3 , 2-4 , 3-3 , 4-4 , 7-3 , 8-3 , 9-3 , 10-3 , 10-4 , 11-4 , 12-4 , 14-3 and 15-4 . The junctions promising for increased yield are 1-1 , 1-4 , 2-3 , 3-1 , 3-4 , 4-3 , 4-6 , 4- 7 , 5-3 , 5-4 , 6-3 , 6-4 , 7-4 , 8-4 , 9-4 , 10-5 , 11-3 , 12-3 , 14-4 , 15-2 , 15-5 and 15-8 . Among the most promising crosses for CEC at least two parents have high CGC. The distance from the last node to the first branch of the tassel, length and number of tassel branches negatively affect the yield estimates for linear phenotypic and genotypic methods. The distance from the last node to the first branch of the tassel negatively influences the performance and should be considered in the criteria for strain selection. Selections for smaller leaf angle and greater stem diameter and mass of a thousand grains appear to be favorable for the increase of grain yield in maize. / Cruzamentos dialélicos são importantes para predição das melhores combinações heteróticas entre diferentes grupos de linhagens de milho, assim como o conhecimento das associações entre caracteres. O objetivo deste trabalho é estimar a capacidade combinatória entre linhagens endogâmicas de milho pela análise dialélica parcial para identificação das ações gênicas envolvidas na expressão de caracteres e predição das melhores combinações e identificação das relações diretas e indiretas fenotípicas e genéticas de caracteres morfológicos sobre componentes do rendimento. As linhagens utilizadas no cruzamento dialélico parcial dos dois grupos heteróticos são provenientes da empresa KSP Sementes Ltda. Os ensaios foram conduzidos baseados em cruzamentos com esquema de dialelo parcial, utilizando-se 15 linhagens como genitores femininos e oito linhagens como genitores masculinos. Os ensaios foram conduzidos em cinco ambientes, em delineamento de blocos completos ao acaso com três repetições. As variáveis analisadas foram: diâmetro do colmo (DC), ângulo de folha (AF), comprimento do pendão (CP), distância do último nó do colmo até a primeira ramificação do pendão (DUN), distância da folha bandeira a primeira ramificação do pendão (CFB), número de ramificações primárias na haste principal do pendão (NR), número de ramificações secundárias no pendão (NRS), área foliar (AFT), massa de mil grãos (MMG) e rendimento de grãos. No grupo I as estimativas das linhagens 15 e 4 e grupo II 3 e 4 são favoráveis para o rendimento de grãos pela CGC. Os caracteres comprimento de pendão, distância do último nó e da folha bandeira a primeira ramificação do pendão as melhores combinações pela CEC são 1-3 , 2-4 , 3-3 , 4-4 , 7-3 , 8-3 , 9-3 , 10-3 , 10-4 , 11-4 , 12-4 , 14-3 e 15-4 . Os cruzamentos promissores para aumento do rendimento são 1-1 , 1-4 , 2-3 , 3-1 , 3-4 , 4-3 , 4-6 , 4-7 , 5-3 , 5-4 , 6-3 , 6-4 , 7-4 , 8-4 , 9-4 , 10-5 , 11-3 , 12-3 , 14-4 , 15-2 , 15-5 e 15-8 . Entre os cruzamentos mais promissores para CEC pelo menos dois genitores possuem elevada CGC. As distâncias do último nó até primeira ramificação do pendão comprimento e número de ramificações do pendão afetam negativamente o rendimento para as estimativas lineares fenotípicas e genotípicas. A distância do último nó até a primeira ramificação do pendão influencia negativamente o rendimento, devendo ser considerado nos critérios de seleção de linhagens. As seleções para menor ângulo de folha e maior diâmetro de colmo e massa de mil grãos mostram-se favoráveis para o aumento de rendimento de grãos em milho.

[pt] Nas redes de fibras óticas, as informações são transmitidas na forma de um sinal luminoso através de uma fibra ótica. A tecnologia de multiplexação WDM permite a transmissão simultânea de vários sinais em um mesmo enlace. As conexões entre estações terminais são estabelecidas na forma de caminhos óticos, que são definidos em função de sua rota e do comprimento de onda no qual são multiplexados. Conversores de comprimentos de onda não são considerados neste trabalho. Conseqüentemente, os caminhos óticos devem permanecer com o mesmo comprimento de onda em todos os enlaces do transmissor ao receptor. O Problema de Roteamento e Atribuição Mínima de Comprimentos de Onda (min- RWA) consiste em estabelecer um conjunto de conexões entre pares de estações e atribuir um determinado comprimento de onda para cada uma delas, de forma que caminhos óticos que compartilhem algum enlace da rede tenham comprimentos de onda diferentes e que o número total de comprimentos de onda utilizados seja mínimo. Neste trabalho, uma nova heurística é proposta para min-RWA, onde k possíveis rotas são calculadas para cada conexão e, em seguida, uma rota (dentre as rotas pré-calculadas) e um comprimento de onda são atribuídos a cada conexão resolvendo-se um Problema de Coloração de Partições (PCP). O PCP é um problema de coloração em grafos particionados, ou seja, grafos onde os vértices estão particionados em subconjuntos disjuntos. O PCP consiste em selecionar e colorir um único vértice de cada subconjunto, de modo que dois vértices adjacentes, no grafo induzido pelos vértices selecionados tenham cores diferentes e que o número total de cores utilizadas seja mínimo. Nesta dissertação, são apresentadas e propostas novas heurísticas para PCP e min-RWA. Estas heurísticas são comparadas com as melhores conhecidas na literatura. / [en] In optical networks, the information is transmitted along the optical fibers as optical signals. Wavelength Division Multiplexing (WDM) allows more efficient use of the huge capacity of optical fibers, as far as it permits the simultaneous transmission of different channels along the same fiber, each of them using a different wavelength. The connections are established by lightpaths, in which the signal is converted to the optical domain and reaches the receptor without conversion to the electrical domain. A lightpath is defined by a route and a wavelength. We assume that wavelength conversion along a lightpath is not permitted, since this technology is not yet fully available. Therefore, each lightpath should use the same wavelength from the transmitter to the receiver. The Routing and Wavelength Assignment problem consists in routing a set of lightpaths and assigning a wavelength to each of them. All connection requirements are known beforehand and one seeks to minimize the total number of wavelengths used for routing these connections, so as that two lightpaths sharing a common link use different wavelengths. In this work, we propose a new heuristic in which min-RWA is solved by a combined approach involving the computation of alternative routes for the lightpaths, followed by the solution of a Parttion Coloring Problem (PCP). Given a graph where the vertex set is partitioned in disjoint susets, PCP consists in selecting and coloring only one vertex in each subset, so as that every two adjacent colored nodes have different colors and the total number of colors used is minimum. We present and propose new heuristics for PCP and min-RWA. Computational experiments are reported comparing the new heuristics and those which already appeared in the literature.

La classe des graphes sans P5, c'est-à-dire des graphes ne contenant pas de chaîne induite à cinq sommets, est d'un intérêt particulier en théorie des graphes. Il s'agit en effet de la plus petite classe définie par un seul sous-graphe connexe interdit pour laquelle on ignore encore s'il existe un algorithme polynomial permettant de résoudre le problème du stable maximum. Or ce problème, dont on sait qu'il est difficile en général, est d'une grande importance en pratique (problèmes de planification, d'allocation de registres dans un processeur, biologie moléculaire...). Dans cette thèse, nous commençons par dresser un état de l'art complet des méthodes utilisées pour résoudre le problème dans des sous-classes de graphes sans P5, puis nous étudions et résolvons ce problème dans une sous-classe particulière, la classe des graphes sans P5 3-colorables. Nous apportons également des solutions aux problèmes de la reconnaissance et de la coloration de ces graphes, chaque fois en temps linéaire. Enfin, nous définissons, caractérisons et sommes capables de reconnaître les graphes "chain-probe", qui sont les graphes auxquels il est possible de rajouter des arêtes entre certains sommets de sorte qu'ils soient bipartis et sans P5. Les problèmes de ce type proviennent de la génétique et ont également des applications en intelligence artificielle. / The class of P5-free graphs, namely the graphs without induced chains with five vertices, is of particular interest in graph theory. Indeed, it is the smallest class defined by only one forbidden connected induced subgraph for which the complexity of the Maximum Independent Set problem is unknown. This problem has many applications in planning, CPU register allocation, molecular biology... In this thesis, we first give a complete state of art of the methods used to solve the problem in P5-free graphs subclasses; then we study and solve this problem in a particular subclass, the class of 3-colorable P5-free graphs. We also bring solutions to recognition and coloring problems of these graphs, each time in linear time. Finally, we define, characterize, and are able to recognize "chain-probe" graphs, namely the graphs for which we can add edges between particular vertices such that the resulting graph is bipartite and P5-free. Problems of this type come from genetics and have application in I.A.

Durant longtemps la spectroscopie RMN en solution a été limitée à de petits objets biologiques. Aujourd'hui, il est clairement reconnu que la stratégie du marquage isotopique spécifique de groupements méthyle dans une protéine perdeutérée a considérablement repoussé la frontière de cette technique. En effet, des protéines aussi grande que 1 MDa ont pu être récemment étudiées par RMN. Cependant, cette stratégie présente un inconvénient important lié au nombre réduit de sondes protonées. Dans ce contexte, le projet de thèse vise a développer de nouvelles méthodes pour faire face à cette rareté d'information structurale, en s'appuyant sur le marquage simultané (combinatoire) de plusieurs groupements méthyle afin d'augmenter le nombre de sondes. Pour un marquage combinatoire optimal, le choix des acides aminés à marquer et les précurseurs à utiliser ainsi que le protocole de leur incorporation doit être judicieusement étudié. Dans le présent travail, un nouveau protocole a été mis en place pour un marquage AbId1(LV)proS optimisé, exempt de toutes fuites isotopiques. En comparaison avec le marquage “AbId1LV standard", le modèle proposé permet la diminution d'un facteur de 2 le nombre de signaux RMN des Leu et Val et améliore par un facteur de 4 l'intensité des nOes à long portée qui sont expérimentalement détectable. Par ailleurs, ce protocole permet également la suppression des corrélations parasites, particulièrement nocives pour les études structurales basées sur la détection / analyse de nOes. Afin d'exploiter les spectres RMN obtenus en utilisant le protocole ci-dessus mentionné, l'attribution des signaux des méthyles est obligatoire. Deux stratégies ont été donc proposées. La première s'applique aux systèmes dont le poids moléculaire ne dépasse pas les 100 kDa (e.g. MSG). Elle se repose sur la linéarisation du marquage isotopique des acides aminés permettant ainsi l'utilisation de l'expérience 13C-TOCSY pour attribuer de manière régio et stéréo-spécifique les méthyles de l'isoleucine, leucine et valine en une seule étape. En ce qui concerne la seconde, adaptée aux protéines supra-moléculaire (> 100 kDa), c'est une optimisation de l'approche SeSAM (Sequence-Specific Assignment of Methyl groups by Mutagenesis) précédemment décrite dans la littérature. En effet, grâce au milieu de culture enrichi, mit au point pour le marquage spécifique de l'Ala, le volume minimal de culture requis a été considérablement diminué. Ceci a permis par conséquence de produire les protéines dans des plaques de 24 puits et de les purifier dans des plaques de 96 puits, raccourcissant ainsi le temps global de préparation des échantillons. Il a été estimé que l'utilisation de cette version améliorée de SeSAM offre la possibilité d'attribuer environ 100 méthyles en 2 semaines, dont 4 jours de temps de RMN, en consommant moins de 2 k € de matériaux isotopiques. Pour illustrer la pertinence du marquage isotopique et la protonation sélectifs des méthyles, de façon combinée ou pas, de nombreuses applications ont été présentés, à savoir l'étude en temps réel des processus d'auto-assemblage d'une protéine supramoléculaire (PhTET-2, ~ 0,5 MDa) par RMN. Le marquage combinatoire des protéines (82 kDa et 0,5 MDa) pour la détection de nOes longue portée (jusqu'à 10 Å et 8 Å respectivement) a également été étudié. Cette même approche a également été utilisée pour le filtrage de nOes inter-monomères à long portée, qui sont particulièrement importants pour le calcul de structure, dans des systèmes symétrique et homo-oligomèriques (PhTET-2). / Solution NMR spectroscopy has been limited to small biological objects for a long time. Nowadays, it is unequivocally recognized that the strategy of specific isotope labeling of methyl groups in a perdeuterated protein has significantly extended the frontier of this technique. Indeed, proteins as large as 1 MDa could be investigated by NMR. Conversely, this strategy presents an important drawback consisting of the drastically reduced number of protonated probes. The project of this thesis falls within the framework of developing new methodologies to cope with this scarce structural information, relying on the simultaneous labeling of several methyl groups to increase the number of probes. For optimized combinatorial labeling, the choice of the ensemble of amino acids to label simultaneously and the precursors as well as the protocol for their incorporation have to be carefully studied. In this work, a new protocol was introduced for the scrambling-free and optimized isotopic labeling of AbId1(LV)proS methyl groups. In comparison to the “standard AbId1LV” labeling scheme, the proposed pattern induces a 2-fold decrease of number of Leu and Val NMR signals and enhances the intensity of detectable long-range nOes by a factor 4. The described protocol also permits the suppression of spurious correlations, especially harmful for structural studies based on detection/analysis of nOes. To make an efficient use of the obtained high quality NMR spectra using this protocol, assignment of the methyl groups signals is mandatory. Two strategies were then proposed. The first is suitable for systems whose molecular weight does not exceed 100 kDa. It relies on the use of isotopically linearized precursors (with different isotope topologies to discriminate each methyl group) to assign in a regio- and stereo-specific manner the isoleucine, leucine and valine methyl groups in a single step, employing an optimized “out and back” 13C-TOCSY pulse sequence. While the second, adapted to supra-molecular proteins (> 100 kDa), consists of optimizing the previously reported SeSAM approach (Sequence-Specific Assignment of Methyl groups by Mutagenesis). Indeed, thanks to the developed enriched culture medium for the specific labeling of Ala, the minimal required culture volume was significantly decreased, enabling the proteins expression in 24 well plates and their parallel purification in 96 well plates. This improved SeSAM version was estimated to allow the assignment of ca. 100 methyl cross-peaks in 2 weeks, including 4 days of NMR time and less than 2 k€ of isotopic materials. To illustrate the pertinence of using selectively protonated methyl groups, either in a single or combined fashion, several applications were presented, namely the real-time NMR study of self-assembly process of a ~0.5 MDa supra-molecular protein (PhTET-2). The use of combinatorial labeling for the detection of long-range nOes to up to 10 Å (8 Å) in proteins of 82 kDa (respectively 0.5 MDa) was also investigated. This same approach was exploited for the filtering of inter-monomeric long-range nOes in the same symmetrical and homo-oligomeric PhTET-2 protein.

L'objectif de cette thèse est d'explorer les applications potentielles d'un système de langue électronique basée sur des récepteurs combinatoires à réactivités croisées et l'imagerie par résonance de plasmons de surface, pour l'analyse et la discrimination de différents milieux complexes et de bactéries. L'étude de milieux complexes a été réalisée sur des échantillons de différentes natures comme le vin, la bière et le lait d'origines végétale et animale. Les expériences ont démontré que notre système de langue électronique est capable de répondre avec une bonne sélectivité à ces milieux complexes et qu'il génère ainsi des profils continus 2D et des images 3D, propres à chaque échantillon. La différentiation et la classification de ces divers types de boissons ont été réalisées grâce à ces signatures 2D et 3D. Le dispositif a également prouvé son efficacité pour le suivi du vieillissement du lait. Une seconde étude a été dédiée à l'application du système pour la détection de bactéries. Dans un premier temps, des paramètres fluidiques ont été optimisés comme la forme et la profondeur de la cuve ou le débit fluidique, en raison de la morphologie variable des bactéries, considérées ici comme des objets biologiques complexes et volumineux. Dans un second temps, le système s'est révélé performant pour l'analyse de bactéries et a montré la possibilité de quantifier ces analyses. En effet, la langue électronique a permis la discrimination de différentes bactéries selon leur genre, leur espèce et en fonction des souches grâce aux profils continus 2D et aux images 3D. / The objective of this PhD thesis is to explore the potential applications of the electronic tongue, based on combinatorial cross-reactive receptors and surface plasmon resonance imaging, for analysis and discrimination of different complex mixtures and bacteria. In this work, various complex mixtures of different nature such as wine, beer, and milk (either animal-based or plant-based) are used. It has been demonstrated that the electronic tongue is capable of responding differently to theses samples with good selectivity. For each of them, it can generate characteristic continuous 2D profile and 3D image, based on which the differentiation and classification of the complex mixtures have been carried out. Furthermore, it has been illustrated that the electronic tongue is efficient for monitoring the deterioration of milk. In the second part of this thesis, the electronic tongue has been applied for detection and analysis of bacteria. At first, some fluidic parameters have been optimized due to the variable morphology of these complexes and large biological objects. Under optimized experimental conditions, the electronic tongue is effective for analysis of bacteria with the possibility for quantification. Thereafter, the electronic tongue has allowed for the discrimination of different bacteria according to their genus, species and strains based on continuous 2D profiles and 3D images.

Esta dissertação apresenta os algoritmos BicriterionAnt, MACS e MONACO, disponíveis na literatura, baseados em colônia de formigas, para resolução do Problema do Caixeiro Viajante Multiobjetivo (PCVMO). São apresentadas as características do problema e de cada algoritmo utilizado. Estes algoritmos foram testados em seis instâncias bi-objetivo do PCVMO. Foram implementadas algumas alterações na estrutura original dos algoritmos na tentativa de produzir resultados melhores do que os algoritmos originais. Para a avaliação dos resultados e medição da qualidade das soluções, foram utilizadas métricas de desempenho que auxiliam na identificação dos melhores conjuntos de soluções não-dominadas. / This dissertation presents the BicriterionAnt, MACS and MONACO Ant Colony algorithms, available in literature, to solve the Multi-Objective Traveling Salesman Problem (MOTSP). The characteristics of the problem and of each algorithm used are presented. Those algorithms were tested in six bi-objective instances of MOTSP. Changes in the original algorithms were implemented to try to produce better results than the original ones. To validate the results and to measure the quality of the solutions, metrics of performance were used which help to identify the best non-dominated solution sets.

A seleção de fornecedores de transporte é um desafio cada vez maior. O crescimento da rede de clientes a ser coberta demanda uma alocação eficiente em termos de custo não suprida por mecanismos tradicionais de negociação. Neste âmbito, o leilão combinatório torna-se uma alternativa de negociação ao permitir capturar sinergias entre os trajetos que devem ser atendidos. Em conseqüência disso, diminui-se o custo de transporte do fornecedor que se reflete nos menores preços de suas propostas e finalmente no custo total de compra do serviço. Por outro lado, esta decisão envolve fatores além do custo total; a mensuração destes torna-se importante para identificar fornecedores que melhor se ajustam aos requerimentos do comprador. No entanto, é fundamental escolher um método adequado para sua avaliação porque este influência a decisão final. Este problema de compra de serviços de transporte é conhecido na literatura como Winner Determination Problem (WDP) que, devido a sua complexidade, possui uma resolução limitada. Após revisão teórica, foi observado que os estudos relacionados à área de transporte focalizavam o desenvolvimento de modelos matemáticos que fossem representativos da realidade. Alguns destes modelos abordam a utilização de múltiplos critérios atribuindo um coeficiente que pondera cada critério. Evidenciou-se a necessidade do desenvolvimento de um algoritmo alternativo que além de facilitar sinergias entre trajetos, fosse abrangente o suficiente para tratar múltiplos critérios em instâncias compatíveis com problemas reais. Logo, com o intuito de contribuir com a literatura foi adaptado um algoritmo matemático otimizante ao problema de compras de fornecedores de transporte com base no algoritmo de Sandholm (2002). Este algoritmo aplica leilão combinatório de compras, apoiando-se na teoria da análise de decisão para mensurar critérios relevantes do comprador. Inicialmente, o algoritmo minimiza o custo total do comprador designando combinações de trajetos e fornecedores; depois é modificado para o tratamento multi-critério. Os resultados obtidos foram comparados com o software comercial CPLEX. / Selecting suppliers is a crescent challenge for the enterprises. The extent of the client web that needs to be served demands efficient allocations, in terms of cost, that are not addressed by traditional mechanisms. In this scenario, another mechanism came to be: the combinatorial auction. In this one, suppliers can express their synergies on routes they wish to supply. This leads to lowering their transportation costs, which is reflected in lower bidding prices as well as in the total cost of service. On the other hand, the selection of a supplier involves other criteria besides cost. The definition of these is essential to define which supplier fits the needs of the buyer. That is why it is of most importance to choose the right method to evaluate these needs, as it defines the final choice. This problem is known as Winner Determination Problem (WDP) and due to its complexity, possesses a feeble solution. After compiling what has been done about the subject, it was noticed that in the field of transport, studies are focused on mathematical models that represent reality. Some models address criteria assigning coefficients to the objective function by weighting on it. Clearly, there was a need for alternative algorithms that would, besides promoting synergies on routes, also treat multi-criteria problems close to reality. Therefore, searching for a valid contribution in the field, an adaption of an optimizing algorithm based on Sandholm (2002)s was made. The algorithm applies combinatorial auction, supported by decision analysis for measuring relevant buyers criteria. First, the main algorithms objective is to minimize buyers costs by combining routes and suppliers; then, a modified approach considers multi criteria. Results were then compared to the commercial software CPLEX.

Made available in DSpace on 2014-06-11T19:22:35Z (GMT). No. of bitstreams: 0 Previous issue date: 2007-05-25Bitstream added on 2014-06-13T20:49:18Z : No. of bitstreams: 1 goulartsobrinho_ef_me_ilha.pdf: 944900 bytes, checksum: 47dc5d964428b7cb8bd18e1e00e1d994 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Neste trabalho descreve-se uma metodologia para síntese e otimização de circuitos digitais, usando a teoria de algoritmos evolutivos e como plataforma os dispositivos reconfiguráveis, denominada Hardware Evolutivo do inglês- Evolvable Hardware - EHW. O EHW, tornou-se viável com o desenvolvimento em grande escala dos dispositivos reconfiguráveis, Programmable Logic Devices (PLD s), cuja arquitetura e função podem ser determinadas por programação. Cada circuito pode ser representado como um indivíduo em um processo evolucionário, evoluindo-o através de operações genéticas para um resultado desejado. Como algoritmo evolutivo, aplicou-se o Algoritmo Genético (AG), uma das técnicas da computação evolutiva que utiliza os conceitos da genética e seleção natural. O processo de síntese aplicado neste trabalho, inicia por uma descrição do comportamento do circuito, através de uma tabela verdade para circuitos combinacionais e a tabela de estados para os circuitos seqüenciais. A técnica aplicada busca o arranjo correto e minimizado do circuito que desempenhe uma função proposta. Com base nesta metodologia, são implementados alguns exemplos em duas diferentes representações (mapas de fusíveis e matriz de portas lógicas). / In this work was described a methodology for optimization and synthesis of digital circuits, which consist of evolving circuits through evolvable algorithms using as platforms reconfigurable devices, denominated Evolvable Hardware (EHW). It was became viable with the large scale development of reconfigurable devices, whose architecture and function can be determined by programming. Each circuit can be represented as an individual within an evolutionary process, evolving through genetic operations to desire results. Genetic Algorithm (GA) was applied as evolutionary algorithm where this technique evolvable computation as concepts of genetics and natural selection. The synthesis process applied in this work starts from a description from the circuits behavior. Trust table for combinatorial circuits and state transition table for sequential circuits were used for synthesis process. This technic applied search the correct arrange and minimized circuit which response the propose function. Based on this methodology, some examples are implemented in two different representations (fuse maps and logic gate matrices).

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Every beginning of semester higher education institutions face the same dilemma: to assignment courses to classrooms keeping up certain restrictions. This problem is known as Classroom Assignment Problem or Rooms Allocation Problem and consists of allocating courses, with schedules established, at classrooms considering the room capacity and the needs of teachers and students. This process usually is solved manually by the institutions, which can take several days to complete, besides it is hard work and often does not guarantee the efficient allocation of spaces. This reality is also faced by the Technology Center of the Federal University of Santa Maria that due to increasing demand and expansion of the institution needs to adapt to efficiently allocate the available spaces. Currently, the center has 14 undergraduate courses divided into three buildings that have 47 rooms, effectively used, with capacities ranging between 25 and 50 students. Thereby, the aim of this study is to propose a new configuration for the allocation of classrooms in the Technology Center at the Federal University of Santa Maria in order to make the most efficient use of space. Therefore, the study has the support of the precepts of operational research so that a mathematical model was developed to represent the problem. Were used as reference the courses offered in the first and second half of 2014 and from these databases built were coded in ZIMPL and implemented with CPLEX. Because of the problem size, it was decided to split the databases on weekdays and shifts (morning and afternoon) totaling 20 instances. Overall, the results meets the proposed objectives to optimize the spaces and also demonstrated some nonconformities as between the number of vacancies offered by the disciplines and capabilities of rooms. In addition, it was found that there is some imbalance in the supply of disciplines as the days and timeslots, which consequently leads to difficulties for classrooms assignment. Furthermore, it is suggested that further studies are conducted, especially with the use of metaheuristics in order to test the quality of these solutions. / Todo início de semestre letivo as instituições de ensino superior enfrentam o mesmo dilema: o de alocar disciplinas às salas de aula respeitando determinadas restrições. Esse problema é conhecido como Classroom Assignment Problem ou Problema de Alocação de Salas (PAS) e consiste na alocação de disciplinas, com horários já estabelecidos, a salas de aulas considerando-se a capacidade da sala e as necessidades dos docentes e discentes. Esse processo, geralmente, é resolvido pelas instituições de ensino manualmente o que além de levar vários dias para ser concluído muitas vezes não garante a alocação eficiente dos espaços. Tal situação também é a enfrentada pelo Centro de Tecnologia da Universidade Federal de Santa Maria (UFSM) que devido à crescente demanda e expansão da Instituição precisa se adaptar para alocar eficientemente os espaços disponíveis. Atualmente, o Centro conta com 14 cursos de graduação alocados em três prédios que dispõem de 47 salas, efetivamente utilizadas, com capacidades que variam entre 25 e 50 alunos. Sendo assim, este estudo se propôs a desenvolver uma nova configuração para a alocação de salas de aula do Centro de Tecnologia da UFSM a fim de tornar mais eficiente o uso dos espaços. Para tanto o trabalho teve como aporte metodológico os preceitos da pesquisa operacional de modo que foi desenvolvido um modelo matemático para representar o problema. Foram utilizados como referência os dados das disciplinas ofertadas no primeiro e segundo semestre de 2014. De modo geral, os resultados encontrados foram ao encontro dos objetivos propostos de otimizar os espaços e também demostraram algumas inconformidades como entre o número de vagas ofertadas pelas disciplinas e as capacidades das salas. Ademais, sugere-se que novos estudos sejam realizados, em especial com o uso de metaheurísticas, a fim de testar a qualidade das soluções apresentadas.

Made available in DSpace on 2016-06-02T19:51:39Z (GMT). No. of bitstreams: 1 2523.pdf: 1711552 bytes, checksum: cf13454170c0e1db1eb5ae2aa8cff6a3 (MD5) Previous issue date: 2009-02-26 / Financiadora de Estudos e Projetos / The object of this study is a particular case of the cutting and packing problems, known as container loading problems. These problems consist in arranging rectangular boxes orthogonally into containers (or into trucks, railcars and pallets), in order to optimize an objective function, for example, maximize the utilization of the available space, or minimize the number of the required containers to load all the available items. The objective of this study is to develop mathematical programming models to deal with situations commonly found in container loading practice. Multiple orientations of the boxes, weight limit of the container, cargo stability, load bearing strength of the boxes and multiple destinations of the cargo are considered. The author is not aware of mathematical formulations available in the cutting and packing literature that deal with such considerations, and this paper intends to contribute with possible formulations that describe these situations, although not very realistic for being used in practice. Computational experiments with the proposed models are performed with the software AMS/CPLEX and randomly generated instances extracted from the cutting and packing literature. The results show that the models are consistent and properly represent the practical situations treated, although this approach (in its current version) is limited to solve to optimality only medium-sized problems. However, we believe that the proposed models can be useful to motivate future research exploring decomposition methods, relaxations, heuristics, among others, to solve the present problems. / O objeto de estudo deste trabalho é um caso particular dos problemas de corte e empacotamento, conhecido como problemas de carregamento de contêineres. Estes problemas consistem em arranjar caixas retangulares ortogonalmente dentro de contêineres (ou caminhões, vagões ferroviários e paletes), de maneira a otimizar uma função objetivo, por exemplo, maximizar o aproveitamento do espaço disponível, ou então minimizar o número de contêineres necessários para carregar todas as caixas disponíveis. O objetivo deste trabalho é desenvolver modelos de programação matemática que abordem situações comumente encontradas na prática do carregamento de contêineres. Considerações de múltiplas orientações das caixas, limite de peso do contêiner, estabilidade do carregamento, resistência das caixas ao empilhamento e carga fracionada em múltiplos destinos são tratadas. O autor não tem conhecimento de formulações matemáticas disponíveis na literatura de corte e empacotamento que tratem estas considerações, e este trabalho pretende contribuir com possíveis formulações que, embora pouco realistas para serem aplicadas na prática, descrevem estas situações. Experimentos computacionais com os modelos propostos são realizados utilizando o aplicativo GAMS/CPLEX e exemplos gerados aleatoriamente e da literatura. Os resultados mostram que os modelos são coerentes e representam adequadamente as situações tratadas, embora esta abordagem (na sua versão atual) esteja limitada a resolver otimamente apenas problemas de tamanho bem moderado. No entanto, os modelos podem ser úteis para motivar pesquisas futuras explorando métodos de decomposição, métodos de relaxação, métodos heurísticos, entre outros, para resolver os problemas em questão.