Prompt Scheduling for Selfish Agents

23^rd May 2018, 13:00
Nicos Protopapas
University of Liverpool

Abstract

An online mechanism for scheduling jobs to minimize the sum of weighted completion times is proposed. An unknown number of jobs, controlled by strategic agents need to be scheduled in a set of identical machines. The jobs arrive over time, have private values for processing time and weight and once their processing starts they cannot be delayed. Their aim is to minimize their personal cost. The proposed mechanism offers to each agent a menu of possible slots in machines and each job buys one.

Additional Materials

• https://arxiv.org/abs/1804.03244