TY - JOUR
T1 - Competitive analysis of fundamental scheduling algorithms on a fault-prone machine and the impact of resource augmentation
AU - Fernández Anta, Antonio
AU - Georgiou, Chryssis
AU - Kowalski, Dariusz R.
AU - Zavou, Elli
N1 - Funding Information:
This research was partially supported by the grant TEC2014-55713-R from the Spanish Ministry of Economy and Competitiveness (MINECO), the Cloud4BigData grant (S2013/ICE-2894) from Madrid Regional Government (CM), co-financed by Structural Funds of the European Union (FSE & FEDER), and the FPU12/00505 grant from the Spanish Ministry of Education, Culture and Sports (MECD). In addition, the second author was supported by the grant UCY/ED2015 of the University of Cyprus and the third author by the grant 2015/17/B/ST6/01897 of the National Science Centre, Poland.
Publisher Copyright:
© 2016 Elsevier B.V.
PY - 2018/1
Y1 - 2018/1
N2 - 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).
AB - 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).
KW - Competitive analysis
KW - Different task processing times
KW - Failures
KW - Online algorithms
KW - Resource augmentation
KW - Scheduling
UR - http://www.scopus.com/inward/record.url?scp=84977480329&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84977480329&partnerID=8YFLogxK
U2 - 10.1016/j.future.2016.05.042
DO - 10.1016/j.future.2016.05.042
M3 - Article
AN - SCOPUS:84977480329
SN - 0167-739X
VL - 78
SP - 245
EP - 256
JO - Future Generation Computer Systems
JF - Future Generation Computer Systems
ER -