Makespan Minimization for Scheduling on Heterogeneous Platforms with Precedence Constraints

Taking a good decision about the assignment of each job becomes crucial in the era of hybrid and heterogeneous computing systems, such as personal machines equipped with CPUs and GPUs, or HPC platforms composed of multiple generations of processors. In this study, we focus on the fundamental makespan minimization problem of scheduling jobs subject to precedence constraints on a platform composed of q different families of machines. Each family is constituted of identical parallel machines. The processing time of a job depends on the family where it is allocated. We propose an algorithm that guarantees an approximation ratio of \(q+1+2\sqrt{q-1}\) , which improves upon the existing upper bound of \(q(q+1)\) . In particular, this algorithm achieves a ratio of 5 in the special case of a machine composed only of CPUs and GPUs. This specific scenario with \(q=2\) families of machines has been widely studied by the scientific community in recent years. The best known lower and upper bounds known so far were 3 and 5.83, respectively.