Graph Balancing: A Special Case of Scheduling Unrelated Parallel Machines

Abstract

We design a 1.75-approximation algorithm for a special case of scheduling parallel machines to minimize the makespan, namely the case where each job can be assigned to at most two machines, with the same processing time on either machine. (This is a special case of so-called restricted assignment, where the set of eligible machines can be arbitrary for each job.) This is the first improvement of the approximation ratio 2 of Lenstra, Shmoys, and Tardos (Math. Program. 46:259-271, 1990), to a smaller constant for any special case with unbounded number of machines and unbounded processing times.

We conclude by showing integrality gaps of several relaxations of related problems.

Keywords

• combinatorial optimization
• linear programming
• scheduling
• makespan minimization
• restricted assignment