Full Text:
<2612>
CLC number: O223
On-line Access:
Received:
Revision Accepted: 2004-08-08
Crosschecked: 0000-00-00
Cited: 4
Clicked: 5719
Semi on-line scheduling for maximizing the minimum machine completion time on three uniform machines
| |||||||||||||
LUO Run-zi, SUN Shi-jie. Semi on-line scheduling for maximizing the minimum machine completion time on three uniform machines[J]. Journal of Zhejiang University Science A, 2005, 6(6): 591-595.
@article{title="Semi on-line scheduling for maximizing the minimum machine completion time on three uniform machines",
author="LUO Run-zi, SUN Shi-jie",
journal="Journal of Zhejiang University Science A",
volume="6",
number="6",
pages="591-595",
year="2005",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.2005.A0591"
}
%0 Journal Article
%T Semi on-line scheduling for maximizing the minimum machine completion time on three uniform machines
%A LUO Run-zi
%A SUN Shi-jie
%J Journal of Zhejiang University SCIENCE A
%V 6
%N 6
%P 591-595
%@ 1673-565X
%D 2005
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2005.A0591
TY - JOUR
T1 - Semi on-line scheduling for maximizing the minimum machine completion time on three uniform machines
A1 - LUO Run-zi
A1 - SUN Shi-jie
J0 - Journal of Zhejiang University Science A
VL - 6
IS - 6
SP - 591
EP - 595
%@ 1673-565X
Y1 - 2005
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2005.A0591
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.
[1] Azar, Y., Epstein, L., 1997. On-line Machine Covering, Algorithms-ESA’97. Lecture Notes in Computer Science 1284, Springer Verlag, p.23-36.
[2] Csirik, J., Kellerer, H., Woeginger, G., 1992. The exact LPT-bound for maximizing the minimum completion time. Oper. Res. Letters, 11:281-287.
[3] Deuermeyer, B.L., Friesen, D.K., Langston, M.A., 1982. Scheduling to maximize the minimum processor finish time in a mutiprocessor system. SIAM J. Algorithms Discrete Methods, 3:190-196.
[4] Epstein, L., 2002. Tight Bounds for Bandwidth Allocation on two Links. Proc. of the 3rd ARACNE, p.39-50.
[5] Garey, M.R., Johnson, D.S., 1979. Computers and Intractability. W.H. Freeman and Company, San Francisco.
[6] He, Y., 2000. The optimal on-line parallel machine scheduling. Computers & Mathematics with Applications, 39:117-121.
[7] He, Y., 2001. Semi on-line scheduling problem for maximizing the minimum machine completion time. Acta Mathematica Applicate Sinica, 17:107-113 (in Chinese).
[8] He, Y., Zhang, G., 1999. Semi on-line scheduling on two identical machines. Computing, 62(3):179-187.
[9] He, Y., Tan, Z.Y., 2002. Ordinal on-line scheduling for maximizing the minimum machine completion time. Journal of Combinatorial Optimization, 6:199-206.
[10] He, Y., Tan, Z.Y., 2003. Randomized on-line and semi on-line scheduling on identical machines. Asia-Pacific Journal of Operational Research, 20:31-40.
[11] Woeginger, G., 1997. A polynomial time approximation scheme for minimizing the minimum machine completion time. Oper. Res. Letters, 20:149-154.
Open peer comments: Debate/Discuss/Question/Opinion
<1>