1 Relatório
Período: 01-08-96 a 31-07-97
Ref.: Processo CNPq 520844/96-3
Resumo do projeto
O projeto (OC-SIAC) 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.
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.
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.
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. 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.
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.
Principais resultados obtidos (por área)
Sistemas Flexíveis de Manufatura
Resultados: -----------------------------------------------------------------------------------------------------
Tese de doutorado: ----------------------------------------------------------------------
Arthur Tórgo Gómez
Curso: Computação Aplicada no INPE
Orientador: Dr. Luiz Antonio N. Lorena
Apresentada em dezembro de 1996.
Resumo:
Os problemas de grupamento de partes, grupamento de partes e ferramentas e o de troca de ferramentas foram tratados propondo novas versões da metaheurística "busca tabu" para a solução dos problemas.
Trabalhos Submetidos para apresentação em congressos: -------------------
Gomez, A. T. and Lorena. L A. N., Modelagem de sistemas de manufatura flexíveis considerando restrições temporais e a capacidade do magazine. Convidado para a II Oficina de Cortes e Ema apacotamento.Gramado-RS- 1997.
Propostas: -------------------------------------------------------------------------------------------------------
Os resultados da tese de doutorado serão apresentados na 2a. Oficina de Cortes e Empacotamento, que será realizada em Gramado, em setembro/97. Também serão submetidos dois trabalhos para publicação, em revistas nacionais e internacionais.
Pretende-se ainda que algum aluno de mestrado
venha a continuar as pesquisas.
Sistemas de Informações Geográficas
Resultados: -----------------------------------------------------------------------------------------------------
Os problemas de Localização de Facilidades foram estudados considerando uma nova relaxaçao para problemas de Otimização Combinatória foi proposta e está sendo desenvolvida como tese de doutorado de Marcelo Gonçalves Narciso. A nova relaxação combina duas relaxações conhecidas (Lagrangeana e surrogate) e produz os mesmos limites da relaxação Lagrangeana usual, mas com significativos ganhos (de até 75%) em tempo computacional para problemas de grande porte. A relaxação Lagrangeana/surrogate foi aplicada com sucesso aos seguintes problemas: Problema Generalizado de Atribuição (com Marcelo Narciso - dois trabalhos), o Problema das P-Medianas, e os Problemas de Localização Capacitado e Não-capacitado (em cooperação com o Prof. Edson L. Senne da FEG-UNESP).
Os Algoritmos Genéticos foram aplicados ao problema de Cobertura de Conjuntos (com Luciana de S. Lopes). Em particular excelentes resultados foram obtidos para instâncias computacionalmente difíceis. A partir desses resultados uma nova versão de algoritmos genéticos está sendo desenvolvida, considerando como um método construtivo para a formação de uma população com o máximo de informação possível sobre o problema em questão. Resultados preliminares promissores foram obtidos na proposta de tese de doutorado de João Carlos Furtado (problema das p-medianas).
O aluno de Iniciação Científica Fernando Galbier, está implementando uma versão do Algoritmo Genético Construtivi para o problema de roteamento de veículos.
O projeto temático Análise de Redes com Sistemas de Informacoes Geograficas - ARSIG foi aprovado em junho de 1997.
Publicações: -------------------------------------------------------------------------------
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 Researc 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 - 1997.
Trabalhos submetidos para publicação: --------------------------------------------
Lorena, L. A. N. and Senne, E. L. F., A Lagrangean/surrogate Heuristic for Uncapacitated Facility Location Problems. International Transactions on Operations Research.
Lorena, L. A. N. and Senne, E. L. F., Lagrangean/surrogate Heuristics for a Capacitated Facility Location Problem. Location Science.
Senne, E. L. F. and Lorena, L. A. N., A Lagrangean/Surrogate approach to p-median problems. European Journal of Operational Research.
Narciso, M. G. and Lorena, L. A. N. Lagrangean/surrogate Relaxation for Generalized Assignment Problems. European Journal of Operational Research.
Trabalhos apresentados em congressos: ------------------------------------------
Lorena, L. A. N. and Senne, E. L. F., A Lagrangean/Surrogate Heuristic for Uncapacitated Facility location Problems, Apresentado no CLAIO-SOBRAPO-96.
Narciso, M. G. and Lorena, L. A. N. , Lagrangean/surrogate relaxation to Large Scale Generalized Assignment Problems, apresentado no ENEGEP-96 - 16o. Encontro Nacional de Engenharia de Produção e 2o. Congresso Internacional de Engenharia Industrial. Piracicaba, SP - 7 a 10 de outubro de 1996.
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.
Narciso, M. G. and Lorena L. A. N., A Lagrangean/surrogate approach to generalized assignment problems. Apresentado no EURO INFORMS - Barcelona, 14 - 17 de julho de 1997.
Trabalhos Submetidos para apresentação em congressos: -------------------
Furtado, J. C. and Lorena, L. A. N. Otimização do Problema das p-medianas usando um Algoritmo Genetico Construtivo. Submetido para apresentacao no ENEGEP/97 - Gramado-RS.
Lorena, L. A. N. and Narciso, M. G. A Lagrangean/surrogate approach to Traveling Salesman Problems. Submetido para apresentacao no XXIX SBPO- Simposio Brasileiro de Pesquisa Operacional - Salvador - 22 a 24 de outubro de 1997.
Projeto Temático: ------------------------------------------------------------------------
ANÁLISE DE REDES COM SISTEMAS DE INFORMAÇÕES GEOGRÁFICAS - ARSIG
Projeto temático - FAPESP
http://www.lac.inpe.br/~lorena/ArsigIndex.html
Resumo:
projeto visa a integração de grupos de pesquisa na área de algoritmos para problemas de redes com aplicação em Sistemas de Informações Geográficas. Os problemas a serem estudados são conhecidos como problemas de localização e roteamento. São problemas que justificam a atenção devido ao fato de possuirem diversas aplicações e serem considerados de difícil solução. O objetivo principal da pesquisa está no desenvolvimento de novos algoritmos e na adaptação de algoritmos clássicos considerados eficientes, para as áreas de localização e roteamento. Propõe-se também como objeto de integração da equipe o uso comum de Sistemas de Informações Geográficas, com a adaptação dos algoritmos de localização e roteamento a estes sistemas. Pode-se vir ainda a aproveitar a experiência da equipe na realização de uma aplicação prática, definida para uma cidade do Vale do Paraíba.
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
2 alunos de Mestrado e 1 de Doutorado do Curso de Computação Aplicada
2 bolsistas de Iniciação Científica.
FEG/UNESP
Prof. Dr. Edson Luis França Senne
Prof. Dr. Edgard Dias Batista Júnior
2 Bolsistas de Iniciação Científica, com bolsa do REENGE/CNPq:
2 bolsistas de Iniciação Científica.
Propostas: -------------------------------------------------------------------------------------------------------
Pretende-se continuar com os experimentos com a relaxação Lagrangeana/surrogate aplicando-a a instancias de grande porte do problema do caixeiro viajante, bem como formalizar a teoria como tese de doutorado de Marcelo Gonçalves Narciso (orientada por Luiz A. N. Lorena).
Os problemas de roteamento de veículos, p-medianas e caixeiro viajante continuarão a ser tratados com Algoritmos Genéticos Construtivos.
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.
Sistemas Automáticos para Cortes e Empacotamento
Resultados: -----------------------------------------------------------------------------------------------------
Na área de sequenciamento de padrões de cortes, os resultados obtidos na tese de doutorado de Arthur Tórgo Gómez (veja ítem sobre Sistemas Flexíveis de Manufatura) são diretamente aplicáveis dado a semelhança dos problemas.
Os cortes guilhotinados estão sendo explorados usando a versão construtiva de algoritmos genéticos.
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.
O Algoritmo Genético Construtivo foi aplicado com sucesso na dissertação de mestrado de Geraldo Ribeiro Filho (problemas de coloração de grafos).
Dissertação de Mestrado: --------------------------------------------------------------
Geraldo Ribeiro Filho
Curso: Computação Aplicada no INPE
Orientador: Dr. Luiz Antonio N. Lorena
Apresentada em fevereiro de 1997
Título: Uma heurística construtiva para coloração de grafos.
Publicações: -------------------------------------------------------------------------------
Lorena, L.A.N. and Lopes, F.B. A Dynamic List Heuristic for
2D-Cutting. In: " System Modeling and Optimization" , ed. J. Dolezal and J. Fidler, Chapman & Hall, London, p. 481-488, 1996.
Furtado, J. C. and Lorena, L.A.N. Otimizao de Leiaute usando Busca Tabu. Gestao & Producao, 4(1), 88-107, abril 1997.
Trabalhos apresentados em congressos: ------------------------------------------
Furtado, J. C. and Lorena, L.A.N. Otimizao de Leiaute usando Busca Tabu. Ia. Oficina de Coretes e Empacotamento. IME-USP. Dez. 1996.
Trabalhos Submetidos para apresentação em congressos: -------------------
Furtado , J. C. and Lorena, L.A.N. Otimizacao em Problemas de leiaute. Convidado para a II Oficina de Cortes e Empacotamento. Gramado-RS - set. 1997.
Lorena, L. A. N. and Ribeiro Filho, G. Constructive Genetic Algorithm for Graph Coloring and Maximum Independent Set Problems. Submetido para apresentacao no XXIX SBPO- Simposio Brasileiro de Pesquisa Operacional - Salvador - 22 a 24 de outubro de 1997.
Trabalhos aceitos para apresentação em congressos: -------------------------
Ribeiro Filho, G. and Lorena, L. A. N. A Constructive Genetic Algorithm for Graph Coloring Problems. Aceito para apresentacao no congresso APORS'97 a ser realizado em Melbourne/ Australia - de 30 de novembro a 04 de dezembro de 1997.
Projetos Temáticos: ---------------------------------------------------------------------
Corte e Empacotamento Assistido por Computador - CEAC
Projeto temático - FAPESP
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 & Empacotamentos e Correlatos - PCE
Projeto temático CNPq - Protem CC
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)
Propostas: -------------------------------------------------------------------------------------------------------
Pretende-se dar continuidade ao desenvolvimento dos algoritmos para sequenciamento de padrões, cortes guilhotinados e "layout".
O Algoritmo Genético Construtivo esta sendo aplicado aos problemas citados. Os problemas de "layout" continuarão a ser estudados visando a preparação de uma monografia que poderá vir a ser um capítulo de livro sobre cortes e empacotamento.
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.
Dois alunos de mestrado estão iniciando
dissertação nas áreas. Específicamente, usando
o Algoritmo Genético Construtivo para cortes irregulares e para
problemas de "bin packing". O aluno de Iniciação Científica
Alexandre Lucano, esta implementando uma versão para cortes com
multiplos paineis. Pretende-se ainda usar a cooperação de
um bolsista recém-doutor.
Outras atividades relevantes
Docência, coordenação e orientação:
Curso: Computação Aplicada no INPE
Docência -----------------------------------------------------------------------------------
Estruturas e Algoritmos - 1 período 1997
Otimização Combinatória - 2 período 1996
Coordenação ------------------------------------------------------------------------------
Coordenador do curso de Computação Aplicada do INPE (até nov./96)
Orientação ---------------------------------------------------------------------------------
Doutorado
Arthur Torgo Gomez - defendeu em dez./96
Fábio Belo Lopes
João Carlos Furtado - previsão de término: dez./97
Marcelo Gonçalves Narciso - previsão de término:dez/97
Mestrado
Geraldo Ribeiro Filho - defendeu em fev./97
Henrique O. Q. Aquino - previsão de término: nov./97
Iniciação Científica
Alexandre M. Lucano
João V. Silva Júnior e Fernando Galbier (substituição)
Colaboração -------------------------------------------------------------------------------
UNESP - FEG (Guaratinguetá)
Prof. Edson Luis França Senne
UFRJ - COPPE (Rio de Janeiro)
Prof. Roberto Diegues Galvão
Pesquisa conjunta na área de Relaxação Lagrangeana/surrogate para problemas de localização de facilidades.
Assessoria ---------------------------------------------------------------------------------
FAPESP: Assessor para pedidos de bolsas e auxílios.
CAPES: Assessor para pedido de auxílio.
Revisor -------------------------------------------------------------------------------------
Revistas: Pesquisa Operacional e Produção
Congresso: ENEGEP - Encontro Nacional de Engenharia
de Produção e 2o. Congresso Internacional de Engenharia Industrial
Resumo das atividades
bolsa de pesquisa
Luiz Antonio Nogueira Lorena
| Trabalhos | Internacionais | Nacionais | Orientação | finalizada | Em andamento |
| Publicados em revistas |
|
|
Doutorado |
|
|
| Submetidos para revistas |
|
Mestrado |
|
|
|
| Apresentados em congressos |
|
|
Iniciação científica |
|
|
| Submetidos para apresentação |
|
|
|||
| Projetos Temáticos |
|
|
coordenador | ||
| ARSIG |
|
Luiz A N. Lorena | |||
| CEAC |
|
Horácio H. Yanasse | |||
| PCE |
|
Horácio H. Yanasse |
Fernando
Galbier
Alexandre
Lucano
--------------------------------------------------------------------------------------------------------------------------------