On some special cases of the restricted assignment problem

•We study the scheduling problem of minimizing makespan on unrelated parallel machines in the restricted assignment model.•We give an LP-formulation for the problem with two job sizes and show that it has an integral optimal solution.•We also present a PTAS for the case that the MjMj's are intervals of the same length.•We give a simple algorithm for the case that |Mj|=2|Mj|=2 (graph balancing problem) with ratio 11/6.

We consider some special cases of the restricted assignment problem. In this scheduling problem on parallel machines, any job j   can only be assigned to one of the machines in its given subset MjMj of machines. We give an LP-formulation for the problem with two job sizes and show that it has an integral optimal solution. We also present a PTAS for the case that the MjMj's are intervals of the same length. Further, we give a new and very simple algorithm for the case that |Mj|=2|Mj|=2 (known as the graph balancing problem) with ratio 11/6.