1. Introdução
 
 

O projeto OC-SIAC (Otimização Combinatória em Sistemas de Informação Assistidos por Computador) foi aprovado em julho de 1996 pelo CNPq, área de Engenharia de Produção/Pesquisa Operacional, recebendo o número CNPq 520844/96-3. .
 
 

Nesta segunda fase do projeto, denominada OC-SIAC 2, objetivo maior será o de continuar 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. Outros objetivos estão na formação de recursos humanos e pesquisa e desenvolvimento conjunto com outros colegas pesquisadores da área. Um objetivo complementar será o de basear nossos procedimentos com a participação e/ou coordenação em quatro projetos temáticos nas áreas correlatas ao projeto. Neste caso decidiu-se pela continuação apenas pedindo a renovação da bolsa de produtividade e pesquisa de Luiz Antonio Nogueira Lorena. Os recursos necessários para a execução do projeto OC-SIAC 2 estarão cobertos pelos projetos temáticos acima referidos.
 
 

Os sistemas que estão sendo 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 itens 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 interdependência 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 três 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 freqüentemente 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 três 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 ferramentas). Restringe-se a análise ao período entre sucessivas trocas de ferramentas. 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 instantes de troca. É o caso de quando o tempo de "setup" é proporcional ao número de trocas de ferramentas.
 
 

Os três 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.
 
 

Nesta segunda fase do projeto, além dos problemas citados estaremos interessados em estudar os problemas que aparecem na formação de células de manufatura, no contexto da teoria de grupos, que aparecem descritos no trabalho de Heragu (1994).
 
 
 
 

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 constituem 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 trocas 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 continuar o desenvolvimento de novas heurísticas para o problema usando abordagem de grafos e algoritmos genéticos.
 
 
 
 
 
 
 
 

3. Resultados do Projeto OC-SIAC
 
 

Principais resultados obtidos (por área)
 
 

Sistemas Flexíveis de Manufatura
 
 

Resultados:
 
 

Tese de doutorado:

Orientador: Dr. Luiz Antonio N. Lorena

Apresentada em dezembro de 1996.
 
 

Resumo:

Resultados:
 
 

INPE

Resultados:
 
 

bolsa de produtividade e pesquisa

Luiz Antonio Nogueira Lorena
 
 
 

Trabalhos	Internacionais	Nacionais	Total parcial	Orientação	Final	Em andamento	Total parcial
Publicados em revistas e/ou capítulos de livros	3	2	5	Doutorado	3	1	4
Aceitos para publicação	1		1	Mestrado	1	1	2
Submetidos para revistas	1	2	3	Iniciação científica		2	2
Apresentados em congressos	4	5	9	Totais	4	4	8
Totais	9	9	18
Projetos temáticos	CNPq	FAPESP	Total parcial
Em Sistemas Flexíveis de Manufatura		1	1
Em Sistemas de Informações Geográficas		1	1
Em Sistemas Automáticos para Cortes e Empacotamento	1	1	2
Totais	1	1	4

 
 
 
 
 
 
 
 
 
 
 
 
 

4. Propostas para o projeto OC-SIAC 2
 
 
 
 

Sistemas Flexíveis de Manufatura
 
 

1. Os resultados da tese de doutorado de Arthur Tórgo Goméz deverão ainda ser submetidos para publicação em revista internacional. Espera-se também continuar o desenvolvimento de algoritmos para os problemas de sequenciamento com restrições temporais e de capacidades.
2. Estamos iniciando trabalho com a aplicação de Algoritmos Genéticos Construtivos ao problema da formação de células de manufatura (aluno de doutorado Geraldo Ribeiro Filho).
3. O projeto temático "Planejamento e Controle da Produção em Sistemas de Manufatura", foi proposto no final de 1997 à FAPESP. Nossa participação estará vinculada às áreas citadas acima. Espera-se bons resultados e colaboração com os pesquisadores da UNICAMP e USP/UFSCAR que estão envolvidos no projeto.

1. Com a apresentação da tese de doutorado de João Carlos Furtado em março, pretende-se implementar o Algoritmo Genético Construtivo para problemas das p-medianas no Sistema de Informação Geográfica ARC/INFO adquirido no projeto temático ARSIG. A implementação será realizada no INPE com o auxílio de bolsista PCI/CNPq.

 

 
 
 

2. A tese de doutorado de Marcelo Gonçalves Narciso também coloca à disposição os algoritmos que usam relaxação Lagrangeana e/ou surrogate para problemas de Localização. Estes serão implementados no âmbito do projeto ARSIG na FEG/UNESP, usando o SIG ARC/INFO, e baseando-se nos trabalhos conjuntos de Lorena & Senne ( ). A tese do Marcelo estuda também o Problema Simétrico do Caixeiro Viajante, e pretende-se continuar a pesquisa com variações do problema.

 

 
 
 

