Approximation algorithms for job scheduling with block-type conflict graphs

Hanna Furmańczyk, Tytus Pikies, Inka Sokołowska +1

The problem of scheduling jobs on parallel machines (identical, uniform, or unrelated), under incompatibility relation modeled as a block graph, under the makespan optimality crite…