"On-line Admission Control and Packet Scheduling with Interleaving", 
Juan A. Garay, Joseph (Seffi) Naor, Bulent Yener, Peng Zhao, 
INFOCOM 2002.


In last Wednesday's Colloquium, Boaz Patt-shamir explained a competitive
buffer management model, and discuss some results about the natural greedy
algorithm, the optimal (off-line) algorithm, and a few new algorithm using
competitive analysis. 
In this talk, I will present a comprehensive study of the effect of
job interleaving by preemption on the utilization of a single server, also
using competitive analysis to measure the performance of the scheduling
algorithm.  I will first talk about a abstract level model and its
generality and applicability to many scenarios. then, I will describe two
scheduling models: with and without commitment, using the on-line
algorithm GREEDY and a new algorithm ALG respectively.  Through competitive
analysis, we will discuss the upper and lower bounds for each
case. Finally, we will quickly go through the simulation study and results.