Scheduling on Uniform and Unrelated Machines with Bipartite Incompatibility Graphs

Tytus Pikies; Hanna Furmańczyk

doi:10.1109/ipdps53621.2022.00070

Scheduling on Uniform and Unrelated Machines with Bipartite Incompatibility Graphs

Abstract

The problem of scheduling jobs on parallel machines under an incompatibility relation is considered in this paper. In this model, a binary relation between jobs is given and no two jobs that are in the relation can be scheduled on the same machine. We consider job scheduling under the incompatibility relation modeled by a bipartite graph, under the makespan optimality criterion, on uniform and unrelated machines. Unrelated machines are considered first. An FPTAS for R2|G=bipartite|Cmax is provided. We also show that for any ϵ>0,b>0 and m≥3 , there is no polynomial-time algorithm of approximation ratio O(nbp1−ϵmax) for Rm|G = bipartite |Cmax , unless P = NP. Uniform machines are considered as second. For any ϵ>0 , we show that under P = NP assumption there is no polynomial-time O(n1/2−ϵ )-approximation algorithm, even in the case of unit time jobs. We also provide a polynomial-time Σpj−−−√ -approximation algorithm for the case of jobs of arbitrary lengths pj , matching the established bound. To enrich the analysis, bipartite graphs generated randomly according to Gilbert's model Gn,n,p(n) are considered. We show that there exists an algorithm producing a schedule with makespan almost surely at most twice the optimum for a broad class of p(n) functions. To the best of our knowledge, this is the first study of randomly generated graphs in the context of scheduling in the considered model.