(OC-SIAC) 
(OC-SIAC)
Índice: 1. Introdução 2. Objetivos e Descrição da Pesquisa 2.1. Sistemas Flexíveis de Manufatura 2.2. Sistemas de Informações Geográficas 2.3. Sistemas Automáticos para Cortes e Empacotamento 3. Resultados atuais e propostas 3.1. Sistemas Flexíveis de Manufatura 3.2. Sistemas de Informações Geográficas 3.3. Sistemas Automáticos para Cortes e Empacotamento 4. Descrição da equipe 5. Cronograma de execução 6. Bibliografia
Este projeto tem como objetivo a pesquisa e desenvolvimento de algoritmos eficientes para problemas de Otimização Combinatória que ocorrem em alguns Sistemas de Informação Assistidos por Computador.
Os sistemas a serem estudados são os seguintes:
- Sistemas Flexíveis de Manufatura,
- Sistemas de Informações Geográficas, e
- Sistemas Automáticos para Cortes e Empacotamento.
Problemas de Otimização Combinatória aparecem quando temos que selecionar de um conjunto discreto e finito de dados o melhor subconjunto que satisfaz a determinados critérios. Por exemplo, selecionar o melhor conjunto de ítens indivisíveis a serem transportados em um veículo de espaço e capacidade limitados.
Um fato que tem motivado os estudos na área é a intratabilidade da maioria dos problemas de Otimização Combinatória. Até o momento não se conhecem abordagens eficientes, em tempo de processamento e/ou memória, de solução geral para esses problemas.
Tais problemas ocorrem em várias áreas, em sistemas produtivos em geral, e em particular nos sistemas citados. A seleção das áreas de aplicação obedeceu aos seguintes critérios:
- Atualidade dos temas,
- Experiência teórica adquirida,
- A interdependencia entre os temas, e
- Uso comum de automação assistida por computador.
Alguns dos problemas de otimização combinatória encontrados nas tres áreas são considerados clássicos, tais como: mochila, cobertura de conjuntos, "clustering", "scheduling" e outros. Nos interessamos pelos problemas citados, mas também, e principalmente pelos específicos das aplicações.
Sistemas Flexíveis de Manufatura (SFM) podem ser definidos como um conjunto de máquinas ligadas por um sistema flexível de manipulação de material (em geral robot ou veículos de guiagem automática), todos controlados por um sistema computacional (Kusiak, 1990). São fartos em problemas de "clustering" e "scheduling", também em problemas de "layout". Aqui porém são tratados obedecendo a aplicação específica, produzindo mesmo problemas novos que não existiam até recentemente, tais como a otimização do "scheduling" combinado com a seleção de partes a serem manufaturadas (Crama, 1995).
Sistemas de Informações Geográficas (SIG) integram Computação Gráfica a uma base de dados. São poderosas ferramentas de análise e planejamento espacial. O comércio de SIGs representa um dos segmentos que mais crescem nos Estados Unidos, tornando-se crítica a integração de técnicas e filosofia da Pesquisa Operacional nesta tecnologia (Fischbeck, 1994). Os problemas de Otimização Combinatória aparecem combinados à análise de redes de fluxo de dados (estradas, ruas, canais de comunicação, e outras), representados por segmentos de linha. Os algoritmos clássicos de otimização de fluxo em redes são diretamente aplicáveis. Problemas mais complexos de localização de centros (escolas, ambulatórios, e outros) e roteamento de veículos podem também ser tratados levando-se em conta várias informações espaciais.
Sistemas Automáticos para Cortes e Empacotamento apresentam problemas relacionados a determinação de padrões de corte (empacotamento) de unidades de material (objetos) de modo a produzirem (comporem) um conjunto de unidades menores (itens), satisfazendo a determinadas restrições. Dependendo do tipo de objeto (barra, placas, caixas, e outros) temos os chamados problemas unidimensional, bidimensional, tridimensional e outros. Tais sistemas se beneficiam muito de processos automatizados, como maquinas de controle numérico e sistemas CAD para cortes irregulares. Aqui também vários problemas clássicos da otimização combinatória aparecem, tais como, mochila, cobertura de conjuntos e outros. Os problemas específicos da área são propícios ao uso de heurísticas.
2. Objetivos e Descrição da Pesquisa
Este projeto visa promover e contribuir para o desenvolvimento científico e tecnológico bem como a formação de recursos humanos na área de Otimização Combinatória. Seu objetivo principal está no desenvolvimento de algoritmos para resolução de problemas de natureza combinatória que surgem em alguns Sistemas de Informação Assistidos por Computador (SIAC).
Optou-se por contemplar tres sistemas para a pesquisa: Sistema Flexíveis de Manufatura (SFM), Sistemas de Informações Geográficas (SIG) e os Sistemas Automáticos para Cortes e Empacotamento (SACE). Os sistemas escolhidos para compor a pesquisa foram os que consideramos relevantes em termos de aplicação prática e nos quais acreditamos poder contribuir para o estado-da-arte, com resultados que serão de interesse para as comunidades científicas nacional e internacional. Outro aspecto levado em conta foi a atualidade dos temas e sua vinculação ao uso de processos totalmente assistidos por computador.
As contribuições deste projeto para o desenvolvimento científico e tecnológico das áreas serão feitas principalmente através da identificação e desenvolvimento de modelos, padrões, técnicas e procedimentos que resolvam algumas classes de problemas de otimização combinatória.
2.1. Sistemas Flexíveis de Manufatura
Em ambientes automatizados de manufatura, modelos de planejamento e sequenciamento da produção exibem várias características que diferem dos sistemas tradicionais de produção. Por exemplo, sistemas automatizados apresentam frequentemente restrições de ferramentas, que refletem a possibilidade de uma máquina usar diferentes ferramentas para executar operações sucessivas, considerando os limites impostos pelo tamanho do magazine de ferramentas. Em geral, estes modelos levam em conta também a participação de sistemas flexíveis para manipulação de materiais, cujas atividades devem ser sincronizadas com as operações de máquina visando a otimização de utilização do sistema.
Vários problemas interessantes de otimização combinatória surgem neste ambiente (veja Crama (1995) para uma descrição detalhada de alguns desses problemas). Estaremos interessados em tres problemas relacionados e que levam em conta a restrição de ferramentas para uma ou mais máquinas de uma célula de manufatura. Os problemas são:
- Problemas de grupamento ("batch") de partes : Formação de grupos de partes (tarefas) com características (ferramentas) comuns, de forma que possam ser processadas diretamente sem interrupções (troca de ferrementas). Restringe-se a análise ao período entre sucessivas trocas de ferrementas. O objetivo está em selecionar um "melhor" agrupamento das partes;
- Problemas de grupamento de partes e ferramentas: O problema geral que ocorre é o de processar o conjunto todo de partes o mais eficientemente possível. Uma maneira de satisfazer este critério será o de encontrar uma partição das partes em número mínimo de grupamentos. De forma equivalente, pode-se interpretar como a busca pelo menor número de instantes em que ocorre uma ou mais trocas de ferramentas. Este objetivo é razoável nos casos da existência de dispositivos automáticos de troca de ferramentas que podem trocar um conjunto de ferramentas ao mesmo tempo;
- Problemas de troca de ferramentas: Em algumas situações o número de trocas de ferramentas no processo se apresenta como uma medida de performance mais apropriada que o número de intantes de troca. É o caso de quando o tempo de "setup" é proporcional ao número de trocas de ferramentas.
Os tres problemas aparecem muito bem descritos em Crama (1995), que salienta suas dificuldades (são em geral NP-hard) e as principais abordagens na busca de soluções.
Neste projeto de pesquisa estaremos interessados nos tres problemas, com a participação de alunos de mestrado e doutorado.
2.2. Sistemas de Informações Geográficas
O desenvolvimento de sistemas computacionais para aplicações gráficas e de imagens vem influenciando de maneira crescente diversas áreas como cartografia, mapeamento, análise de recursos naturais, agricultura, planejamento urbano e regional.
Esta tecnologia torna possível a automatização de tarefas realizadas manualmente e facilita a realização de análises complexas, através da possibilidade de integração de dados de diversas fontes e da criação de um banco de dados geocodificado. Os sistemas para tal fim são denominados Sistemas de Informação Geográficas, Sistemas de Análise Geo-ambiental ou ainda Sistemas para Cartografia Automatizada.
Um sistema de informação consiste em uma série de operações que compreendem desde o planejamento das observações e coleta de dados, até o armazenamento e análise dos dados. Utilizam-se as informações resultantes para planejamento e decisões. Por exemplo, um mapa é um tipo de sistema de informação onde os dados foram armazenados e analisados e a informação resultante é útil para as mais variadas aplicações.
Um Sistema de Informações Geográficas (SIG) é um sistema de informação apropriado para trabalhar com dados referenciados através de coordenadas geográficas. Dentro deste conceito, define-se um SIG como:
- Um sistema de base de dados específico, para dados referenciados espacialmente;
- Um conjunto de operações para se trabalhar com os dados e
- Uma ferramenta para manipular e armazenar dados não-espaciais.
Estaremos interessados principalmente na análise de redes usando as potencialidades dos SIG. Ruas (ou estradas, canais de comunicação e outros) são representados através de segmentos de linhas ligados entre si formando uma rede. A vantagem em se usar um SIG está na habilidade de se associar a cada arco na rede um conjunto de atributos que de outra maneira não estaria disponível para a análise. Por exemplo, as opções padrões de minimizar a distância e tempo percorridos em uma rota estão imediatamente disponíveis. Entretanto, usando informações de um censo demográfico, será possível usar características econômicas e de população para uma área nas redondezas de cada arco.
Nosso interesse está em adaptar algoritmos clássicos e propor novos algoritmos para roteamento de veículos e localização de facilidades, usando as características dos SIG.
2.3. Sistemas Automáticos para Cortes e Empacotamento
Cortes e empacotamentos de materiais contituem componentes importantes na formação do custo final dos produtos, e claramente, qualquer redução de custo é sempre interessante neste cenário econômico competitivo atual. Temos interesse em disseminar os resultados obtidos, capacitando as indústrias nacionais que tradicionalmente usam ferramentas automáticas para embalagem e corte, metalúrgicas, madeireiras, etc.
Os tópicos principais a serem estudados são:
- Problemas de sequenciamento de padrões de corte e empacotamento: Uma possível maneira de resolver este problema é modelá-lo como um problema de programação matemática e explorar sua estrutura. Outra alternativa é desenvolver um método de busca de soluções com as mesmas propriedades que as soluções ótimas devem satisfazer. Problemas de minimização de ttrocas de ferramentas no contexto de SFM estão diretamente relacionados com esse problema;
- Problemas de cortes guilhotinados: Cortes tipo guilhotina são os mais comuns na indústria e também os mais estudados. É o problema de combinar um numero limitado de retângulos dados de forma a preencher um (ou mais) retângulo (s) maior (es), sem sobreposição, com a menor perda possível. Pretende-se desenvolver novas heurísticas para o problema usando abordagem de grafos e estruturas de listas dinâmicas.
3. Resultados atuais e propostas
Problemas de Otimização Combinatória são considerados altamente complexos e custosos do ponto de vista computacional. Em geral utilizam-se de Heurísticas para obter uma "boa" aproximação das soluções dos problemas. Muitas vezes essas aproximações são suficientes para o propósito do usuário. Senão podem fazer parte de métodos, considerados exatos, que encontram soluções ótima dos problemas. A utilização de soluções heurísticas como parte de métodos exatos tem conduzido à solução de muitos problemas da Otimização Combinatória.
Propõe-se neste projeto a pesquisar e desenvolver Heurísticas e Métodos Exatos para alguns Problemas de Otimização Combinatória que surgem nos seguintes sistemas automatizados:
- Sistemas Flexíveis de Manufatura (SFM);
- Sistemas de Informacões Geográficas (SIG), e
- Sistemas Automáticos para Cortes e Empacotamento (SACE).
Uma proposta geral para as áreas será:
Proposta geral
Pretende-se desenvolver um sistema computacional composto de uma biblioteca programas de "linkagem" dinâmica para a solução de problemas de otimização combinatória nas áreas de manufatura, cortes e empacotamento e informações geográficas.
As propostas e os resultados específicos que já vem sendo obtidos para cada uma das áreas estão descritos a seguir.
3.1. Sistemas Flexíveis de Manufatura
Resultados atuais:
Os problemas de grupamento de partes, grupamento de partes e ferramentas e o de troca de ferramentas foram tratados na tese de doutorado de Arthur Tórgo Gomez, orientada por Luiz Antonio N. Lorena. No trabalho novas versões da metaheurística "busca tabu" foram empregadas na solução dos problemas.
Propostas:
Não se tem conhecimento ainda de nenhum procedimento exato sugerido na literatura que resolva o problema de troca de ferramentas e que tenha apresentado um bom desempenho em termos de temo e memória computacional. Pretende-se implementar um método exato, tipo "Branch & Bound", para o problema, e espera-se que ele apresente desempenho aceitável.
3.2. Sistemas de Informações Geográficas
Resultados atuais:
Os problemas de Localização de Facilidades e Roteamento estão sendo considerados usando uma proposta recente de Heurísticas Baseadas em Relaxações (HBR).
Nas HBR cada solução relaxada é tornada viável ao problema considerado. Uma sequência de soluções é obtida, em geral em combinação com uma otimização por subgradientes. Seus resultados estão entre os melhores da literatura.
Uma HBR clássica usa como relaxação a Relaxacão Lagrangeana (RL) (veja Beasley (1993)). Em 1988, foi proposta por Lorena e Plateau (Lorena e Plateau (1990-)) o uso da Relaxação "Surrogate" (RS) nas HBR. Como característica principal das HBR baseadas em RS, obteve-se os mesmos excelentes resultados das baseadas em LR, mas com metade do tempo computacional. Isso foi comprovado nos trabalhos de Lorena e Lopes (Lorena e Lopes (1994)), Lorena e Narciso (Lorena e Narciso (1996)) e recentemente em Senne e Lorena (Senne e Lorena (1996)). Os tres problemas estudados, cobertura de conjuntos, problema generalizado de atribuição e p-medianas são problemas clássicos muito importantes e aparecem em muitas das aplicações da área.
Outros excelentes resultados foram obtidos com o uso de metaheurísticas, principalmente Algoritmos Genéticos, aplicadas ao problema de cobertura de conjuntos (veja Lorena e Lopes (1995)).
Propostas:
Pretende-se continuar com o uso da combinação HBR/RS para outros problemas da área (caixeiro viajante), bem como formalizar a teoria como tese de doutorado de Marcelo Gonçalves Narciso, orientada por Luiz A. N. Lorena.
Também pretende-se continuar e incentivar a cooperação com os pesquisadores Edson Senne da FEG/UNESP e Roberto Galvão da COPPE. Alunos de mestrado e doutorado poderão vir a explorar os temas. Pretende-se ainda usar a cooperação de um bolsista recém-doutor.
3.3. Sistemas Automáticos para Cortes e Empacotamento
Resultados atuais:
Na área de sequenciamento de padrões de cortes, os resultados obtidos na tese do Arthur Tórgo Gomez (veja ítem 3.1.) são diretamente aplicáveis dado a semelhança dos problemas.
Os cortes guilhotinados estão sendo explorados usando uma nova heurística construtiva de busca que armazena os padrões de corte em uma lista dinâmica, cujo critério de armazenamento (porcentagem de perda) vai tornando-se cada vez mais restritivo a medida que a busca se desenvolve. A nova heurística, chamada Heurística de Lista Dinâmica (HLD) foi aplicada com sucesso nos trabalhos de Lorena e Lopes (Lorena e Lopes (1995)).
A metaheurística "busca tabu" foi utilizada com grande sucesso em um problema geral de "layout". Um retângulo que deve ser particionado em retangulos menores, que conservam suas áreas mas que podem admitir medidas diferentes, e que ainda admitem a inclusão de áreas mortas. Os trabalhos de Furtado e Lorena (Furtado e Lorena (1995)) descrevem a aplicação.
Propostas:
Pretende-se dar continuidade ao desenvolvimento dos algoritmos para sequenciamento de padrões, cortes guilhotinados e "layout".
O sequenciamento continuará a ser tratado na tese de Arthur T. Gomez. A heurística HLD está sendo generalizada para uma metaheurística que seria aplicável na maioria dos problemas citados. Esta formalização será desenvolvida como tese de doutorado por Fábio Belo Lopes, com a orientação de Luiz A. N. Lorena. Os problemas de "layout" continuarão a ser estudados na tese de doutorado de João Carlos de Oliveira, com a orientação de Luiz A. N. Lorena.
Também pretende-se continuar e incentivar a cooperação com os pesquisadores Reinaldo Morabito da UFSCAR, Marcos Arenales da USP/S.Carlos e Horácio H. Yanasse do LAC/INPE. Alunos de mestrado e doutorado poderão vir a explorar os temas.
Dois alunos de mestrado estão iniciando dissertação nas áreas. Específicamente, usando a HLD para cortes guilhotinados com multiplos paineis, e o uso da HLD no problema de coloração de grafos. Pretende-se ainda usar a cooperação de um bolsista recém-doutor.
A equipe será composta por:
Coordenador: - Dr. Luiz Antonio Nogueira Lorena
Pesquisador Titular - LAC/INPE
Colaboradores: - 1 Recém-doutor a ser admitido com bolsa CNPq;
- Bolsistas de Iniciação científica:
Fabio Belo Lopes, Geraldo Ribeiro Filho, Joao Carlos Furtado e Marcelo Goncalves Narciso;
Mestrado
Andre Pulcherio de Oliveira e Sousa e Henrique O. Q. Aquino
Atividades básicas para períodos de um ano:
(válidas para os anos 1 e 2, com as devidas adaptações)
- Pesquisa e implementação de algoritmos eficientes para Problemas de Otimização Combinatória;
- Pesquisa sobre novas aplicações dos métodos propostos;
- Apresentação dos resultados obtidos em Congressos Internacionais e Nacionais, bem como a publicação em periódicos de circulação Internacional e Nacional;
- Orientações de dissertações e teses.