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

Pesquisa Operacional

Jorge M. S. Valente¹ 

[1] ,Universidade do Porto Faculdade de Economia Porto,Portugal

关键词: scheduling;    dispatch rules;    tie breaking;    sequenciamento;    regras de despacho;    resolução de empates;   

DOI  :  10.1590/S0101-74382006000100009

来源: SciELO

【 摘 要 】

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.

【 授权许可】

CC BY   
 All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License