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.)