Analysis of Fork-Join Scheduling on Heterogeneous Parallel Servers

This paper investigates the
$(k,k)$
fork-join scheduling scheme on a system of
$n$
parallel servers comprising both slow and fast servers. Tasks arriving in the system are divided into
$k$
sub-tasks and assigned to a random set of
$k$
servers, where each task can be assigned independently to a distinct slow or fast server with selection probability
$p_s$
or
$1-p_s$
, respectively. Our analysis demonstrates that the joint distribution of the stationary workload across any set of
$k$
queues becomes asymptotically independent as the number of servers
$n$
grows, with
$k$
scaling as
$o(n^{\frac{1}{4}})$
. Under asymptotic independence, the limiting mean task completion time can be expressed as an integral. However, it is analytically challenging to compute the optimal selection probability
$p_s^\ast$
that minimizes this integral. To address this, we provide an upper bound on the limiting mean task completion time and identify the selection probability
$\hat{p}_s$
that minimizes this bound. We validate that this selection probability
$\hat{p}_s$
yields a near-optimal performance through numerical experiments.