An analysis of the importance of appropriate tie breaking rules in dispatch heuristics

In this paper, we analyse the effect of using appropriate tie breaking criteria in dispatch rules. We consider four different dispatch procedures, and for each of these heuristics we compare two versions that differ only in the way ties are broken. The first version breaks ties randomly, while the second uses a criterion that incorporates problem-specific knowledge. The computational results show that using adequate tie breaking criteria improves the performance of the dispatch heuristics. The magnitude of the improvement is different for the four heuristics, and also depends on the characteristics of each specific instance. The use of problem-related knowledge for breaking ties should therefore be given some consideration in the implementation of dispatch rules.