Article ID: | iaor20043215 |
Country: | Netherlands |
Volume: | 10 |
Issue: | 1 |
Start Page Number: | 89 |
End Page Number: | 104 |
Publication Date: | Jan 2004 |
Journal: | Journal of Heuristics |
Authors: | Tadei R., Croce F. Della, Ghirardi M. |
Keywords: | beam search |
A hybrid heuristic method for combinatorial optimization problems is proposed that combines different classical techniques such as tree search procedures, bounding schemes and local search. The proposed method enhances the classic beam search approach by applying to each partial solution corresponding to a node selected by a beam, a further test that checks whether the current partial solution is dominated by another partial solution at the same level of the search tree. If this is the case, the latter solution becomes the new current partial solution. This step allows to partially recover from previous wrong decisions of the beam search procedure and can be seen as a local search step on the partial solution. We present here the application to two well known combinatorial optimization problems: the two-machine total completion time flow shop scheduling problem and the uncapacitated