Controlling the correlation of costmatrices to assess schedulingalgorithm performance on heterogeneous platforms

摘要

Bias in the performance evaluation of scheduling heuristics has been shown to undermine thescope of existing studies. Improving the assessment step leads to stronger scientific claims whenvalidating new optimization strategies. This article considers the problem of allocating independenttasks to unrelated machines such as to minimize the maximum completion time. Testingheuristics for this problem requires the generation of cost matrices that specify the executiontime of each task on eachmachine. Numerous studies showed that the task and machine heterogeneitiesbelong to the properties impacting heuristics performance themost. This study focuseson orthogonal properties, the average correlations between each pair of rows and each pair ofcolumns, which measure the proximity with uniform instances. Cost matrices generated with 2distinct novel generation methods show the effect of these correlations on the performance ofseveral heuristics from the literature. In particular, EFT performance depends on whether thetasks aremore correlated than the machines andHLPT performs the best when both correlationsare close to one.