Return to search

[en] A HYBRID IMPROVEMENT HEURISTICS FOR THE BIN PACKING PROBLEM AND ITS APPLICATION TO THE PROBLEM OF TASK SCHEDULING / [pt] UMA HEURÍSTICA HÍBRIDA DE MELHORIA PARA O PROBLEMA DE BIN PACKING E SUA APLICAÇÃO AO PROBLEMA DE ESCALONAMENTO DE TAREFAS

[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.

Identiferoai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:4364
Date09 January 2004
CreatorsADRIANA CESARIO DE FARIA ALVIM
ContributorsCELSO DA CRUZ CARNEIRO RIBEIRO, CELSO DA CRUZ CARNEIRO RIBEIRO
PublisherMAXWELL
Source SetsPUC Rio
LanguagePortuguese
Detected LanguagePortuguese
TypeTEXTO

Page generated in 0.0111 seconds