Article ID Journal Published Year Pages File Type
1143230 Operations Research Letters 2007 8 Pages PDF
Abstract
We consider the scheduling of groups of identical jobs on related machines with sequence independent setup times. We provide a 2-approximation algorithm for minimizing the makespan. The second result is a truthful, polynomial time, randomized mechanism for the batch scheduling problem with a deterministic approximation guarantee of 4.
Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
Approximations and auctions for scheduling batches on related machines
Authors
, ,