کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
436378 689996 2008 22 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Probabilistic analysis for scheduling with conflicts
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 396, Issues 1–3, 10 May 2008, Pages 158-179