New Challenges in Scheduling Theory

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

Selfish scheduling with multiple tasks agents

SpeakerJohanne Cohen

Co-authorFanny Pascual

We study coordination mechanisms for selfish scheduling. Whereas previous work consider that each agent owns only one task, we consider in this paper the setting where two agents, each one having a set of tasks, share a set of parallel identical machines. Each agent chooses the machine on which she assigns each of her tasks, and her aim is to minimize the average completion times of her tasks. A coordination mechanism consists in giving each machine a scheduling policy. We study conditions needed to obtain good coordination mechanisms, and we study the stability of the schedules obtained with three standard coordination mechanisms. Our results show that standard coordination mechanisms are not robust with agents owning several tasks, as pure Nash equilibria do not exist. Furthermore some of these policy may induce schedules as unstable as wanted, whatever the number of machines is.