کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
9655860 685323 2005 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On-line Chain Partitioning as a Model for Real-time Scheduling
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On-line Chain Partitioning as a Model for Real-time Scheduling
چکیده انگلیسی
We consider on-line chain partitioning of a poset as a theoretical model for some variant of tasks scheduling. Restricting ourselves to interval orders given by its representation the problem is equivalent to the coloring problem of interval graphs. We prove that up-growing variant of on-line chain partitioning of interval orders given by its representation has an optimal solution (Nearest-Fit algorithm). We also consider on-line chain partitioning of interval orders without representation and prove the lower bound for the up-growing version (3w/2). Moreover we show that there is no on-line algorithm constructing the representation of interval orders and graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Theoretical Computer Science - Volume 140, 18 November 2005, Pages 15-29
نویسندگان
,