| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 435508 | Theoretical Computer Science | 2009 | 7 Pages |
Abstract
We study two online problems on m uniform machines with speeds s1≤⋯≤sm. The problems are online in the sense that all jobs arrive over time. Each job’s characteristics, such as processing time and weight become known at its arrival time. For the first problem Q|rj,online|∑Cj, we prove that R-LIST algorithm is -competitive. For the second problem Q|rj,online,pmtn|∑wjCj, we show that WSPT-1 algorithm is 2-competitive if for i=1,…,m−1. Then we study a special case where s1=s2=⋯=sm−1≤sm. We obtain that algorithm WSPT-1 is 2-competitive if sm(m−2)≤s1(m−1).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
