Proposição e análise de modelos híbridos para o problema de escalonamento de produção em oficina de máquinas

Nas últimas décadas, o problema de escalonamento da produção em oficina de máquinas, na literatura referido como JSSP (do inglês Job Shop Scheduling Problem), tem recebido grande destaque por parte de pesquisadores do mundo inteiro. Uma das razões que justificam tamanho interesse está em sua alta complexidade. O JSSP é um problema de análise combinatória classificado como NP-Difícil e, apesar de existir uma grande variedade de métodos e heurísticas que são capazes de resolvê-lo, ainda não existe hoje nenhum método ou heurística capaz de encontrar soluções ótimas para todos os problemas testes apresentados na literatura. A outra razão basea-se no fato de que esse problema encontra-se presente no diaa- dia das indústrias de transformação de vários segmento e, uma vez que a otimização do escalonamento pode gerar uma redução significativa no tempo de produção e, consequentemente, um melhor aproveitamento dos recursos de produção, ele pode gerar um forte impacto no lucro dessas indústrias, principalmente nos casos em que o setor de produção é responsável por grande parte dos seus custos totais. Entre as heurísticas que podem ser aplicadas à solução deste problema, o Busca Tabu e o Multidão de Partículas apresentam uma boa performance para a maioria dos problemas testes encontrados na literatura. Geralmente, a heurística Busca Tabu apresenta uma boa e rápida convergência para pontos ótimos ou subótimos, contudo esta convergência é frequentemente interrompida por processos cíclicos e a performance do método depende fortemente da solução inicial e do ajuste de seus parâmetros. A heurística Multidão de Partículas tende a convergir para pontos ótimos, ao custo de um grande esforço computacional, sendo que sua performance também apresenta uma grande sensibilidade ao ajuste de seus parâmetros. Como as diferentes heurísticas aplicadas ao problema apresentam pontos positivos e negativos, atualmente alguns pesquisadores começam a concentrar seus esforços na hibridização das heurísticas existentes no intuito de gerar novas heurísticas híbridas que reúnam as qualidades de suas heurísticas de base, buscando desta forma diminuir ou mesmo eliminar seus aspectos negativos. Neste trabalho, em um primeiro momento, são apresentados três modelos de hibridização baseados no esquema geral das Heurísticas de Busca Local, os quais são testados com as heurísticas Busca Tabu e Multidão de Partículas. Posteriormente é apresentada uma adaptação do método Colisão de Partículas, originalmente desenvolvido para problemas contínuos, onde o método Busca Tabu é utilizado como operador de exploração local e operadores de mutação são utilizados para perturbação da solução. Como resultado, este trabalho mostra que, no caso dos modelos híbridos, a natureza complementar e diferente dos métodos Busca Tabu e Multidão de Partículas, na forma como são aqui apresentados, da origem à algoritmos robustos capazes de gerar solução ótimas ou muito boas e muito menos sensíveis ao ajuste dos parâmetros de cada um dos métodos de origem. No caso do método Colisão de Partículas, o novo algorítimo é capaz de atenuar a sensibilidade ao ajuste dos parâmetros e de evitar os processos cíclicos do método Busca Tabu, produzindo assim melhores resultados.

Metaheurística para o Problema de Planejamento de Redes de Transmissão de Energia Elétrica com Redimensionamento

Com o passar do tempo, a demanda elétrica de diversas áreas varia tornando necessária a construção de novos geradores elétricos e a expansão da rede de transmissão de energia elétrica. Nesta dissertação, focamos no problema de expansão da rede de transmissão, assumindo que novos geradores estão construídos para suprir as novas demandas. Essa expansão exige altos investimentos que precisam ser cuidadosamente planejados. O problema pode ser modelado como um problema de otimização não linear inteira mista e pertence à classe dos problemas NP-difíceis. Desta forma, uma abordagem heurística pode ser adequada para a sua solução pois pode vir a fornecer boas soluções em tempo computacional aceitável. Esta dissertação se propõe a apresentar um estudo do problema de planejamento da expansão de redes de transmissão de energia elétrica estático e multiestágio. Mostramos o que já existe na literatura para o que é chamado de problema sem redimensionamento e as inovações feitas por nós para o problema com redimensionamento. Quanto aos métodos de solução, utilizamos a metaheurística GRASP para o problema estático e combinamos o GRASP com o procedimento Backward-Forward quando falamos em problema multiestágio. Nesta dissertação comparamos os resultados computacionais obtidos com resultados encontrados na literatura.

A legitimação jurídico-moral da regulação estatal à luz da premissa liberal republicana: autonomia privada, igualdade e autonomia pública. Estudo de caso sobre as regulações paternalistas

