29 July 2024 in IEEE/ACM Transactions on Networking
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.