Orientador : Flavio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-03T22:35:40Z (GMT). No. of bitstreams: 1 Livramento_Silvana_M.pdf: 3965624 bytes, checksum: 7efc5625e3e06afcabeb2446a5d7a69e (MD5) Previous issue date: 2004 / Resumo: Desenvolvemos Algoritmos Genéticos (AGs) para resolver problemas no projeto de redes de telecomunicações. Um problema consiste em particionar uma grande área de projeto urbana em pequenas seções de serviços, as quais são controladas por um único equipamento de comunicação. O AG desenvolvido para este problema incorpora informações geométricas e topológicas da área de projeto operando diretamente com uma malha de pontos de demanda geograficamente dispersos. Dada uma seção de serviço, a outra fase deste projeto, consiste em agrupar os pontos de demanda em grupos pequenos e posicionar outros equipamentos em postes da rede elétrica, para fazer a comunicação entre estes grupos e o equipamento de comunicação da seção de serviço. Outro AG foi desenvolvido para este problema, e também incorpora informações geométricas e topológicas, pois trabalha diretamente sobre o grato de vizinhança dos postes existentes numa seção de serviço e a ligação destes com os pontos de demanda. Os resultados computacionais mostraram que os dois AGs são técnicas promissoras para projetar uma rede de telecomunicações, obtendo resultados favoráveis em tempo computacional razoável. Todos os testes foram realizados com instâncias reais tomadas de grandes áreas da cidade de São Paulo / Abstract: We propose Genetic Algorithms (GAs) to solve problems in telecommunication network design. The first problem is to partition a large urban project area into sma1ler service sections, which can be controlled by a single standard communication switch. The GA for this problem incorporates geometric and topological information from the project area by operating directly with a grid of geographically dispersed demand points. Given a service section, the second problem, consists to group the demand points in sma1ler areas and to position another equipments in poles of the electric net, to make the communication between these groups and the service section switch. Another GA is developed to this problem, and also incorporates geometric and topological information, since it works directly through the neighborhood graph of existents poles in a service section and the connection between these poles and the demand points. Computation results show both AGs to be a promising technique for telecommunication network design. In the tests, we used real instances taken from large areas in the city of São Paulo / Mestrado / Mestre em Ciência da Computação

Orientador: Marcus Vinicius Soledade Poggi de Aragão / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-20T17:26:15Z (GMT). No. of bitstreams: 1 Parreira_AndersonDelcio_M.pdf: 2926539 bytes, checksum: 1988c6c0a1469a2fe4ef22acd76a154d (MD5) Previous issue date: 1995 / Resumo: Este trabalho tem como tema central a proposta de um método de resolução eficiente do Problema de Máxima Satisfatibilidade Ponderada. Esta proposta tem sua motivação em uma classe de instâncias deste problema que pode ser resolvida em tempo polinomial. A classe de interesse neste trabalho é a das instâncias cujo grafo de co-ocorrência associado é uma k-árvore. O algoritmo capaz de resolve-lo em tempo linear é um método algébrico conhecido como Algoritmo Fundamental de Hammer, Rosenberg e Rudeanu em sua versão modificada proposta por Crama, Hansen e laumard. A abordagem deste trabalho está na utilização de métodos enumerativos, branch & bound como são mais frequentemente citados, de modo a transformar instâncias gerais em instâncias pertencentes à classe de interesse. Deste modo, tanto a enumeração como a resolução algébrica podem ter suas tarefas simplificadas. Três estratégias para esta combinação algébrico-enumerativa foram propostas e implementadas. Os algoritmos resultantes foram extensivamente testados em diferentes conjuntos de instâncias, sendo seus resultados comparados com implementações dos algoritmos puramente algébrico e puramente enumerativo. Esse trabalho apresenta também uma generalização dos limites superiores propostos por Hansen para programação não-linear 0-1 para o caso em que variáveis complementadas são incorporadas aos termos. Esses limites além de integrados ao método proposto, foram implementados e testados individualmente / Abstract: The proposal of an efficient resolution on method for the Maximum Satisfiability Problem is the object of this work. The motivation for this proposal relies on a special class of instances that can be solved by a linear time algorithm. This class is the one for which the co-occurrence graph associated to the instance is a partial k-tree. It was shown by Crama, Hansen and Jaumard how the Basic Algorithm of Hammer, Rosenberg and Rudeanu, an algebraic method, an solve these instances in linear time. The approach here proposed consists in applying an enumerative method to derive from any general instance several linear time instances that constitute a partition of the solution space. This allows the enumerative and the algebraic approaches to have their tasks simplified. Three strategies of this algebraic-enumerative combination where proposed and implemented. The resulting algorithm where tested on several different data sets. The results where compared with both algebraic and enumerative pure approaches. This work also generalizes Hansen's upper bounds and penalties for non-linear 0-1 programming to the case where complemented and uncomplement variables appear in the product terms. These where also implemented, tested and incorporated to the combined codes / Mestrado / Mestre em Ciência da Computação