A presente tese tem por objetivo principal estudar a legitimação jurídico-moral da regulação estatal. Trata-se de tema de grande relevância e extrema atualidade em decorrência de dois fatores. Por um lado, desde o fenômeno da virada kantiana e da retomada da preocupação com o estabelecimento de uma teoria da justiça, tornou-se necessária a análise de justificação jurídico-moral de toda e qualquer instituição político-jurídica positivada. Por outro lado, entre as inúmeras instituições político-jurídicas positivadas, cresce cada vez mais a utilização das medidas jurídicas regulatórias, através das quais o Poder Público direciona ou controla a conduta dos agentes com o intuito de atingir determinada finalidade. Instituto econômico que é, ao interferir na alocação de riquezas, bens e serviços no mercado, a regulação estatal há tempos já vem sendo objeto de análise em uma perspectiva de legitimação econômica. Tradicionalmente, ainda dentro do paradigma da racionalidade, os economistas sempre apontaram as falhas de mercado como as razões a justificar as regulações estatais em um viés econômico. Mais recentemente, por sua vez, os adeptos da economia comportamental, rompendo ou relativizando as lições da Rational Choice Theory, têm apontado também as ações irracionais em heurística como razões a justificar as regulações estatais em um viés econômico. Ocorre, entretanto, que a regulação estatal é um instituto interdisciplinar. Ao direcionar ou controlar a conduta dos indivíduos, limitando ou implementando direitos e liberdades, a regulação constitui instituto simultaneamente jurídico e moral. A presente tese, portanto, buscará apresentar as razões a servir de justificação para a regulação estatal em uma perspectiva jurídico-moral. Neste ponto, adotar-se-á como paradigma de aferição de legitimação jurídico-moral das instituições político-jurídicas positivadas (entre as quais as regulações estatais) um liberalismo-republicano, consistente na compatibilização do liberalismo-igualitário com um republicanismo moderado. Desta forma, o estudo buscará defender a possibilidade de a legitimação jurídico-moral das diversas regulações estatais encontrar fundamento em um ou alguns de três valores jurídico-morais: a autonomia individual privada, as condições igualitárias e a autonomia pública. No que diz respeito à implementação da autonomia individual privada e das condições igualitárias, primeiramente, a tese defenderá a possibilidade de ser realizada uma nova leitura jurídico-moral dos institutos econômicos das falhas de mercado e das ações irracionais em heurística. Neste sentido, o conceito de falhas de mercado e o conceito de ações irracionais em heurística, em uma leitura jurídico-moral como razões a justificar a legitimação das regulações estatais, devem ser entendidos como situações em que o atuar livre dos agentes no mercado viole ou deixe de implementar os valores jurídico-morais fundamentais da autonomia individual privada e das condições igualitárias. Ainda no que diz respeito às influências liberal-igualitárias, a tese sustentará que, mesmo na inexistência de falhas de mercado ou de ações irracionais em heurística, será possível o estabelecimento de regulações estatais que encontrem justificação no valor jurídico-moral fundamental da igualdade, desde que tais regulações estejam destinadas a implementar as condições igualitárias mínimas necessárias à manutenção da própria autonomia individual privada e da dignidade humana. Por outro lado, no que diz respeito às influências republicanas, será exposto que as regulações estatais podem encontrar legitimação jurídico-moral também no valor jurídico-moral fundamental da autonomia pública. A saber, as regulações podem se encontrar legitimadas jurídico-moralmente quando da implementação dos projetos e políticas deliberados pelos cidadãos e pela sociedade no exercício da soberania popular, desde que tais projetos coletivos não violem os requisitos mínimos de dignidade humana dos indivíduos. A tese defenderá que os princípios da proporcionalidade e da igualdade podem exercer um papel de destaque na análise de legitimação jurídico-moral das regulações estatais. O princípio da proporcionalidade, neste ponto, será útil instrumental metodológico na aferição de legitimação jurídico-moral de uma medida regulatória em uma perspectiva interna, quando da aferição da relação estabelecida entre os meios e os fins da regulação. O princípio da igualdade, por sua vez, será útil instrumental metodológico na aferição de legitimação jurídico-moral de uma medida regulatória em uma perspectiva comparativa entre as diversas medidas regulatórias existentes. Por fim, uma vez enfrentados os pontos mais sensíveis pertinentes à justificação de toda e qualquer medida regulatória bem como estabelecida uma teoria geral acerca da legitimação jurídico-moral da regulação estatal, a presente tese realizará um estudo de caso acerca da legitimação jurídico-moral especificamente das regulações que utilizam argumentos de natureza paternalista. Trata-se de regulações que, ao direcionar a conduta de agentes com o intuito de zelar por bens, direitos e interesses destes próprios indivíduos cuja liberdade é restringida, apresentam-se extremamente controversas. Será exposto que, desde a clássica obra On Liberty de JONH STUART MILL, o paternalismo jurídico vem sendo tradicionalmente associado a uma conotação pejorativa de violação aos valores jurídico-morais fundamentais. A tese, porém, adotará posição segundo a qual as regulações paternalistas podem eventualmente encontrar legitimação jurídico-moral na promoção ou proteção dos valores jurídico-morais fundamentais da autonomia individual privada e da igualdade. Além disto, defenderá o estudo que os institutos econômicos das falhas de mercado da assimetria de informações e dos problemas de coordenação bem como os institutos econômicos das ações irracionais em heurística, adotados na nova leitura jurídico-moral proposta, servirão de instrumental útil na identificação das situações em que tais regulações paternalistas se encontram legitimadas jurídico-moralmente diante da premissa liberal-republicana.

