New Challenges in Scheduling Theory

September, 12-17 2010, Centre CNRS "La Villa Clythia", Frejus

Online unrelated parallel machine scheduling with resource dependent processing times

SpeakerDeshi Ye

Co-author Guochuan Zhang

We consider a new variant of online unrelated machine scheduling. In addition to m unrelated machines, we are given a speeding-up renewable resource of k units. The processing time of a job is dependent on both the machine allocated and the amount of resource assigned. We assume that, the more units of resource a job receives, the smaller is its processing time. Moreover, at any time, the total amount of the resource simultaneously used by jobs are at most k. The jobs arrive over list and we have to irrevocably schedule the coming job without any future information. Our goal is to minimize the makespan. This problem contains online unrelated machine scheduling as a special case. Thus, any online algorithms cannot have a competitive ratio smaller than \Omega(logm). In this paper, we design an online algorithm that based on the framework of online primal-dual scheme. The competitive ratio is shown to be O(logm) + min{O(log k);O(mlogm)}, which is best possible if k is a polynomial of m.