On-Line Scheduling of Parallel Jobs in Heterogeneous Multiple Clusters

摘要

We consider the on-line scheduling of parallel jobs in heterogeneous multiple clusters, in which a set of clusters is given and the parallel jobs arrive one by one, and the goal is to schedule all the jobs while minimizing the makespan. A cluster consists of many identical processors. A parallel job may require several processors in one cluster to execute it simultaneously. In this paper, we investigate two variants of the heterogeneous clusters. First, for the clusters of different widths (number of processors) but identical processor speeds, we provide an on-line algorithm with a competitive ratio at most of 14.2915. Second, for the clusters of different speeds but identical widths, we provide an on-line algorithm with a competitive ratio at most of 18.2788.