Probabilistic analysis for scheduling with conflicts

In this paper, we consider scheduling 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. Our goal is to bound the maximum response time of any job in the system. We adopt a discrete model of time and assume that each job requires one time unit to be completed once it is started. It has been previously shown [S. Irani, V. Leung, Scheduling with conflicts, and applications to traffic signal control, in: Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 1996] that the best competitive ratio achievable by any online algorithm is Ω(n), where n is the number of nodes in the 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 value for the pi’s, 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.