ICS Theory Group

ICS 269, Spring 2001: Theory Seminar


11 May 2001:
First-Fit Interval Scheduling with Three Links and Deterministic Service
George Lueker

Abstract: Following Coffman, Feldman, Kahale and Poonen, and Coffman, Robert, and Stolyar, we consider the stability of first-fit queuing systems for scheduling requests on an interval network. Both Hajek's theorem and fluid limits have been used as tools in the investigation of stability. We show how a variation of Hajek's theorem yields a fairly simple analysis for the case of 3 links and deterministic service.