Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines

Abstract

In the paper we consider the problem of scheduling $n$ identical jobs on 4 uniform machines with speeds $s_1\ge s_2\ge s_3\ge s_4,$ respectively. Our aim is to find a schedule with a minimum possible length. We assume that jobs are subject to some kind of mutual exclusion constraints modeled by a bipartite incompatibility graph of degree $\Delta$, where two incompatible jobs cannot be processed on the same machine. We show that the problem is NP-hard even if $s_1=s_2=s_3$. If, however, $\Delta \le 4$ and $s_1\ge 12s_2$, $s_2=s_3=s_4$, then the problem can be solved to optimality in time $O(n^{1.5})$. The same algorithm returns a solution of value at most 2 times optimal provided that $s_1\ge 2s_2$. Finally, we study the case $s_1\ge s_2\ge s_3=s_4$ and give an $O(n^{1.5})$-time $32/15$-approximation algorithm in all such situations.

Cited by in corpus (2)

• Tight Bounds on the Complexity of Semi-Equitable Coloring of Cubic and Subcubic Graphs
• Graph theoretic and algorithmic aspect of the equitable coloring problem in block graphs