|
|
|
| Semi on-line scheduling for maximizing the minimum machine completion time on three uniform machines |
| LUO Run-zi, SUN Shi-jie |
| Department of Mathematics, Shanghai University, Shanghai 200444, China |
|
|
|
Abstract The paper investigates a semi on-line scheduling problem wherein the largest processing time of jobs done by three uniform machines M1, M2, M3 is known in advance. A speed si (s1=1, s2=r, s3=s, 1£r£s) is associated with machine Mi. Our goal is to maximize Cmin-the minimum workload of the three machines. We present a min3 algorithm and prove its competitive ratio is max{r+1,(3s+r+1)/(1+r+s)}, with the lower bound being at least max{2,r}. We also claim the competitive ratio of min3 algorithm cannot be improved and is the best possible for 1£s£2, r=1.
|
|
|
|
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
