Scheduling with task replication on desktop grids: theoretical and experimental analysis

Eduardo C. Xavier (), Robson R. S. Peixoto () and Jefferson L. M. Silveira ()
Additional contact information
Eduardo C. Xavier: University of Campinas (UNICAMP)
Robson R. S. Peixoto: University of Campinas (UNICAMP)
Jefferson L. M. Silveira: University of Campinas (UNICAMP)

Journal of Combinatorial Optimization, 2015, vol. 30, issue 3, No 8, 520-544

Abstract: Abstract Our main objective in this paper is to study the possible benefits of using task replication when generating a schedule in a desktop grid. We consider the problem of constructing a schedule in an environment where machines’ speeds may be unpredictable and the objective is to minimize the makespan of the schedule. Another considered objective is to minimize the total processor cycle consumption. First we provide a theoretical study of a well known algorithm that makes use of replication: the WQRxx algorithm. We prove approximation ratios for this algorithm in different scenarios, and also show that such ratios are tight. We propose a simple interface and show how to add replication to any scheduling algorithm using this interface. We also prove approximation ratios for any algorithm that uses this interface. We then extend several well known algorithms to generate schedules with replication via the interface, and present computational simulations comparing the quality of the solutions of these algorithms with the addition of replication.

Keywords: Desktop grid Scheduling; Approximation algorithms; Task replication (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9650-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:30:y:2015:i:3:d:10.1007_s10878-013-9650-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9650-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().