A heuristic for the minimization of open stacks problem

AUTOR(ES)

Ashikaga, Fernando Masanori, Soma, Nei Yoshihiro

FONTE

Pesquisa Operacional

DATA DE PUBLICAÇÃO

2009-08

RESUMO

Sugerimos uma heurística rápida e de implementação simples para o problema de minimização de pilhas abertas (MOSP). O problema é modelado como um problema de percorrimento de arcos no grafo (Gmosp) associado (Yanasse, 1997b). Foi observado em Ashikaga (2001) que o grafo Gmosp possui grandes cliques e uma alta densidade de arestas. Esta informação foi utilizada para implementar uma heurística baseada no algoritmo Extensão-Rotação de Pósa (1976) para aproximação de Circuitos Hamiltonianos. O caminho inicial para o algoritmo de Pósa é obtido a partir dos vértices de uma aproximação do maior clique do grafo para acelerar o processo. Testes computacionais extensivos mostram que a abordagem domina tanto em tempo quanto em erro médio a mais rápida heurística conhecida de Yuen (1991 e 1995).

ASSUNTO(S)

minimização de pilhas abertas heurística extensão-rotação clique

Documentos Relacionados

• GRAPH PROPERTIES OF MINIMIZATION OF OPEN STACKS PROBLEMS AND A NEW INTEGER PROGRAMMING MODEL
• A HYBRID HEURISTIC ALGORITHM FOR THE CLUSTERED TRAVELING SALESMAN PROBLEM
• A MODEL-BASED HEURISTIC FOR THE IRREGULAR STRIP PACKING PROBLEM
• Combinatorial instruments in the design of a heuristic for the quadratic assignment problem
• A multi-start random constructive heuristic for the container loading problem