Scheduling with Communication Delays via LP Hierarchies and Clustering II: Weighted Completion Times on Related Machines

We consider the problem of scheduling jobs with precedence constraints on related machines to minimize the weighted sum of completion times, in the presence of communication delays. In this setting, denoted by Q | prec, c | Σw_jC_j, if two dependent jobs are scheduled on different machines, then at least c units of communication delay time must pass between their executions. Our main result is an O(log^4 n)-approximation algorithm for the problem. As a byproduct of our result, we also obtain an O(log^3 n)-approximation algorithm for the problem of minimizing makespan Q | prec, c | C_max, which improves upon the O(log^5 n/ log log n)-approximation algorithm due to a recent work of Maiti et al.