Minimizing the Worst Slowdown: Off-Line and On-Line
Herve J. Moulin · RePEc: Research Papers in Economics · 2005
Minimizing the slowdown (expected sojourn time divided by job size) is a key concern of fairness in scheduling and queuing problems where job sizes are very heterogeneous. We look for protocols (service disciplines) capping the worst slowdown (called here liability) ajob may face no matter how large (or small) the other jobs are. In the scheduling problem (all jobs released at the same time), allowing the server to randomize the order of service cuts almost in half the liability profiles feasible under deterministic protocols. The same statement holds if cash transfers are feasible and users have linear waiting costs. In a queuing problem (release times of jobs are arbitrary), we can construct a deterministic on-line (non anticipative) protocol guaranteeing the liability θr to job i, whereris the number of jobs in the queue when i was released, if and only if P∞ 1 1 ≤ 1. When the θr arrival of new jobs is Poisson with rate λ, the liability of a job of size x is no smaller than its slowdown when all other jobs are of the same 1 size, namely