ICS Theory Group

ICS 269, Winter 1996: Theory Seminar


19 January 1996:
Scheduling with Conflicts,
and Applications to Traffic Signal Control
Vitus Leung, ICS, UC Irvine

In this paper, we consider the scheduling of jobs that may be competing for mutually exclusive resources. We model the conflicts between jobs with a conflict graph, so that all concurrently running jobs must form an independent set in the graph. We believe that 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. In both of these applications, guaranteeing the best turnaround time to any job entering the system is important. Our results focus on two special classes of graphs motivated by our applications: bipartite graphs and interval graphs. Although the algorithms for bipartite and intervals graphs are quite different, the bounds they achieve are the same: we prove that for any sequence of jobs in which the maximum completion time of a job in the optimal schedule is bounded by A, the algorithm can complete every job in time O(n^3 A^2). n is the number of nodes in the conflict graph. We also show that the best competitive ratio achievable by any online algorithm for the maximum completion time on interval or bipartite graphs is Omega(n).

(Practice talk for Vitus' SODA '96 presentation; joint work with Sandy Irani. Full paper available.)