Orientador: Armando Zaupa Remacre / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Geociencias / Made available in DSpace on 2018-07-19T10:49:29Z (GMT). No. of bitstreams: 1 Camara_PauloSergio_M.pdf: 9008932 bytes, checksum: 1911a3cf82c5fbb16ad2aa8e52215daf (MD5) Previous issue date: 1992 / Resumo: A modelagem estocástica vem recebendo interesse crescente na indústria do petróleo, consolidando-se como ferramenta cada vez mais rotineira na elaboração de planos de explotação em reservatórios produtores. Técnicas de otimização combinatorial, como o "simulated annealing", permitem gerar modelos equiprováveis de variáveis do reservatório, reproduzindo a princípio qualquer característica que possa ser expressa como uma função objetivo, além do histograma e variograma, que podem ser honrados com os métodos tradicionais da geoestatística. Nesta dissertação, a capacidade do algoritmo de "annealing" em aproveitar informações geológicas e de produção (testes de formação), diminuindo as incertezas dos modelos gerados é revista. Conclusões de trabalhos recentes (Pérez, 1991; Deutsch, 1992) são confirmadas e extendidas para casos mais abrangentes. Um algoritmo recentemente desenvolvido, denominado evolução estocástica, é introduzido na modelagem probabilística, sendo comparado com o "simulated annealing" em termos de tempo de execução e capacidade de reproduzir características com niveis de complexidade diversos, em problemas de diferentes dimensões. A qualidade dos modelos simulados também é analisada com alguns critérios apresentados (tempos, tolerâncias, coeficiente de correlação entre as imagens simulada e real e comportamentos de fluxo). É verificada a capacidade dos algoritmos em simular seções verticais de reservatórios com diferentes niveis de informação. São analisados o efeito da inclusão do variograma global, de variogramas e médias de regiões do reservatório e finalmente, aproximações da permeabilidade equivalente obtidas de testes de formação por dois métodos existentes / Abstract: Stochastic modeling has received increasing attention in the oil industry, being established as a ordinary tool for helping the elaboration of development plans in producing reservoirs. Combinatorial optimization techniques, such as simulated annealing, allow to produce equiprobable models of reservoir variables, reproducing a priori any characteristic that can be stated as an objective function, besides the histogram and the variogram, which can be honored with traditional geostatistics methods. In this thesis, the ability of the simulated annealing algorithm to incorporate geological and production (well test) data, reducing uncertainties in simulated models is reviewed. Recent works resuIts (Pérez, 199] j Deutsch, ]992) are reinforced and extended for a wider range of properties. Stochastic evolution, a newly developed algorithm, is introduced in probabilistic modeling. A comparison between this technique and annealing is performed, taking into account computing times and capacity of reproducing several complexity levels characteristics for different size problems. The quality of simulated models is also studied using some cri teria, such as CPU time, tolerances, correlation coefficients between simulated and real images, and flow performance. The algorithms ability for generating reservoir vertical cross sections with several constraining information levels is verified. The effect of inc1uding global (whole reservoir) variogram, local variograms, local averages and well test derived permeability with two approximations methods is analyzed. / Mestrado / Geoengenharia de Reservatorios / Mestre em Geociências

A dissertação apresenta o problema de corte de estoque, que é um problema de otimização inteiro, difícil de ser resolvido computacionalmente. Resolvemos o problema relaxando a condição de integralidade pelo método simplex com geração de colunas, mas esta solução não é viável na prática. Estudamos várias heurísticas para a obtenção da solução inteira do problema.

