Scheduling Algorithms for new Emerging Applications

May, 29th - June, 2nd 2006, CIRM, Marseille, France

An auction mechanism for scheduling batches on uniform machines

SpeakerTamas Kis

In a centralized scheduling system all decisions are taken by one author- ity. In contrast, when machines are responsible for their own schedules, a control mechanism is needed for distributing the jobs between the machines. Inspired by the results of Nisan and Ronen, and of Archer and Tardos on job allocation problems, we have studied allocation of batches in a uniform machine environment.

In a job auction, a dispatcher wants to assign jobs to machines the ob- jective being to minimize the makespan. But it does not know everything about the capabilities of the machines, i.e., it does not know their speeds. Therefore, the dispatcher announces all job parameters and asks a process- ing speed (a bid) from each machine. The machines, in turn, send-in some claimed speed. Based on the collected speeds, the dispatcher allocates the batches to the machines and computes a payment. The cost of each machine is proportional to the true time spent on processing the assigned batches. Hence, a machine could make profit by bidding differently to its true speed. However, if the machines do not provide their true speed, the dispatcher may allocate jobs poorly, i.e., the resulting schedule is far from the optimum. Hence, the dispatcher has to use a payment scheme which incite the machines telling their true speeds.

The above scheme has been described by Archer and Tardos for job auc- tions in a uniform machine environment. We extend their results to batch scheduling problems, where each batch consists of identical jobs and setups do not depend on the sequence of processing. Our main contribution is a polyno- mial time auction mechanism (allocation algorithm + payment calculation) for scheduling the batches on uniform machines to minimize makespan.