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

摘要

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