Made available in DSpace on 2019-03-30T00:01:23Z (GMT). No. of bitstreams: 0 Previous issue date: 2018-06-26 / Virtual sensors provisioning is a central issue for sensors cloud middleware since it is responsible for selecting physical nodes, usually from Wireless Sensor Networks (WSN) of different owners, to handle user's queries or applications. Recent works perform provisioning by clustering sensor nodes based on the correlation measurements and then selecting fewer nodes as possible to preserve WSN energy. However, such works consider only homogeneous nodes (all nodes using the same set of sensors). Therefore, those works are not entirely appropriate for sensor clouds, which in most cases comprises heterogeneous sensor nodes. In this thesis, we propose ACxSIM, an approach to enhance the provisioning task by considering heterogeneous environments. Two main algorithms form ACxSIM. The first one, ACASIM, creates multi-dimensional clusters of sensor nodes, taking into account the measurements correlations instead of the physical distance between nodes like most works on literature. Then, the second algorithm, ACOSIM, based on an Ant Colony Optimization system, selects an optimal set of sensors nodes from to respond user¿s queries while attending all parameters and preserving the overall energy consumption. Simulations have shown that ACxSIM has better performance than the LEACH protocol regarding energy consumption (7.0x) and Mean Squared Error (2.0x), indicating the feasibility of the proposed approach. Keywords: Ant Colony Optimization. Clustering. Virtualization. Wireless Sensor Networks. / No contexto de nuvens de sensores, o procedimento de provisionamento é essencial, uma vez que é responsável por selecionar os sensores físicos, geralmente de redes de sensores sem fio (RSSF) de diferentes proprietários, que serão alocados (provisionados) para compor os sensores virtuais. Trabalhos recentes na literatura realizam o provisionamento agrupando nós de sensores com base nas medidas de correlação e, em seguida, selecionando o menor conjunto possível de nós para preservar a energia da RSSF, ao mesmo tempo que garante os requisitos das aplicações. No entanto, tais trabalhos consideram apenas nós homogêneos, i.e., nós que monitoram o mesmo conjunto de variáveis. Desta forma, tais trabalhos não são inteiramente apropriados para o ambiente de nuvens de sensores, que na maioria dos casos incluem nós sensores heterogêneos. Nesta tese, propomos ACxSIM, uma abordagem para aprimorar o provisionamento de sensores virtuais, considerando ambientes heterogêneos. Dois algoritmos principais formam ACxSIM. O primeiro, ACASIM, cria clusters multidimensionais de nós de sensores, levando em consideração as correlações de medições em vez da distância física entre nós, que é a abordagem padrão da maioria dos trabalhos encontrados na literatura. Em seguida, ACOSIM, um algoritmo baseado em um sistema de otimização por colônia de formigas, seleciona um conjunto ótimo de nós de sensores para responder as consultas do usuário que atende aos parâmetros das consultas e preserva o consumo geral de energia. Simulações realizadas mostraram que ACxSIM possui melhor desempenho do que o protocolo LEACH com relação ao consumo de energia (aproximadamente 7.0x) e Erro Quadrático Médio (2.0x), indicando a viabilidade da abordagem proposta. Palavras-chaves: Otimização por colônia de formigas. Agrupamento. Virtualização. Redes de Sensores Sem Fio.

