Donald Bren School of Information and Computer Sciences

In this paper, we discuss simulation results for the traffic signal control problem. Our algorithms are motivated by theoretical results from 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. 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 have shown [14] a simple algorithm which achieves the optimal competitive ratio. We have also studied 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, if the conflict graph is a perfect graph, we have given [15] an algorithm whose competitive ratio converges to 1. 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.