This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Moulin, H. Search for Related Content

Minimizing the Worst Slowdown: Offline, Online

Economics Department, Rice University, Houston, Texas 77005
moulin{at}rice.edu

We look for protocols (service disciplines) setting an upper bound on the slowdown (expected sojourn time divided by job size) a job may face, irrespective of the processing times of other jobs. We call this worst slowdown the liability of a job. In a scheduling problem with identical release dates, allowing the server to randomize the order of service cuts almost in half the liability profiles feasible under deterministic protocols. The same is true if cash transfers are feasible and users have linear waiting costs. When release times are arbitrary, we characterize liability functions implementable by a deterministic online protocol, where the liability depends on the number of jobs in the queue upon release of the job. In an M/D/1 queue with a given arrival rate, the liability of a job is at least its slowdown when all other jobs are of the same size. We conjecture that this liability is feasible online, and identify a probabilistic protocol exceeding it by at most 130%.

Subject classifications: scheduling; queueing; slowdown; probabilistic protocols.
History: Received April 2006; revision received August 2006; accepted September 2006.