A Recovering Beam Search algorithm for the one-machine dynamic total completion time scheduling problem

A Recovering Beam Search algorithm for the one-machine dynamic total completion time scheduling problem

0.00 Avg rating0 Votes
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: ,
Keywords: beam search
Abstract:

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 n where n is the jobsize. The proposed algorithm is able to solve in very short CPU time problems with up to 500 jobs outperforming the best state of the art heuristics.

Reviews

Required fields are marked *. Your email address will not be published.