Made available in DSpace on 2019-03-30T00:01:35Z (GMT). No. of bitstreams: 0 Previous issue date: 2015-01-27 / This work presents a block-loading hybrid approach to solve the Container Loading Problem. The general idea behind the proposed algorithm is to decompose this classic Cutting and Packing problem into two subproblems, namely, a three-dimensional problem of generating a set of blocks of boxes and a two-dimensional problem of positioning a subset of these blocks on the floor of the container. On the one hand, the block generation phase is completely deterministic. Constructive algorithms to accomplish this task have been recently proposed. On the other hand, the positioning phase is non-deterministic. It comprises the Generate-and-Solve methodology, a hybrid optimization framework that combines a metaheuristic engine with an exact solver. Computational experiments performed on benchmark problem instances show that hybrid approach presents very competitive results compared to those found by state-of-the-art algorithms, obtaining in average a space utilization of 93.49% for the instances under investigation. Regarding only the best solution found for each instance, the space utilization was of 94.13% in average. In particular, for instances with a few number of box types, the proposed approach outperformed the best results reported in the literature in several test cases. Key-words: Combinatorial Optimization. Cutting and Packing. Container Loading. HybridMetaheuristics. / Este documento apresenta uma abordagem híbrida de posicionamento de blocos para resolver o Problema de Carregamento de Contêiner. A ideia central do algoritmo proposto é decompor esse clássico problema de Corte e Empacotamento em dois subproblemas: um problema de empacotamento tridimensional que objetiva gerar blocos de caixas; e um problema de posicionamento bidimensional no piso do contêiner que busca maximizar o volume ocupado por um subconjunto desses blocos. Por um lado, a fase de geração de blocos é completamente determinística. Algoritmos construtivos que realizam essa tarefa têm sido recentemente propostos. Por outro lado, a fase de posicionamento de blocos é não-determinística. Esta compreende a metodologia híbrida Gerar-e-Resolver, que combina uma metaheurística com um modelo exato. Experimentos computacionais realizados em bibliotecas de testes da literatura mostram que a abordagem híbrida apresenta resultados bastante competitivos em relação àqueles do estado da arte, alcançando aproveitamento médio de 93,49% do espaço do contêiner para as instâncias estudadas. Considerando apenas a melhor solução encontrada para cada instância, o aproveitamento médio foi de 94,13%. Em particular, para instâncias com poucos tipos de caixas, a abordagem superou os melhores resultados conhecidos na literatura em diversos casos de teste. Palavras-chaves: Otimização Combinatória. Corte e Empacotamento. Carregamento de Contêiner. MetaheurísticasHíbridas.

Made available in DSpace on 2019-03-29T23:32:55Z (GMT). No. of bitstreams: 0 Previous issue date: 2012-08-30 / The aim of this study is to establish a parallel between four bioinspired metaheuristic algorithms (namely, Genetic Algorithm, Differential Evolution, Particle Swarm Optimization, and Harmony Search), testing them with continuous optimization benchmark functions and assessing them based on data collected about the quality of the solutions they generate and based on the way they explore the search space. Novel techniques are proposed to collect data about the modus operandi of the algorithms using Voronoi Diagrams and through a division of the search space in bi-dimensional regions using Self-Organizing Maps. The use of these maps as a Visual Data Mining tool aims to process the resulting data and identify the available clusters. We wish to understand the influence of parameter calibration on the search behavior of the metaheuristic algorithms, as well as their sensitivity to dimension changes of the optimization functions they are solving. Furthermore, behavior profiles can be established and patterns can be defined, allowing us to analyze in detail the similarities/dissimilarities between the algorithms. All metaheuristics were implemented step-by-step to allow us to understand their inner workings, peculiarities, and also facilitate the tracking of their search behavior along their execution on the optimization problems. Keywords: Bioinspired Metaheuristics. Information Visualization. Visual Data Mining. Self-Organizing Maps. Kohonen Maps. Voronoi Diagrams. / Este trabalho tem por finalidade traçar um paralelo entre quatro algoritmos bio-inspirados de cunho meta-heurístico (a saber: Algoritmo Genético, Evolução Diferencial, Otimização por Enxame de Partículas e Busca Harmônica), testando-os em funções de benchmark de otimização contínua e avaliando-os com base em dados coletados sobre a qualidade das soluções geradas e sobre o modo de exploração do espaço de busca. São propostas aqui técnicas de coleta de informações sobre o modus operandi dos algoritmos que envolvem Diagramas de Voronoi e divisão do espaço de busca em regiões bidimensionais utilizando Mapas Auto-organizáveis. O uso desses mapas como ferramenta de Mineração Visual de Dados tem como objetivo avaliar os dados gerados e identificar os agrupamentos que foram formados. Procuramos entender a influência da alteração dos valores dos parâmetros das meta-heurísticas no seu comportamento ao longo do tempo, bem como a sua sensibilidade às mudanças de dimensão das funções de otimização que estão solucionando. Dessa forma, almeja-se traçar perfis de comportamento e definir a posteriori um padrão para possibilitar a análise mais detalhada das similaridades/dissimilaridades entre as abordagens. Todos os algoritmos utilizados foram implementados passo-a-passo a fim de entender as suas particularidades, esclarecer melhor seus mecanismos internos e facilitar o rastreamento do comportamento dos mesmos no ato da resolução dos problemas. Palavras-chave: Meta-heurísticas Bioinspiradas. Visualização da Informação. Mineração Visual de Dados. Mapas Auto-Organizáveis. Mapas de Kohonen. Diagramas de Voronoi.

