OTIMIZAÇÃO COMBINATÓRIA
EM SISTEMAS DE INFORMAÇÃO ASSISTIDOS POR COMPUTADOR - FASE II
(OC-SIAC 2)
Ref.: Bolsa de Produtividade
em Pesquisa
para
Luiz Antonio Nogueira Lorena
lorena@lac.inpe.br
http://www.lac.inpe.br/~lorena
Relatório Final
1. Introdução
O projeto OC-SIAC 2 (Otimização Combinatória em Sistemas de Informação Assistidos por Computador - fase II) foi aprovado em julho de 1998 pelo CNPq, área de Engenharia de Produção/Pesquisa Operacional, recebendo o número CNPq 300837/89-5
O objetivo maior do OC-SIAC2 foi 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 foram cobertos pelos projetos temáticos acima referidos.
Os sistemas 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. Principais resultados obtidos (por área)
Sistemas Flexíveis de Manufatura
Publicações:
Gomez, A. T. and Lorena. L A. N., Modelagem de sistemas de manufatura flexíveis considerando restrições temporais e a capacidade do magazine. Gestão & Produção, 5(1), 69-80,1998.
Trabalhos apresentados em congressos:
Ribeiro Filho, G. and Lorena, L. A. N., A constructive genetic algorithm for cellular manufacturing design. Apresentado no EURO XVI - 16th European Conference on Operational Research. Bruxelas, Bélgica- 12-15 de julho de1998.
Ribeiro Filho, G. e Lorena, L. A. N. Algoritmo Genético Construtivo aplicado ao projeto de células de manufatura. XXX SBPO- Simpósio Brasileiro de Pesquisa Operacional – Curitiba - Nov./1998.
Ribeiro Filho, G. e Lorena, L. A. N. Aplicação do Algoritmo Genético Construtivo a um Problema de Programação de Horários. XXXI SBPO- Simpósio Brasileiro de Pesquisa Operacional. Juiz de Fora. 20-22/10/99
Projeto Temático:
PLANEJAMENTO E CONTROLE DA PRODUÇÃO EM SISTEMAS DE MANUFATURA
Projeto temático – FAPESP
http://www.densis.fee.unicamp.br/~franca/tematicoSituação atual: em andamento.
Equipe:
Coordenador:
Paulo Morelato França - FEEC/UNICAMP
Colaboradores por Instituição:
Luiz Antonio Nogueira Lorena (INPE)
Horácio Hideki Yanasse (INPE)
Marcos Nereu Arenales (USP-S.Carlos)
Reinaldo Morabito Neto (UFSCAR-S.Carlos)
Vinícius Amaral Armentano (FEEC/UNICAMP)
Sistemas de Informações Geográficas
Publicações:
Narciso, M. G. and Lorena, L. A. N. Lagrangean/surrogate Relaxation for Generalized Assignment Problems. European Journal of Operational Research , 114(1), 165-177, 1999.
Lorena, L. A. N. and Senne, E. L. F. Improving traditional subgradient scheme for Lagrangean relaxation: an application to location problems, International Journal of Mathematical Algorithms 1: 133-151, 1999
Senne, E. L. F. and Lorena, L. A. N. Lagrangean/surrogate heuristics for p-median problems. In Computing Tools for Modeling, Optimization and Simulation: Interfaces in Computer Science and Operations Research, M. Laguna and J. L. Gonzalez-Velarde (eds.), Kluwer Academic Publishers, pp. 115-130, 2000
Trabalhos aceitos para publicação:
Yamamoto, M. ; Camara, G. and Lorena, L. A. N. Tabu search heuristic for point-feature cartographic label placement. GeoInformatica - 1999.
Submetidos para publicação:
Lorena, L. A. N. and Furtado, J. C. Constructive genetic algorithm for clustering problems. Evolutionary Computation. No momento em 3ª revisão – 1998
Lorena, L.A.N. and Narciso, M. G. Using local surrogate information in Lagrangean relaxation: an application to symmetric traveling salesman problems. European Journal of Operational Research. No momento em 2ª revisão – 1998.
Lorena, L.A.N. ; Narciso, M. G. and Beasley J. E. A constructive genetic algorithm for the generalized assignment problem. Evolutionary Optimization – 1999
Trabalhos apresentados em congressos:
Lorena, L. A. N. and Furtado, J. C. Constructive genetic algoritnm for clustering problems. Apresentado no Optimization 98- Coimbra, Portugal - 20-22 julho de 1998.
Furtado, J.C. and Lorena, L.A.N. Algoritmo Genético Construtivo na otimização de problemas combinatoriais de agrupamentos. XXX SBPO- Simpósio Brasileiro de Pesquisa Operacional – Curitiba - Nov./1998.
Yamamoto, M. ; Câmara, G. and Lorena, L. A. N. Uma aplicação da busca tabu ao problema da rotulado cartográfica de pontos. Apresentado no GISBRASIL99 - Salvador - Julho 1999.
Yamamoto, M. ; Lorena, L. A. N. and Câmara, G. Tabu search application for point features cartographic label placement problems - Aceito para apresentação no MIC'99 - III Metaheuristics International Conference - Angra dos Reis - Julho 19-22, 1999.
Narciso, M. G. and Lorena, L.A.N. Using local surrogate information in Lagrangean relaxation: an application to symmetric traveling salesman problems. IFORS'99 - The 15th Triennial Conference - The International Federation of Operational Research Societies. Beijing, China. 15-20/08/99.
Lorena, L. A. N. ; Senne, E. L. F. ; Paiva, J. A. M. e Marcondes, S. P. B. Integração de um modelo de p-medianas a sistemas de informações geográficas. XXXI SBPO- Simpósio Brasileiro de Pesquisa Operacional. Juiz de Fora. 20-22/10/99.
Narciso, M. G. and Lorena, L.A.N. Algoritmo Genético Construtivo aplicado ao problema generalizado de atribuição. XXXI SBPO - Simpósio Brasileiro de Pesquisa Operacional. Juiz de Fora. 20-22/10/99.
Projeto Temático:
ANÁLISE DE REDES COM SISTEMAS DE INFORMAÇÕES GEOGRÁFICAS – ARSIG
Projeto temático - FAPESP
Situação atual: finalizado em 01 de junho de 1999.
Equipe:
Coordenador:
Dr. Luiz Antonio Nogueira Lorena
Pesquisador Titular - LAC/INPE
Colaboradores por Instituição:
INPE
Acioli Antonio de Olivo, Mestre
Dr. Luiz Antonio Nogueira Lorena
Dr. Horácio Hideki Yanasse
Dra. Maria de Lourdes N.O. Kurkdjian
FEG/UNESP
Prof. Dr. Edson Luis França Senne
Prof. Dr. Edgard Dias Batista Júnior
Sistemas Automáticos para Cortes e Empacotamento
Publicações:
Arenales, M. N. ; Ferreira, C. E. ; Wakabayashi, Y. , Lorena, L. A N. ; Yanasse, H. H. ; Maculan, N. ; Miyazawa, F. K. ; Morabito, R. and Soma, N. Y. PCE – Packing, Cutting and Related Problems: results of a project supported by CNPq - 1999
Submetidos para publicação:
Ribeiro Filho, G. and Lorena, L. A. N. Constructive genetic algorithm and Column Generation: an application to graph coloring. Asian Pacific Journal of Operation Research (APJOR) - 2000
Trabalhos apresentados em congressos:
Lorena, L. A. N. and Furtado, J. C. Constrained facility layout using tabu search. Apresentado no EURO XVI - 16th European Conference on Operational Research. Bruxelas, Bélgica- 12-15 de julho de1998.
Ribeiro Filho, G. e Lorena, L. A. N. Improvements on constructive genetic approaches to graph coloring. IFORS'99 - The 15th Triennial Conference - The International Federation of Operational Research Societies. Beijing, China. 15-20/08/99.
Projetos Temáticos:
CORTE E EMPACOTAMENTO ASSISTIDO POR COMPUTADOR - CEAC
Projeto temático – FAPESP
http://www.lac.inpe.br/po/projects/ceac/ceac.htmlSituação atual: em andamento.
Responsável/Participantes:
Horácio Hideki Yanasse (resp.)
Luiz Antonio Nogueira Lorena (LAC/INPE)
Marcos Nereu Arenales (USP-S.Carlos)
Reinaldo Morabito Neto (UFSCAR-S.Carlos)
Nei Yohiro Soma (ITA)
PROBLEMAS DE CORTES E EMPACOTAMENTOS E CORRELATOS - PCE
Projeto temático CNPq - Protem CC
Situação atual: finalizado em 01 de junho de 1999.
Responsável/Participantes:
Horácio Hideki Yanasse (resp.)
Luiz Antonio Nogueira Lorena (LAC/INPE)
Marcos Nereu Arenales (USP-S.Carlos)
Reinaldo Morabito Neto (UFSCAR-S.Carlos)
Nei Yohiro Soma (ITA)
Nelson Maculan Filho (UFRJ)
Carlos Eduardo Ferreira (USP)
Yoshiko Wakabayashi (USP)
Outras atividades relevantes
Docência e orientação:
Curso: Computação Aplicada no INPE
Docência
Estruturas e Algoritmos - 1° período 1999
Otimização Combinatória - 2° período 1998 e 2° período 1999.
Orientação
Iniciação cientifica -------------
Alexandre Moraes Lucano - 1998
http://www.lac.inpe.br/~lorena/lucano/cortes/cortes.htm
Helena Kiyoka Kobayashi - 1998
http://matter.ccet.umc.br/~helena/AGC.html
Mestrado -------------------
Henrique O. Q. Aquino - defendeu em julho/1998
Missae Yamamoto - defendeu em dezembro/1998
Tese: Uma aplicação da busca tabu ao problema da rotulação cartográfica de pontos
Helena Kiyoka Kobayashi – a partir de março 1999
Doutorado ------------------
João Carlos Furtado – defendeu em maio/1998
Tese: Algoritmos genéticos construtivos na otimização de problemas combinatoriais de agrupamentos
Marcelo Gonçalves Narciso – defendeu em maio/1998
Geraldo Ribeiro Filho - a partir de março/1997
Tese: Resolução de problemas de Otimização com representação em matrizes 0-1
Previsão de término: maio/2000.
Reinaldo G. Arakaki - a partir de março/1997
Missae Yamamoto (co-orientação com Gilberto Câmara) – a partir de março/1999
Colaboração
UNESP - FEG (Guaratinguetá)
Prof. Edson Luis França Senne
UFRJ - COPPE (Rio de Janeiro)
Prof. Roberto Diegues Galvão
Imperial College (Londres)
Prof. J. E. Beasley
Assessoria
FAPESP: Assessor para pedidos de bolsas e auxílios.
CNPq: Assessor para pedidos de bolsas, cooperação internacional e auxílios.
CAPES: Assessor para pedido de auxílio.
Revisor
Revista: European Journal of Operational Research
Revista: Produção (Membro do Conselho Científico)
Revista: Pesquisa Operacional
3. Resumo das atividades
bolsa de produtividade em 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 |
1 |
4 |
Doutorado |
2 |
3 |
5 |
|
Aceitos para publicação |
1 |
1 |
Mestrado |
2 |
1 |
3 |
|
|
Submetidos para revistas |
4 |
4 |
Iniciação científica |
2 |
2 |
||
|
Apresentados em congressos |
5 |
7 |
12 |
Totais |
6 |
4 |
10 |
|
Totais |
13 |
8 |
21 |
||||
|
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 Empacotam. |
1 |
1 |
2 |
||||
|
Totais |
1
|
1 |
4 |
||||