Full Text:   <1196>

CLC number: O223

On-line Access: 

Received: 

Revision Accepted: 2004-08-08

Crosschecked: 0000-00-00

Cited: 4

Clicked: 3725

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2005 Vol.6 No.6 P.591~595

http://doi.org/10.1631/jzus.2005.A0591


Semi on-line scheduling for maximizing the minimum machine completion time on three uniform machines


Author(s):  LUO Run-zi, SUN Shi-jie

Affiliation(s):  Department of Mathematics, Shanghai University, Shanghai 200444, China

Corresponding email(s):   luo_rz@eyou.com, sun_sj@eyou.com

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


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≤rs) 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.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[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>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE