[pt] As técnicas de tecnologia de grupos vêm sendo largamente usadas em muitos sistemas de manufatura. Vários algoritmos têm sido propostos para o projeto otimizado de eficientes células de manufatura. O problema de formação de células deve levar em conta vários objetivos: o número de operações gargalo, o número de máquinas e/ou peças gargalo, o fluxo intercelular, os custos de subcontratação, os custos de duplicação de máquinas e a carga da máquina e/ou célula mais sobrecarregada, entre outros. Nesta tese propõe-se uma metodologia multi- critério para resolver o problema de formação de células com múltiplos objetivos. Este enforque é baseado no uso da meta-heurística busca tabu para resolver uma seqüência de problemas com objetivos simples e restrições múltiplas, onde cada objetivo é minimizado individualmente, segundo sua ordem de importância. Resultados computacionais envolvendo uma aplicação para um problema bi-critério são apresentados para casos com até 100 máquinas e 1000 peças. / [en] Group tecnology techniques are now widely used in many manufacturing systems. Severla algorithms have been proposed for the optimal design of efficient manufacturing cells. The cell formation problem must take into account several objectives: the number of bottleneck operations, the number of bottleneck machines and/or parts, the intercell flow, the intracell workload balancing, the subcontracting cost, the machine duplication costs, and the workload of the busiest machine and/or cell, among athers. In this work, we propose a multi-criteria methodology for solving the cell formation problem with multiple objectives. This approach is based on the use of the tabu search meta-heuristic for solving a sequence of single-objective, multi-contrained problems, in wich each objective is taken and optimized in turn, following their order of relative importance. Computational results concerning an application to a bi-criteria problem are reported for instances with up 100 machines and 1000 parts.

[pt] O teste lógico de circuitos integrados VLSI é parte indispensável de sua fabricação e projeto. O enfoque pseudo-exaustivo para o teste lógico de circuitos integrados consiste em particionar o circuito original a ser testado em subcircuitos com um reduzido número de entradas, que são então testados em paralelo de forma exaustiva. Neste trabalho apresenta-se um algoritmo aproximado para o problema de particionamento de circuitos integrados combinacionais, baseado na metaheurística de busca tabu. O algoritmo proposto apresenta diversas características originais, tais como: o conceito de vizinhança reduzida, obtida por movimentos envolvendo apenas um subconjunto de nós de fronteira; movimentos complexos que induzem diversos movimentos resultantes, embora as variações na função de custo sejam facilmente calculáveis; uma função objetivo bi-critério combinando o número de circuitos e o número de cortes, que simultaneamente adiciona uma estratégia de diversificação à busca; e o uso de uma heurística de empacotamento como passo de pós-otimização. O desempenho do algoritmo proposto foi avaliado através de sua aplicação a um conjunto de circuitos computacionais ISCAS padronizados. Os resultados computacionais foram comparados com aqueles fornecidos pelos algoritmos conhecidos na literatura, obtendo-se melhorias significativas. As taxas de médias de redução foram da ordem de 30% para o número de subcircuitos na partição e de 40% para o número de cortes. / [en] The logical test of integrated VLSI circuits is one of the main phases of their design and fabrication. The pseudo-exhaustive approach for the logical test of integrated circuits consists in partitioning the original circuit to be tested into non-overlapping subcircuits with a small, bounded number of subcircuits, which are then exhaustively tested in parallel. In this work we present an approximate algorithm for the problem of partitioning integrated combinational circuits, based on the tabu search metaheuristic. The proposed algorithm presents several original features, such as: the use of a reduced neighborhood, obtained from moves involving only a subset of boundary nodes; complex moves which entail several resulting moves, although the variations in the cost function are very easily computable; a bi-criteria cost function combining the number of subcircuits and the number of cuts, which simultaneously adds a diversification strategy to the search; and the use of a bin-packing heuristic as a post-optimization step. The behavior of the proposed algorithm was evaluated through its application to a set of benchmark ISCAS combinational circuits. The computational results have been compared with those obtained by the other algorithms in the literature, with significant improvements. The average reduction rates have been of the order of 30% in the number of subcircuits in the partition, and of the order of 40% in the number of cuts.

[pt] A principal contribuição desta tese consiste no desenvolvimento de uma heurística híbrida, robusta e eficiente, para o problema de empacotamento unidimensional. A heurística proposta utiliza os seguintes componentes: limites inferiores e superiores do número de caixas; reduções; abordagem dual para a obtenção de soluções iniciais; heurísticas para redistribuição dos pesos; e busca tabu. O outro objetivo desta tese é a aplicação desta heurística para a solução do problema de escalonamento em processadores paralelos idênticos. São apresentados resultados computacionais obtidos sobre centenas de problemas testes da literatura. / [en] We propose in this work a hybrid improvement procedure for the bin packing problem. This heuristic has several components: lower and upper bounds; reductions, construction of initial solutions by reference to the dual problem;heuristics for load redistribution based on dominance, differencing, and unbalancing; and tabu search. We also investigate the application of this hybrid heuristic to the problem of task scheduling on identical parallel processors. Computational results on hundreds of benchmark test problem are presented.