3. Um novo aluno de doutorado (Reinaldo Arakaki) estará começando a investigar a implementação e/ou adaptação dos Algoritmos Genéticos Construtivos a várias formulações dos problemas de roteamento de veículos.

 

 
 
 

4. Uma aluna de mestrado (Missae Yamamoto) está implementando uma heurística Tabu para o problema de rotulação de pontos em mapas cartográficos, e aplicando os resultados ao Sistema de Informações Geográficas SPRING, que está sendo desenvolvido no INPE. Esta é uma área de bom potencial de desenvolvimento de novos algoritmos e de grande interesse ao INPE e outros desenvolvedores de SGIs.

 

 
 
 

5. Pretende-se ainda propor cooperação com o Departamento de Processamento de Imagens do INPE e o CNPTIA da EMBRAPA em Campinas, para ampliação do projeto ARSIG, aplicando o sistema SPRING a problemas de distribuição no âmbito agrícola.

Sistemas Automáticos para Cortes e Empacotamento
 
 

1. Pretende-se dar continuidade ao desenvolvimento dos algoritmos para sequenciamento de padrões, cortes guilhotinados, "layout" e coloração de grafos

 

 
 
 

2. Também pretende-se continuar os desenvolvimento dos projetos temáticos PCE e CEAC, com a cooperação de pesquisadores das várias instituições envolvidas, particularmente 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.

1. Um dissertação de mestrado usando o Algoritmo Genético Construtivo para problemas de "bin packing" de verá ser apresentada em junho de 1998. O aluno de Iniciação Científica Alexandre Lucano, esta implementando uma versão para cortes com múltiplos painéis.

5. Cronograma de execução
 
 

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;
• Participação e/ou coordenação de Projetos Temáticos em áreas correlatas ao projeto;
• 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.

6. Bibliografia
 
 

• Beasley, J. E. Lagrangean Heuristics for Location Problems Europen Journal of Operational Research 65: 383-399, 1993.
• Crama, Y. Combinatorial Optimization Models for production scheduling in automated manufacturing systems. Semi-plenary papers - 14^th European Conference on Operational Research, Jerusalém, 1995.
• Fischbeck P. GIS: More than a Map. OR/MS Today 42-45, August 1994.
• Heragu, S.S. (1994) Group Technology and Cellular Manufacturing. IEEE Transactions on Systems, Man and Cybernetics 24(2), 203-214.
• Kusiak, A. Intelligent Manufacturing Systems. Prentice-Hall, New Jersey, 1990.
• Lorena, L.A.N. and Furtado, J.C. Constructive Genetic Algorithm for p-median Problems. Journal of the Operational Research Society - submitted - set./1997.
• Lorena, L. A. N. and Plateau, G. (1990), New subgradient algorithms for the 0-1 multiknapsack Lagrangian and surrogate duals. Pre-publication # 90. LIPN-Universite Paris Nord.
• Lorena, L.A.N. and Lopes, F.B. A surrogate heuristic for set covering problems. European Journal of Operational Research 79: 138-150, 1994.
• Lorena, L.A.N. and Narciso, M.G., Relaxation Heuristics for Generalized Assignment Problem. European Journal of Operational Research 91: 600-610, 1996.
• Lorena, L.A.N. and Lopes, L.S., Genetic Algorithms Apllied to Computationally Difficult Set Covering Problems. Journal of the Operational Research Society 48, 440-445, 1997.
• Lorena, L.A.N. and Lopes, L.S., Computational Experiments with Genetic Algorithms Apllied to Set Covering Problems. Pesquisa Operacional, Vol. 16, no. 1, 41-53, 1996.
• Lorena, L.A.N. and Lopes, F.B. A Dynamic List Heuristic for2D-Cutting. In: "System Modeling and Optimization" , ed. J. Dolezal and J. Fidler, Chapman & Hall, London, p. 481-488, 1996.
• Lorena, L.A.N. and Ribeiro Filho, G. Constructive Genetic Algorithm for Graph Coloring and Maximum Independent Set Problems. Pesquisa Operacional - submetido - out./97.
• Narciso, M. G. and Lorena, L. A. N. Lagrangean/surrogate Relaxation for Generalized Assignment Problems. European Journal of Operational Research, to appear (1998).
• Furtado, J. C. and Lorena, L.A.N. Otimização de Leiaute usando Busca Tabu. Gestão & Produção, 4(1), 88-107, abril 1997.
• Senne, E. L. F. and Lorena L. A. N., Lagrangean/surrogate Heuristuics for Location Problems. Apresentado no EURO INFORMS - Barcelona, 14 - 17 de julho de 1997.