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

• Published in: Journal of combinatorial optimization 2015-10, Vol.30 (3), p.520-544
• Main Authors: Xavier, Eduardo C., Peixoto, Robson R. S., da Silveira, Jefferson L. M.
• Format: Article
• Language: English
• Subjects: Combinatorics; Convex and Discrete Geometry; Mathematical Modeling and Industrial Mathematics; Mathematics; Mathematics and Statistics; Operations Research/Decision Theory; Optimization; Theory of Computation
• ISSN: 1382-6905; 1573-2886
• DOI: 10.1007/s10878-013-9650-8

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.