Donald Bren School of Information and Computer Sciences

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 graphs so that 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 goal is to bound the maximum response time of any job in the system. It has been previously shown [13] that the best competitive ratio achievable by any online algorithm for the maximum response 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 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.