A Recovering Beam Search algorithm for the one-machine dynamic total completion time scheduling problem |
| |
Authors: | F Della Croce V T'kindt |
| |
Affiliation: | 1.DAI, Politecnico di Torino,Turin,Italy;2.E3I, Université de Tours,Tours,France |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|