Abstract: The paper investigates a semi on-line scheduling problem wherein the largest processing time of jobs done by three uniform machines M₁, M₂, M₃ is known in advance. A speed s_i (s₁=1, s₂=r, s₃=s, 1≤r≤s) is associated with machine M_i. Our goal is to maximize C_min-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.

Key words: Scheduling, Semi on-line, Competitive ratio

Please provide your name, email address and a comment

Your Name: Affili: E-Mail Address:

Comment (Please comment in English):


Verification Code(click to change a pic):