Full Text:   <2680>

CLC number: TP393, O223

On-line Access: 

Received: 2004-02-10

Revision Accepted: 2004-07-03

Crosschecked: 0000-00-00

Cited: 0

Clicked: 6217

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
Open peer comments

Journal of Zhejiang University SCIENCE A 2005 Vol.6 No.1 P.20-26

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


Deterministic and randomized scheduling problems under the lp norm on two identical machines*


Author(s):  Ling Lin, Zhi-yi Tan, Yong He

Affiliation(s):  . Department of Mathematics, State Key Lab of CAD & CG, Zhejiang University, Hangzhou 310027, China

Corresponding email(s):   mathhey@zju.edu.cn

Key Words:  Semi-online, Scheduling, Randomization, Competitive ratio


LIN Ling, TAN Zhi-yi, HE Yong. Deterministic and randomized scheduling problems under the lp norm on two identical machines[J]. Journal of Zhejiang University Science A, 2005, 6(1): 20-26.

@article{title="Deterministic and randomized scheduling problems under the lp norm on two identical machines",
author="LIN Ling, TAN Zhi-yi, HE Yong",
journal="Journal of Zhejiang University Science A",
volume="6",
number="1",
pages="20-26",
year="2005",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.2005.A0020"
}

%0 Journal Article
%T Deterministic and randomized scheduling problems under the lp norm on two identical machines
%A LIN Ling
%A TAN Zhi-yi
%A HE Yong
%J Journal of Zhejiang University SCIENCE A
%V 6
%N 1
%P 20-26
%@ 1673-565X
%D 2005
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2005.A0020

TY - JOUR
T1 - Deterministic and randomized scheduling problems under the lp norm on two identical machines
A1 - LIN Ling
A1 - TAN Zhi-yi
A1 - HE Yong
J0 - Journal of Zhejiang University Science A
VL - 6
IS - 1
SP - 20
EP - 26
%@ 1673-565X
Y1 - 2005
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2005.A0020


Abstract: 
Parallel machine scheduling problems, which are important discrete optimization problems, may occur in many applications. For example, load balancing in network communication channel assignment, parallel processing in large-size computing, task arrangement in flexible manufacturing systems, etc., are multiprocessor scheduling problem. In the traditional parallel machine scheduling problems, it is assumed that the problems are considered in offline or online environment. But in practice, problems are often not really offline or online but somehow in-between. This means that, with respect to the online problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi-online ones. In this paper, the semi-online problem P2|decr|lp (p>1) is considered where jobs come in non-increasing order of their processing times and the objective is to minimize the sum of the lp norm of every machine’s load. It is shown that LS algorithm is optimal for any lp norm, which extends the results known in the literature. Furthermore, randomized lower bounds for the problems P2|online|lp and P2|decr|lp are presented.

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

References

[1] Alon, N., Azar, Y., Woeginger, G., 1998. Approximation schemes for scheduling. , J of Scheduling, 55-66. :55-66. 

[2] Avidor, A., Azar, Y., Sgall, J., 2001. Ancient and new algorithms for load balancing in the lp norm. , Algorithmica, 422-441. :422-441. 

[3] Azar, Y., Epstein, L., Richter, Y., 2002. All-norm Approximation Algorithms, Lecture Notes in Computer Science 2368, Springer-Verlag,:288-297. 

[4] Bartal, Y., Fiat, A., Karloff, H., 1995. New algorithms for an ancient scheduling problem. , J of Computer and System Science, 359-366. :359-366. 

[5] Chandra, A.K., Wong, C.K., 1975. Worst-case analysis of a placement algorithm related to storage allocation. , SIAM J on Computing, 249-263. :249-263. 

[6] Faigle, U., Kern, W., Turan, G., 1989. On the performance of online algorithms for partition problems. , Acta Cybernetica, 107-119. :107-119. 

[7] Graham, R.L., 1966. Bounds for certain multiprocessor anomalies. , Bell Systems Technical J, 1563-1581. :1563-1581. 

[8] Graham, R.L., 1969. Bounds on multiprocessing timing anomalies. , SIAM J on Applied Mathematics, 416-429. :416-429. 

[9] He, Y., Yang, Q.F., Tan, Z.Y., 2003. Semi online scheduling on parallel machines (I). , Applied MathematicsA J Chinese Universities, 105-114. :105-114. 

[10] He, Y., Yang, Q.F., Tan, Z.Y., 2003. Semi online scheduling on parallel machines (II). , Applied MathematicsA J Chinese Universities, 213-222. :213-222. 

[11] Leung, J.Y.T., Wei, W.D., 1995. Tighter bounds on heuristic for a partition problem. , Information Processing Letters, 51-57. :51-57. 

[12] Seiden, S., Sgall, J., Woeginger, G.J., 2000. Semi-on-line scheduling with decreasing job sizes. , Operations Research Letters, 215-221. :215-221. 


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 - 2024 Journal of Zhejiang University-SCIENCE