On-line algorithm for scheduling parallel tasks on related computational clusters with processors of different capacities and its average-case analysis

In this article the on-line problem of scheduling parallel tasks on related computational clusters with processors of different capacities was studied in average case. In the problem the objective is to make a schedule on $k$ clusters with $w$ processors each of $N$ tasks, where the task $i,i\le N$ requires time $h_i$ on cluster with nominal capacity of processors and $w_i\le w$ processors. We presume for all $1\le i\le N$ that $w_i$ has uniform distribution on $(0,w]$ and that $h_i$ has uniform distribution on $(0,1]$. The processors on different clusters have different capacities $v_1,\dots,v_k$. The task with nominal time $h_i$ will require $w_i$ processors be computed in time $\frac{h_i}{v_j}$ on cluster number $j$. Let sum volume of computations $W$ be the sum of volumes of computations for each task: $W=\sum_{i=1}^N w_ih_i$. Let $L$ be the minimal time at which all clusters will compute all the tasks, assigned to them, where each task is assigned to one cluster. The expected value of free volume of computations $E(V_{sp})$ is used to analyze the quality of an algorithm, where $V_{sp}=\sum_{1\le i\le k} v_iL-W$. It was shown that for every algorithm for scheduling parallel tasks on related clusters $E(V_{sp})=\Omega(w\sqrt N)$. An on-line algorithm Limited Hash Scheduling was proposed, which has $E(V_{sp})\le 4(w\sqrt{N\ln N})=O(w\sqrt{N\ln N})$, for $N>N_0\in\mathbb N$ if $k\le\sqrt N$ and $v_j\le\sqrt{\ln N}\frac{\sum_{i=1}^k v_i}{k}\forall 1\le j\le k$. The idea of the algorithm is to schedule tasks of close required number of required processors into different limited in time and the number of allowed to use processors areas on clusters.