DIMACS TR: 2001-15
On-line Admission Control and Job Scheduling with Preemption
Authors: Juan Garay, Joseph (Seffi) Naor, B\"ulent Yener and Peng Zhao
ABSTRACT
This paper studies the effect of preemption on the throughput of a
single ``communication channel'' where requests arrive with a given
processing time and slack. The problem is to decide which requests to
serve so as to maximize the channel's utilization. This simple model
captures many situations, both at the application (e.g., delivery of
video) as well as at the network/transmission levels (e.g., scheduling
of jobs at a switch). The problem is on-line in nature, and thus we
use competitive analysis for measuring the performance of our
scheduling algorithms. We consider two modes of operation: with and
without commitment, and derive upper and lower bounds for each case.
Since the competitive analysis is based on the worst-case scenario,
the average-case performance of the on-line algorithms are examined by
a simulation study.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-15.ps.gz
DIMACS Home Page