Minimizing the Worst Slowdown: Offline, Online

Abstract

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%.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 11 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.