Um mÃtodo frugal para o problema de minimizaÃÃo de pilhas abertas.

AUTOR(ES)

Ashikaga, Fernando Masanori

DATA DE PUBLICAÇÃO

2001

RESUMO

Consideramos nesta dissertaÃÃo um problema, NP-difÃcil, de seqÃenciamento de padrÃes, vizando minimizar o nÃmero mÃximo de pilhas abertas em torno de uma mÃquina industrial de corte. Estamos interessados em mÃtodos frugais, os quais, seguindo à terminologia de HalldÃrson (91), sÃo aqueles - mÃtodos - que alÃm de utilizar poucos recursos computacionais - tempo e espaÃo - possuem idÃias de implementaÃÃes simples. A modelagem do problema pela Teoria dos Grafos foi a escolhida para obtenÃÃo de tais mÃtodos, na tentativa de se identificarem aspectos estruturais que, porventura, pudessem emergir e auxiliar na sua resoluÃÃo. A partir daquela modelagem, descobrimos ser o grafo complementar bastante esparso e possuidor de um conjunto independente maximal surpreendentemente grande, se comparado ao nÃmero de vÃrtices do grafo. AtravÃs da informaÃÃo adicional, fornecida por estes dois aspectos estruturais encontrados no grafo modelada, um mÃtodo geral, baseado no clique maximal, foi desenvolvido. A frugalidade do mÃtodo està no uso de uma conhecida heurÃstica gulosa, de tempo linear no nÃmero de vÃrtices, para detecÃÃo de conjuntos independentes. A partir do mÃtodo geral, duas heurÃsticas puderam ser desenvolvidas: a primeira, de detecÃÃo de circuitos hamiltonianos, obtidos atravÃs de uma versÃo do algoritmo extensÃo-rotaÃÃo para grafos randÃnicos, com o circuito inicial composto pelos vÃrtices do clique maximal; e a segunda, de contrataÃÃo recursiva de cliques. Realizamos testes computacionais comparando as nossas heurÃsticas com aquelas pertencentes ao estado da arte encontrado na literatura. Os resultados demonstram que as duas heurÃsticas desenvolvidas atravÃs do mÃtodo proposto sÃo competitivas, tanto em termos de tempo e espaÃo como de erro mÃdio, alÃm da facilidade de implementaÃÃo.

ASSUNTO(S)

corte programaÃÃo matemÃtica teoria dos grafos algoritmos mÃtodos computacionais mÃtodos heurÃsticos pesquisa operacional

Documentos Relacionados

• O problema de seqÃenciamento de padrÃes para a minimizaÃÃo do nÃmero mÃximo de pilhas abertas em ambientes de cortes industriais.
• Uma abordagem heurística construtiva para o problema de minimização de pilhas abertas.
• Um mÃtodo para seleÃÃo de testes de regressÃo para automaÃÃo
• MIDAI: um mÃtodo para identificaÃÃo e definiÃÃo de aspectos iniciais.
• Um novo mÃtodo para investigar cinÃticas de polimerizaÃÃo baseado em RMN