Graph Balancing: A Special Case of Scheduling Unrelated Parallel Machines

Graph Balancing: A Special Case of Scheduling Unrelated Parallel Machines

0.00 Avg rating0 Votes
Article ID: iaor2014327
Volume: 68
Issue: 1
Start Page Number: 62
End Page Number: 80
Publication Date: Jan 2014
Journal: Algorithmica
Authors: , ,
Keywords: makespan, 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 (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.

Reviews

Required fields are marked *. Your email address will not be published.