Minimizing the worst slowdown: offline, online

Minimizing the worst slowdown: offline, online

0.00 Avg rating0 Votes
Article ID: iaor20083055
Country: United States
Volume: 55
Issue: 5
Start Page Number: 876
End Page Number: 889
Publication Date: Sep 2007
Journal: Operations Research
Authors:
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%.

Reviews

Required fields are marked *. Your email address will not be published.