A note on ‘‘Beam search heuristics for the single machine early/tardy scheduling problem with no machine idle time”

In a recent paper by Valente ‘‘Beam search heuristics for the single machine early/tardy scheduling problem with no machine idle time”’, Computers & Industrial Engineering, 55, 663–675, 2008, several beam search approaches are compared on a large set of instances of the total weighted earlinesstardiness problem on single machine with jobs independent weights and no machine idle time. That problem is denoted 1jnmitjPjhEj þPjwTj . This note points out that the standard iterated dynasearch procedure applied to that problem outperforms all the literature heuristics. Based on these results and others obtained on similar problems, we conclude that dynasearch for its efficiency and simplicity, should be used as a benchmark for future heuristics on those types of single machine no idle time problems.