[pt] A principal contribuição desta tese consiste no
desenvolvimento de uma heurística híbrida, robusta e
eficiente, para o problema de empacotamento unidimensional.
A heurística proposta utiliza os seguintes componentes:
limites inferiores e superiores do número de caixas;
reduções; abordagem dual para a obtenção de soluções
iniciais; heurísticas para redistribuição dos pesos; e
busca tabu. O outro objetivo desta tese é a aplicação desta
heurística para a solução do problema de escalonamento em
processadores paralelos idênticos. São apresentados
resultados computacionais obtidos sobre centenas de
problemas testes da literatura. / [en] We propose in this work a hybrid improvement procedure for
the bin packing problem. This heuristic has several
components: lower and upper bounds; reductions,
construction of initial solutions by reference to the dual
problem;heuristics for load redistribution based on
dominance, differencing, and unbalancing; and tabu search.
We also investigate the application of this hybrid
heuristic to the problem of task scheduling on identical
parallel processors. Computational results on hundreds of
benchmark test problem are presented.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:4364 |
| Date | 09 January 2004 |
| Creators | ADRIANA CESARIO DE FARIA ALVIM |
| Contributors | CELSO DA CRUZ CARNEIRO RIBEIRO, CELSO DA CRUZ CARNEIRO RIBEIRO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0111 seconds