Task scheduling for block-type conflict graphs

In this paper, we consider the scheduling of jobs on parallel machines, under incompatibility relation modeled as a block graph, under the makespan optimality criterion. In this model, no two jobs that are in the relation (equivalently in the same block) may be scheduled on the same machine. The presented model stems from a well-established line of research combining scheduling theory with methods relevant to graph coloring. Recently, cluster graphs and their extensions like block graphs were given additional attention. We complement hardness results provided by other researchers for block graphs by providing approximation algorithms. In particular, we provide a $2$-approximation algorithm for identical machines and PTAS for its special case with unit time jobs. In the case of uniform machines, we analyze two cases: when the number of blocks is bounded; and when the number of blocks is arbitrary, but the number of cut-vertices is bounded and jobs are unit time processing length. Finally, we consider unrelated machines and we present an FPTAS for graphs with bounded treewidth and a bounded number of machines.