O Problema de Minimização do Número Máximo de Pilhas Abertas (MOSP, do inglês minimization of open stacks problem) é um problema de otimização combinatória da família NP-Difícil que vem recebendo grande atenção na literatura especializada. Este trabalho apresenta novas contribuições em termos de modelos e técnicas de resolução para o problema. A primeira parte deste trabalho lidou com modelos matemáticos, sendo analisados os modelos existentes que se baseiam em programação inteira mista. Variações de um modelo da literatura foram propostas, com o objetivo de tentar diminuir o tempo de execução necessário para se obter uma solução exata com a utilização de pacotes comerciais. Os resultados mostraram que as propostas são capazes de acelerar a solução de algumas classes de instâncias mas, que de maneira geral, métodos baseados em relaxação linear encontram dificuldade em provar a otimalidade devido à baixa qualidade dos limitantes inferiores. Uma outra contribuição deste trabalho foi o desenvolvimento de um modelo conjunto para o problema MOSP e para o problema de minimização da duração de pedidos (MORP, do inglês minimization of order spread problem). Este modelo propõe um framework unificado em que os dois problemas podem ser resolvidos ao mesmo tempo, tendo suas funções objetivo individuais ponderadas através de pesos definidos pelo usuário. A segunda parte do trabalho voltou-se para o desenvolvimento de métodos heurísticos para o MOSP. Duas estratégias de solução foram desenvolvidas. O primeiro método propõe uma transformação heurística entre o problema MOSP e o clássico problema do caixeiro viajente (TSP, do inglês traveling salesman problem). A partir de uma representação em grafo do MOSP, o TSP é definido por meio de uma regra de atribuição de distâncias baseadas nos graus dos nós. Nos testes computacionais, a estratégia proposta mostrou-se eficiente em relação às heurísticas específicas para o MOSP, obtendo a solução ótima do MOSP em 80,42% das instâncias testadas e sendo competitiva em termos de tempo computacional com algumas das melhores heurísticas da literatura. O segundo método heurístico proposto utilizou a ideia de decomposição. De fato, neste método, um corte no grafo associado ao problema original divide-o em problemas menores, que são resolvidos. A solução global é obtida através da junção das soluções dos subproblemas e, em alguns casos, é possível demonstrar a otimalidade da solução obtida. Testes computacionais indicam a validade da proposta e apontam caminhos para pesquisas futuras / The minimization of open stacks problem (MOSP) is a well known NP-hard combinatorial optimization problem that has been extensively discussed in the specialized literature. This study presents some new contributions in terms of models and solution methods for this problem. The first part of this thesis dealt with mathematical models. The existing mixedinteger models have been analyzed and variants of a well known model have been proposed, with the goal of reducing the time needed by commercial packages to obtain proved-optimal solutions. The results of computational tests on a widely used set of instances have indicated that the modifications proposed are able to reduce the time needed to obtain optimal solutions for some classes of instances. Nevertheless, a conclusion has been the fact that mixed-integer programming models have difficulty in obtaining convergence due to the low quality linear relaxation bounds. Another contribution of this thesis is the proposal of a single model that is able to deal with both the MOSP and with the Minimization of Order Spread Problem (MORP). This unified framework allows both problems to be jointly solved, by using a weighted objective function that included both original objectives. The second part of this thesis dealt with the development of heuristic strategies. Two solution strategies have been proposed. The first method proposes a heuristic conversion between MOSP and Traveling Salesman Problem (TSP) instances. This conversion relies the assignment distances to the TSP instance based on the degree of the vertices of the associated MOSP graph. Computational tests have shown that the proposed methodology is efficient, both in terms of solution quality (optimal solutions were obtained for 80.42% of the tested instances) and computational effort. The second method uses a decomposition idea. A cut is made in the graph associated with the original MOSP problem, yielding two smaller problems, which are solved. In some cases, the obtained combined solution can be prover optimal. Computational tests have shown the validity of the proposal and indicate new research opportunities

