Scheduling with conflicts on bipartite and interval graphs

Scheduling with conflicts on bipartite and interval graphs

0.00 Avg rating0 Votes
Article ID: iaor2008164
Country: United Kingdom
Volume: 6
Issue: 3
Start Page Number: 287
End Page Number: 307
Publication Date: May 2003
Journal: Journal of Scheduling
Authors: ,
Keywords: communications, transportation: road, graphs
Abstract:

In this paper, we consider the on-line 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. The cost function we use is maximum response time. 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. For a specific graph which arises in the traffic intersection control problem, we show a simple algorithm which achieves the optimal competitive ratio.

Reviews

Required fields are marked *. Your email address will not be published.