ETDs @PUC-Rio
| Título: | A HYBRID IMPROVEMENT HEURISTICS FOR THE BIN PACKING PROBLEM AND ITS APPLICATION TO THE PROBLEM OF TASK SCHEDULING | ||||||||||||||||||||||||||||||||||||||||||||
| Autor: |
ADRIANA CESARIO DE FARIA ALVIM |
||||||||||||||||||||||||||||||||||||||||||||
| Colaborador(es): |
CELSO DA CRUZ CARNEIRO RIBEIRO - Orientador |
||||||||||||||||||||||||||||||||||||||||||||
| Catalogação: | 09/JAN/2004 | Língua(s): | PORTUGUESE - BRAZIL |
||||||||||||||||||||||||||||||||||||||||||
| Tipo: | TEXT | Subtipo: | THESIS | ||||||||||||||||||||||||||||||||||||||||||
| Notas: |
[pt] Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio. [en] All data contained in the documents are the sole responsibility of the authors. The data used in the descriptions of the documents are in conformity with the systems of the administration of PUC-Rio. |
||||||||||||||||||||||||||||||||||||||||||||
| Referência(s): |
[pt] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=4364&idi=1 [en] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=4364&idi=2 |
||||||||||||||||||||||||||||||||||||||||||||
| DOI: | https://doi.org/10.17771/PUCRio.acad.4364 | ||||||||||||||||||||||||||||||||||||||||||||
| Resumo: | |||||||||||||||||||||||||||||||||||||||||||||
|
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.
|
|||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||