Institute for Mathematical Behavioral Sciences

Minimizing the slowdown (sojourn time divided by job processing time, or simply job size) is a key concern of fairness and incentive compatibility in scheduling and queuing problems where job sizes are very heterogeneous. It is at the heart of the debate between Shortest Remaining Job First (SRJF) and Processor Sharing (PS). See references below. We look for protocols (service disciplines) capping the worst slowdown a job may face when it is completely ignorant of other jobs’ size and has only limited information on their number. We call this worst slowdown the liability of the job in question. In the scheduling and o.-line queuing problems, the server knows all jobs past present and future, and their size.

• A deterministic protocol can guarantee the liability a(i) to job i if and only if PN1

a(i)+1 ¡Ü 1, where N is the, possibly infinite, set of users.

• If the order of service can be randomized and we minimize the worst expected slowdown, a probabilistic protocol can guarantee the liability a(i) to job i if and only if PN1 2a(i)-1 ¡Ü 1, an improvement of nearly 100% over the deterministic case.

• If cash transfers are feasible and waiting costs per unit of time are constant, an e.cient protocol can guarantee the liability a(i) to job i if and only if PN12a(i)-1 ¡Ü 1.

An on-line protocol only depends upon past and present jobs. A deterministic on-line server can guarantee the liability a(r) to job i, where r is the number of jobs in the queue when i was released, if and only if P�‡1 1a(r)+1 ¡Ü 1. The corresponding protocol is an e.cient version of a weighted processor sharing rule adapted from [3]. I do not know if randomization allows a lower cap. When the arrival of new jobs is Poisson with rate ë, the liability may depend only upon this rate (a measure of the average number of users in the system) and one’s own job size. A lower bound on the best liability a probabilistic protocol can achieve is 1 1-ë·x . I conjecture that this bound is achieved, and have identified a protocol achieving the liability 1.5 1-ë·x . The protocol is a random compromise between FIFO and FILO.

[1].M. Bender, S, Chakrabarti, S. Muthukrishnan, Flow and stretch metrics for scheduling continuous job streams. Proc. 9th ACM-SIAM Symposium on discrete algorithms, 1998.

[2]. N. Bansal, M. Harchol-Balter, Analysis of SRPT scheduling: investigating unfairness, Proc. ACM Sigmetrics 2001 Conference on Measurement and Modeling of Computer Systems.

[3]. E. Friedman and S. Henderson, Fairness and e.ciency in processorsharing protocols to minimize sojourn time, mimeo Cornell Univ. 2002