OTIMIZAÇÃO COMBINATÓRIA
EM SISTEMAS DE INFORMAÇÃO ASSISTIDOS POR COMPUTADOR
(OC-SIAC)
http://www.lac.inpe.br/~lorena
Relatório final
Período: 01-08-96 a 31-07-98
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 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.
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 três á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. 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)
Principais resultados obtidos (por área)
Sistemas Flexíveis de Manufatura
Resultados:
Orientador: Dr. Luiz Antonio N. Lorena
Apresentada em dezembro de 1996.
Resumo:
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.
Marcos Nereu Arenales (USP-S.Carlos)
Reinaldo Morabito Neto (UFSCAR-S.Carlos)
Resultados:
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, com dois trabalhos publicados. A partir desses resultados
uma nova versão de algoritmos genéticos foi desenvolvida,
considerando como um método construtivo para a formação
de uma população com o maior nível de informação
sobre o problema em questão. Na tese de doutorado de João
Carlos Furtado foram conseguidos excelentes resultados para os seguintes
problemas de "clustering": p-medianas, p-medianas capacitado e particionamento
de grafos.
O aluno de Iniciação Científica
Fernando Galbier, iniciou a implementação de uma versão
do Algoritmo Genético Construtivo para o problema de roteamento
de veículos. Atualmente o aluno de doutorado Reinaldo G. Arakaki
esta iniciando estudos para aplicação do Algoritmo Genético
Construtivo a vários problemas de roteamento de veículos
O projeto temático Análise
de Redes com Sistemas de Informações Geográficas -
ARSIG foi aprovado em junho de 1997. Pretende-se integrar os novos
algoritmos ao SIG ARC/INFO.
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.
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.
Lorena, L. A. N. and Narciso, M. G. A Lagrangean/surrogate
approach to Traveling Salesman Problems. Apresentado no XXIX SBPO-
Simposio Brasileiro de Pesquisa Operacional - Salvador - 22 a 24 de outubro
de 1997.
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.
http://www.lac.inpe.br/~lorena/ArsigIndex.html
O 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 possuírem 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:
Dr. Luiz Antonio Nogueira Lorena
Pesquisador Titular - LAC/INPE
INPE
Dra. Maria de Lourdes N.O. Kurkdjian
Prof. Dr. Edgard Dias Batista Júnior
Resultados:
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 retângulos 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).
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.
Lorena, L. A. N. and Ribeiro Filho, G. Constructive
Genetic Algorithm for Graph Coloring and Maximum Independent Set Problems.
Apresentado no XXIX SBPO- Simpósio Brasileiro de Pesquisa Operacional
- Salvador - 22 a 24 de outubro de 1997.
Ribeiro Filho, G. and Lorena, L. A. N. A
Constructive Genetic Algorithm for Graph Coloring Problems. Apresentado
no congresso APORS'97 a ser realizado em Melbourne/ Austrália -
de 30 de novembro a 04 de dezembro de 1997.
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.
Corte e Empacotamento Assistido por Computador - CEAC
Projeto temático - FAPESP
Reinaldo Morabito Neto (UFSCAR-S.Carlos)
Nei Yohiro Soma (ITA)
Projeto temático CNPq - Protem CC
Responsável/Participantes:
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)
Docência
Estruturas e Algoritmos - 1° período 1997 e 1998
Otimização Combinatória - 2° período 1996 e
Coordenador do curso de Computação Aplicada do INPE (até nov./96)
Orientação
Doutorado
Arthur Torgo Gomez - defendeu em dezembro de 1996
Marcelo Gonçalves Narciso - defendeu
em abril de 1998.
Geraldo Ribeiro Filho - a partir de março de 1997
Reinaldo G. Arakaki - a partir de março de 1998
Geraldo Ribeiro Filho - defendeu em fevereiro de 1997
Missae Yamamoto - a partir de janeiro de 1998.
Iniciação Científica
Alexandre M. Lucano
João V. Silva Júnior e Fernando
Galbier (substituição)
Pesquisa conjunta na área de Relaxação Lagrangeana/surrogate para problemas de localização de facilidades.
Imperial College - Londres
Prof. J. Beasley
CAPES: Assessor para pedido de auxílio.
CNPq: Assessor Ad-Hoc
Revista: Produção (Membro do Conselho Científico)
Revista: Pesquisa Operacional
Congresso: ENEGEP - Encontro Nacional de Engenharia
de Produção e 2o. Congresso Internacional de Engenharia Industrial
bolsa de produtividade e pesquisa
Luiz Antonio Nogueira Lorena
|
|
|
|
|
|
|
|
|
|
|
3 |
2 |
5 |
|
3 |
2 |
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
||||
| 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 |
||||
|
|
|
|
|
||||
Paginas internet ® http://www.lac.inpe.br/~lorena