# ICS 269, Winter 1997: Theory Seminar

## 31 Jan 1997:

Scheduling with Conflicts and Applications to Traffic Signal
Control

Vitus J. Leung, ICS,
UC Irvine

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 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. Our results
focus on two special classes of graphs motivated by our
applications: bipartite graphs and interval graphs. In all of the
upper bounds, we devise algorithms which maintain a set of
invariants which bound the accumulation of jobs on cliques (in the
case of bipartite graphs, edges) in the graph. The lower bounds
show that the invariants maintained by the algorithms are tight to
within a constant factor.
The best competitive ratio achievable by any online algorithm
for the maximum completion time on interval or bipartite graphs is
Omega(*n*), where *n* is the number of nodes in the
conflict graph. As a result, we study scheduling with conflicts
under probabilistic assumptions about the input. Each node *i*
has a value *p*_{i} such that a job arrives at node
*i* in any given time unit with probability *
p*_{i}. Arrivals at different nodes and during different
time periods are independent. We focus on distributions where the
expected time to complete the jobs that arrive in a single time
unit is less than 1. Under these assumptions, 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.

For the specific application of traffic signal control, we
simulate our simple K_{2,2} algorithm on a traffic network
with Poisson arrivals at the edges of the network and Robertson's
platoon dispersion model within the network. In some cases, our
simple algorithm achieves significant improvements over actuated
control.

(Practice job interview talk.)