کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4950274 1364283 2018 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Competitive analysis of fundamental scheduling algorithms on a fault-prone machine and the impact of resource augmentation
ترجمه فارسی عنوان
تجزیه و تحلیل رقابتی الگوریتم های برنامه ریزی اساسی بر روی یک ماشین دارای خطا و تاثیر افزایش منابع
کلمات کلیدی
برنامه ریزی؛ الگوریتم های آنلاین؛ زمان پردازش کارهای مختلف؛ شکست؛ تحلیل رقابتی؛ افزایش منابع
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی


- Worst-case analysis of fault-tolerant properties of popular scheduling algorithms.
- Competitive analysis regarding completed/pending load and latency of the algorithms.
- Use of resource augmentation to achieve and/or to improve their performance.
- Differences of scheduling policies based either on arrival time or size of tasks.
- All deterministic and work-conserving algorithms require speedup to be competitive.

Reliable task execution in machines that are prone to unpredictable crashes and restarts is both challenging and of high importance, but not much work exists on the analysis of such systems. We consider the online version of the problem, with tasks arriving over time at a single machine under worst-case assumptions. We analyze the fault-tolerant properties of four popular scheduling algorithms: Longest In System (LIS), Shortest In System (SIS), Largest Processing Time (LPT) and Shortest Processing Time (SPT). We use three metrics for the evaluation and comparison of their competitive performance, namely, completed load, pending load and latency. We also investigate the effect of resource augmentation in their performance, by increasing the speed of the machine. Hence, we compare the behavior of the algorithms for different speed intervals and show that there is no clear winner with respect to all the three considered metrics. While SPT is the only algorithm that achieves competitiveness on completed load for small speed, LIS is the only one that achieves competitiveness on latency (for large enough speed).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Future Generation Computer Systems - Volume 78, Part 1, January 2018, Pages 245-256
نویسندگان
, , , ,