GOMES, R. F. de S. Aplicação da metaheurística tabu search na otimização de rotas de manutenção preventiva em campo. 2011. 108 f. Dissertação (Mestrado em Logística e Pesquisa Operacional) - Pró-Reitoria de Pesquisa e Pós-Graduação, Universidade Federal do Ceará, Fortaleza, 2011. / Submitted by Marlene Sousa (mmarlene@ufc.br) on 2012-10-26T14:32:46Z No. of bitstreams: 1 2011_dis_rfdesgomes.pdf: 1695034 bytes, checksum: cf3b9a4b04cd64169ae948a6d6884458 (MD5) / Approved for entry into archive by Marlene Sousa(mmarlene@ufc.br) on 2012-10-26T17:04:37Z (GMT) No. of bitstreams: 1 2011_dis_rfdesgomes.pdf: 1695034 bytes, checksum: cf3b9a4b04cd64169ae948a6d6884458 (MD5) / Made available in DSpace on 2012-10-26T17:04:37Z (GMT). No. of bitstreams: 1 2011_dis_rfdesgomes.pdf: 1695034 bytes, checksum: cf3b9a4b04cd64169ae948a6d6884458 (MD5) Previous issue date: 2011-12-09 / The aim of this paper was to propose an application based on the Metaheuristic Tabu Search (TS) to be used on FIELD PREVENTIVE MAINTENANCE SERVICES (FPMS) in order to get more logistics efficiency by routing maintenance sectors. Unlike services performed in industry, where all systems, machines and equipment are located practically in the same location, maintenance services in the field require an additional component directly related to cost, which refers to exactly offset between the base unit and jobsite. Services in the field can be considered a variation of the Travelling Salesman Problem (TSP) and its different approaches, like the DTRP (Dynamic Travelling Repairman Problem) proposed by Bertsimas and Van Ryzin. There is a huge demand for maintenance in the field, demonstrating its relevance: elevators, escalators, electronic devices for home-security, IT hardware support and others. The method was designed, implemented and tested in problems of the TSP-LIBRARY ranging from 17 up to 280 points. Good solutions were found in a acceptable processing time. The input data can be made by geographical coordinates or 2D-coordinates. For a real-world application, it was considered an Elevator Company and the results were also efficient, greatly reducing transportation cost and logistics used in the operation. / O objetivo deste trabalho foi propor uma aplicação baseada na metaheurística Busca Tabu (TS) para ser utilizada em serviços de manutenção preventiva em campo (FPMS) a fim de obter maior eficiência logística, através do roteamento de setores de manutenção. Ao contrário dos serviços realizados na indústria, onde todos os sistemas, máquinas e equipamentos estão localizados praticamente no mesmo local, serviços de manutenção em campo requerem um componente adicional diretamente relacionado ao custo, que se refere exatamente a diferença entre a unidade de base e local de trabalho. Serviços em campo podem ser considerados uma variação do Problema do Caixeiro Viajante (PCV) e suas diferentes abordagens, como o Problema Dinâmico do Reparador Viajante (DTRP - Dynamic Travelling Repairman Problem) proposto por Bertsimas e Van Ryzin. Em situações práticas do dia-a-dia existe uma enorme demanda por serviços de manutenção a serem realizados em campo, demonstrando sua relevância: elevadores, escadas rolantes, aparelhos segurança eletrônica residencial, suporte de TI à hardwares, entre outros. O método foi implementado e testado em problemas da biblioteca TSP-LIBRARY variando de 17 a 280 pontos. Boas soluções foram encontradas em um tempo de processamento aceitável. O input do problema leva em consideração duas formas: coordenadas geográficas ou coordenadas cartesianas. Para uma aplicação prática do mundo real, foi considerada uma empresa de manutenção em elevadores e os resultados também foram eficientes, reduzindo bastante os custos de transporte e a logística empregada na operação.

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2017-08-22T12:50:56Z No. of bitstreams: 1 texto completo.pdf: 2002096 bytes, checksum: 846f5e7b160234fc5880c038b656d3f6 (MD5) / Made available in DSpace on 2017-08-22T12:50:56Z (GMT). No. of bitstreams: 1 texto completo.pdf: 2002096 bytes, checksum: 846f5e7b160234fc5880c038b656d3f6 (MD5) Previous issue date: 2017-03-07 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho aborda o problema de flow shop scheduling não permutacional com trabalhadores heterogêneos (FSNPTH). Sendo este classificado como um problema multicomponente, uma vez que, combina dois problemas no qual o resultado de um afeta o outro. O FSNPTH é composto por dois problemas clássicos de otimização combinatória: alocação de trabalhadores em máquinas e o flow shop scheduling não permutacional (FSNP). O problema consiste em alocar trabalhadores hete- rogêneos em máquinas dispostas em série, na qual a heterogeneidade se dá pelo tempo gasto pelo trabalhador ao operar uma máquina. A alocação dos trabalha- dores definem os tempos de execução das tarefas do problema de FSNP. O objetivo do problema de FSNPTH é minimizar o tempo máximo de conclusão das tarefas, conhecido como makespan. Para resolve-lo, inicialmente é proposto a aplicação do método Proximity Search (PS) para tentar determinar soluções ótimas para o pro- blema utilizando o modelo de programação linear inteira mista 0-1 (PLIM). Esse método consiste em substituir a função objetivo por uma função de proximidade e adicionar uma restrição de corte no modelo. Iterativamente o novo modelo é resolvido e a restrição de corte é atualizada. Isso garante que PS limite o espaço de busca e identifique as soluções ótimas. Foram desenvolvidas três versões do PS denotadas por P S 1 , P S 2 e P S 2RIN S . Dado que o problema pertence à classe NP-Difícil e é considerado de difícil resolução de maneira exata, foram desenvolvi- dos dois algoritmos híbridos, VNS-IG e TS-IG, a fim de obter soluções de forma aproximada de alta qualidade em baixo tempo computacional. Esses algoritmos combinam as meta-heurísticas Variable Neighborhood Search (VNS) e Busca Tabu (TB, do inglês Tabu Search) com o Iterated Greedy (IG). Experimentos computa- cionais e análises estatísticas foram realizados a fim de comparar o desempenho das versões do PS e dos algoritmos propostos. De acordo com os experimentos computacionais, as versões do PS obtiveram melhorias na qualidade da solução obtida e redução no tempo computacional se comparado a resolução do modelo matemático pelo solver IBM ILOG CPLEX. Além disso os experimentos realiza- dos mostram que algoritmos propostos são significativamente superiores ao melhor algoritmo da literatura (Scatter Search) em relação a dois fatores: qualidade das soluções e tempo de execução. / The current work addresses the non-permutation flow shop scheduling problem with heterogeneous workers (Het-FSSP), which is defined as a multicomponent problem, since it combines two problems where the result of one affects the other. Het-FSSP consists of two classical combinatorial optimization problems: machine worker allocation and non-permutation flow shop scheduling (NPFSS). The pro- blem is to allocate heterogeneous workers in machines arranged in series, in which the heterogeneity is due to the time spent by the worker when operating a ma- chine. The allocation of workers defines the periods of execution of the jobs of the NPFSS problem. The goal of the Het-FSSP problem is to minimize the maximum job completion time, which is known as makespan. In order to solve this problem, it is initially proposed to apply the Proximity Search (PS) method to try to de- termine optimal solutions for the problem using mixed integer programing (MIP) model. This method consists of replacing the objective function with a proximity function and adding a cut-off constraint on the model. Then, by iteration, the new model is resolved and the cut restriction is updated. This ensures that PS limits the search space and identifies optimal solutions. Three PS versions denoted by P S 1 , P S 2 and P S 2RIN S have been developed. Since the problem belongs to the NP-Difficult class and is considered to be difficult to solve exactly, two hybrid algorithms, VNS-IG and TS-IG, were developed in order to obtain approximate solutions of high quality in low computational time. These algorithms combine the meta-heuristics Variable Neighborhood Search (VNS) and Tabu Search (TS) with Iterated Greedy (IG). Computational experiments and statistical analyzes were performed in order to compare the performance of PS versions and the proposed algorithms. The computational experiments results suggest that the PS versions acquired improvements in the quality of the solution obtained and also reduced computational time spent compared to the resolution of the mathematical model by the IBM ILOG CPLEX solver. In addition, the experiments performed have shown that the proposed algorithms are significantly superior to the best algorithm found in the literature (Scatter Search) in relation to two factors: solution quality and execution time.