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


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