Roteamento e alocação de comprimento de onda em redes WDM segundo algoritmo baseado em regras da natureza.

O surgimento de novos serviços de telecomunicações tem provocado um enorme aumento no tráfego de dados nas redes de transmissão. Para atender a essa demanda crescente, novas tecnologias foram desenvolvidas e implementadas ao longo dos anos, sendo que um dos principais avanços está na área de transmissão óptica, devido à grande capacidade de transporte de informação da fibra óptica. A tecnologia que melhor explora a capacidade desse meio de transmissão atualmente é a multiplexação por divisão de comprimento de onda ou Wavelength Division Multiplexing (WDM) que permite a transmissão de diversos sinais utilizando apenas uma fibra óptica. Redes ópticas WDM se tornaram muito complexas, com enorme capacidade de transmissão de informação (terabits por segundo), para atender à explosão de necessidade por largura de banda. Nesse contexto, é de extrema importância que os recursos dessas redes sejam utilizados de forma inteligente e otimizada. Um dos maiores desafios em uma rede óptica é a escolha de uma rota e a seleção de um comprimento de onda disponível na rede para atender uma solicitação de conexão utilizando o menor número de recursos possível. Esse problema é bastante complexo e ficou conhecido como problema de roteamento e alocação de comprimento de onda ou, simplesmente, problema RWA (Routing and Wavelentgh Assignment problem). Muitos estudos foram realizados com o objetivo de encontrar uma solução eficiente para esse problema, mas nem sempre é possível aliar bom desempenho com baixo tempo de execução, requisito fundamental em redes de telecomunicações. A técnica de algoritmo genético (AG) tem sido utilizada para encontrar soluções de problemas de otimização, como é o caso do problema RWA, e tem obtido resultados superiores quando comparada com soluções heurísticas tradicionais encontradas na literatura. Esta dissertação apresenta, resumidamente, os conceitos de redes ópticas e de algoritmos genéticos, e descreve uma formulação do problema RWA adequada à solução por algoritmo genético.

Síntese evolucionária de circuitos sequenciais inspirada nos princípios da computação quântica.

Esta dissertação investiga a aplicação dos algoritmos evolucionários inspirados na computação quântica na síntese de circuitos sequenciais. Os sistemas digitais sequenciais representam uma classe de circuitos que é capaz de executar operações em uma determinada sequência. Nos circuitos sequenciais, os valores dos sinais de saída dependem não só dos valores dos sinais de entrada como também do estado atual do sistema. Os requisitos cada vez mais exigentes quanto à funcionalidade e ao desempenho dos sistemas digitais exigem projetos cada vez mais eficientes. O projeto destes circuitos, quando executado de forma manual, se tornou demorado e, com isso, a importância das ferramentas para a síntese automática de circuitos cresceu rapidamente. Estas ferramentas conhecidas como ECAD (Electronic Computer-Aided Design) são programas de computador normalmente baseados em heurísticas. Recentemente, os algoritmos evolucionários também começaram a ser utilizados como base para as ferramentas ECAD. Estas aplicações são referenciadas na literatura como eletrônica evolucionária. Os algoritmos mais comumente utilizados na eletrônica evolucionária são os algoritmos genéticos e a programação genética. Este trabalho apresenta um estudo da aplicação dos algoritmos evolucionários inspirados na computação quântica como uma ferramenta para a síntese automática de circuitos sequenciais. Esta classe de algoritmos utiliza os princípios da computação quântica para melhorar o desempenho dos algoritmos evolucionários. Tradicionalmente, o projeto dos circuitos sequenciais é dividido em cinco etapas principais: (i) Especificação da máquina de estados; (ii) Redução de estados; (iii) Atribuição de estados; (iv) Síntese da lógica de controle e (v) Implementação da máquina de estados. O Algoritmo Evolucionário Inspirado na Computação Quântica (AEICQ) proposto neste trabalho é utilizado na etapa de atribuição de estados. A escolha de uma atribuição de estados ótima é tratada na literatura como um problema ainda sem solução. A atribuição de estados escolhida para uma determinada máquina de estados tem um impacto direto na complexidade da sua lógica de controle. Os resultados mostram que as atribuições de estados obtidas pelo AEICQ de fato conduzem à implementação de circuitos de menor complexidade quando comparados com os circuitos gerados a partir de atribuições obtidas por outros métodos. O AEICQ e utilizado também na etapa de síntese da lógica de controle das máquinas de estados. Os circuitos evoluídos pelo AEICQ são otimizados segundo a área ocupada e o atraso de propagação. Estes circuitos são compatíveis com os circuitos obtidos por outros métodos e em alguns casos até mesmo superior em termos de área e de desempenho, sugerindo que existe um potencial de aplicação desta classe de algoritmos no projeto de circuitos eletrônicos.