[pt] O aumento do consumo de energia elétrica leva os sistemas de distribuição a operar próximo do seu limite, podendo ocorrer situações de máximo fluxo de potência ativa e reativa nos ramos, ou seja, problemas de estabilidade de tensão. A mudança da topologia da rede permite encontrar uma configuração em que os índices de estabilidade de tensão estão distantes do ponto de máximo carregamento do sistema, reduzir as perdas técnicas e tornar a distribuição de carga nos alimentadores mais uniforme. Contudo, o número de possibilidades de chaveamento cresce com o aumento da dimensão da rede elétrica e a busca pela solução ótima requer esforço computacional elevado. O uso do algoritmo heurístico de Busca Tabu permite direcionar a busca por novas configurações de qualidade, armazenando suas características e proibindo a adição e/ou remoção de atributos por um período, evitando que a busca termine em um valor mínimo (máximo) local. Os resultados das análises em diferentes níveis de carregamento, que representam a operação do sistema radial de distribuição com carga leve, pesada e crítica, mostram que o algoritmo de Busca Tabu adotado neste trabalho consegue maximizar a margem de potência da barra crítica do sistema, levando o ponto de operação original à uma distância maior do ponto de máximo carregamento do sistema, na região normal de operação e minimizando as perdas técnicas. Com isso, evita-se que o sistema opere no ponto de máximo carregamento ou, na pior das hipóteses, na região anormal de operação, onde as ações de controle têm efeito oposto ao esperado. / [en] The increase of the consumption of electric energy takes the distribution systems to operate next to its limits, which might cause situation of maximum active and reactive power flow in the branches, that is, problems of voltage stability. The change of the topology of the network allows to find a configuration where de voltage stability indexes are far from de maximum loading point, improve voltage profile, reduce power losses and load balancing. However, the number of possible switching grows with the dimension of network and searching for optimal solution requires high computational effort. Using Tabu Search heuristics allows guiding the search for new configuration of high quality, being storing its characteristics and forbidding the addition and/or removal of attributes for a period, avoiding that the search finishes in a local minimum (maximum) value. The results in different loading levels, that represent the operation of radial distribution system with normal, weighed and critical load, show that the Tabu Search algorithm maximizes the voltage stability margin, leading the original operation point to a new one that is far from the maximum loading point, in the normal region of operation. With this, it is prevented that the system operates next to the maximum loading point or, in the worse case, in the abnormal region of operation, where the actions of control have opposing effect to the waited one.

[pt] Esta tese faz um estudo do problema do Conjunto Dominante, um problema NP-difícil de grande relevância em aplicações relacionadas ao projeto de rede sem fio, mineração de dados, teoria de códigos, dentre outras. O conjunto dominante mínimo em um grafo é um conjunto mínimo de vértices de modo que cada vértice do grafo pertence a este conjunto ou é adjacente a um vértice que pertence a ele. Três variantes do problema foram estudadas; primeiro, uma variante na qual considera pesos nos vértices, buscando um conjunto dominante com menor peso total; segundo, uma variante onde o subgrafo induzido pelo conjunto dominante está conectado; e, finalmente, a variante que engloba essas duas características. Para resolver esses três problemas, propõe-se um algoritmo híbrido baseado na meta-heurística busca tabu com componentes adicionais de programação matemática, resultando em um método por vezes chamado de mateurística, (matheuristic, em inglês). Diversas técnicas adicionais e vizinhanças largas foram propostas afim de alcançar regiões promissoras no espaço de busca. Análises experimentais demonstram a contribuição individual de todos esses componentes. Finalmente, o algoritmo é testado no problema do código de cobertura mínima, que pode ser visto como um caso especial do problema do conjunto dominante. Os códigos são estudados na métrica Hamming e na métrica Rosenbloom-Tsfasman. Neste último, diversos códigos menores foram encontrados. / [en] This thesis addresses the Dominating Set Problem, an NP- hard problem with great relevance in applications related to wireless network design, data mining, coding theory, among others. The minimum dominating set in a graph is a minimal set of vertices so that each vertex of the graph belongs to it or is adjacent to a vertex of this set. We study three variants of the problem: first, in the presence of weights on vertices, searching for a dominating set with smallest total weight; second, a variant where the subgraph induced by the dominating set needs to be connected, and,finally, the variant that encompasses these two characteristics. To solve these three problems, we propose a hybrid algorithm based on tabu search with additional mathematical-programming components, leading to a method sometimes called matheuristic. Several additional techniques and large neighborhoods are also employed to reach promising regions in the search space. Our experimental analyses show the good contribution of all these individual components. Finally, the algorithm is tested on the covering code problem, which can be viewed as a special case of the minimum dominating set problem. The codes are studied for the Hamming metric and the Rosenbloom-Tsfasman metric. For this last case, several shorter codes were found.