Randomized on-line scheduling on two uniform machines

Randomized on-line scheduling on two uniform machines

0.00 Avg rating0 Votes
Article ID: iaor20021711
Country: United Kingdom
Volume: 4
Issue: 2
Start Page Number: 71
End Page Number: 92
Publication Date: Mar 2001
Journal: Journal of Scheduling
Authors: , , , ,
Abstract:

We study the problem of on-line scheduling on two uniform machines with speeds 1 and s ⩾ 1. A φ ≈ 1.61803 competitive deterministic algorithm was already known. We present the first randomized results for this problem: We show that randomization does not help for speeds s ⩾ 2, but does help for all s < 2. We present a simple memoryless randomized algorithm with competitive ratio (4 – s)(1 + s)/4 ⩽ 1.56250. We analyse other randomized algorithms that demonstrate that the randomized competitive ratio is at most 1.52778 for any s. These algorithms are barely random, i.e. they use only a constant number of random bits. Finally, we present a 1 + s/(s2 + s + 1) competitive deterministic algorithm for the preemptive version of this problem. For any s, it is best possible even among randomized preemptive algorithms.

Reviews

Required fields are marked *. Your email address will not be published.