Article ID: | iaor20031866 |
Country: | United Kingdom |
Volume: | 53 |
Issue: | 11 |
Start Page Number: | 1275 |
End Page Number: | 1280 |
Publication Date: | Nov 2002 |
Journal: | Journal of the Operational Research Society |
Authors: | Croce F. Della, T'kindt Vincent |
Keywords: | beam search |
This paper deals with the one-machine dynamic total completion time scheduling problem. This problem is known to be NP-hard in the strong sense. A polynomial time heuristic algorithm is proposed which applies the recently introduced Recovering Beam Search (RBS) approach. The algorithm is based on a beam search procedure with unitary beam width and includes a recovering subroutine that allows to overcome wrong decisions taken at higher levels of the beam search tree. It is shown that the total number of considered nodes is bounded by