A novel bicriteria list scheduling with duplication for heterogeneous distributed systems
by Weipeng Jing; Yaqiu Liu; Qu Wu
International Journal of Modelling, Identification and Control (IJMIC), Vol. 17, No. 4, 2012

Abstract: In order to achieve high performance in heterogeneous distributed systems, the efficient scheduling strategy is critical. Most of the heuristics for this NP-hard problem are based on a very simple system model of the target parallel system where communication contention is not taken into account. In this paper we propose a novel bicriteria list scheduling framework for the (schedule length and reliability) on communication contention model. We take the primary-backup replication technique of each individual task of the dependency task graph given as a specification with respect to the desired failure rate. To solve this bicriteria optimisation problem, we consider the processor and the communication link failure rate as a constraint, and we minimise the schedule length. We are thus able to use a Pareto curve of non-dominated solutions so we can choose the compromise that fits user requirements best. Another innovation is that we realise the case without offline planned schedules and discuss dynamic planning and adaptation of DAG tasks. Experimental results fully demonstrate the usefulness of the proposed algorithms, which lead to efficient execution schemes, while guaranteeing a prescribed level of fault-tolerance.

Online publication date: Wed, 17-Dec-2014

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Modelling, Identification and Control (IJMIC):
Login with your Inderscience username and password:

Username:        Password:          Forgotten your password?

Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com