| Article ID: | iaor20072877 |
| Country: | Netherlands |
| Volume: | 35 |
| Issue: | 1 |
| Start Page Number: | 61 |
| End Page Number: | 68 |
| Publication Date: | Jan 2007 |
| Journal: | Operations Research Letters |
| Authors: | Kis Tams, Kpolnai Richrd |
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.