Approximations and auctions for scheduling batches on related machines |
| |
| Authors: | Tamás Kis Richárd Kápolnai |
| |
| Institution: | a Computer and Automation Research Institute, Kende utca 13-17, 1111 Budapest, Hungary
b Budapest University of Technology and Economics, Magyar tudósok körútja 2/d, 1117 Budapest, Hungary |
| |
| 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: | Batch-scheduling Approximation-algorithms Auctions Mechanism design |
| 本文献已被 ScienceDirect 等数据库收录！ |
