Artículo
A proposal for a hybrid meta-strategy for combinatorial optimization problems
Autor/es | Framiñán Torres, José Manuel
Pastor, Rafael |
Departamento | Universidad de Sevilla. Departamento de Organización Industrial y Gestión de Empresas I |
Fecha de publicación | 2008 |
Fecha de depósito | 2020-12-04 |
Publicado en |
|
Resumen | In this paper, we propose an algorithm named BDS (Bound-Driven Search) that combines features of exact and approximate methods. The proposed procedure may be seen as a local search algorithm that systematically explores ... In this paper, we propose an algorithm named BDS (Bound-Driven Search) that combines features of exact and approximate methods. The proposed procedure may be seen as a local search algorithm that systematically explores (in a branch-and bound sense) the most promising nodes, thus preventing solutions from being reevaluated. Additionally, it can be regarded as an exact method as it may be able to guarantee that the solution found is optimal. We present the application of this new algorithm to a specific problem domain: the permutation flow shop scheduling problem with makespan objective. The subsequent computational experiments are encouraging, as the algorithm is able to yield exact or near exact solutions to most instances of the problem. Furthermore, the algorithm outperforms one of the best state-of-the-art algorithms for the problem. |
Identificador del proyecto | DPI 2004-02902
DPI 2004-03472 |
Cita | Framiñán Torres, J.M. y Pastor, R. (2008). A proposal for a hybrid meta-strategy for combinatorial optimization problems. Journal of Heuristics volume, 2008 (14), 375-390. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
A_proposal_for_a_hybrid_meta_s ... | 398.8Kb | [PDF] | Ver/ | |