ICS Theory Group

ICS 269, Spring 1997: Theory Seminar


23 May 1997:
Final Public Oral Dissertation Defense
Vitus Leung, ICS, UC Irvine

In this dissertation, we develop a model for scheduling jobs that may be competing for mutually exclusive resources. The conflicts between jobs are modeled by a conflict graph, so that the set of all concurrently running jobs must form an independent set in the graph. This model is natural and general enough to have applications in a variety of settings; however, we are motivated by the following two specific applications: traffic intersection control and session scheduling in high speed local area networks with spatial reuse. For all the graphs we address, we focus on the problem of minimizing the maximum response time of any job that enters the system. For the specific graph which arises in the traffic intersection control problem, we show a simple algorithm which achieves the optimal competitive ratio. Motivated by the second application, we also give an algorithm for interval graphs.

Since I have already presented some of the details in the upper bounds, I will be presenting some of the details in the lower bounds. The best competitive ratio achievable by any online algorithm even on a path of n nodes is Omega(n). As a result, we turn to scheduling with conflicts under probabilistic assumptions about the input. Each node i has a value pi such that a job arrives at node i in any given time unit with probability pi. Arrivals at different nodes and during different time periods are independent. Under reasonable assumptions on the input sequence, we are able to obtain a bounded competitive ratio for an arbitrary conflict graph. In addition, if the conflict graph is a perfect graph, we give an algorithm whose competitive ratio converges to 1.

Finally, we discuss simulation results for the traffic signal control problem. Using the methodology of Recker, Ramanathan, Yu, and McNally and a modification of their software, we show that some of our algorithms achieve significant improvements over full-actuated control, the most advanced traffic signal control method in the public domain.