Full Text:   <1644>

CLC number: TP393

On-line Access: 

Received: 2000-12-18

Revision Accepted: 2001-03-18

Crosschecked: 0000-00-00

Cited: 0

Clicked: 3992

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2002 Vol.3 No.1 P.60-64


Algorithms for semi on-line multiprocessor scheduling problems

Author(s):  HE Yong, YANG Qi-fan, TAN Zhi-yi, YAO En-yu

Affiliation(s):  Department of Mathematics, Zhejiang University, Hangzhou 310027, China; more

Corresponding email(s): 

Key Words:  analysis of algorithm, on-line scheduling, worst-case ratio

Share this article to: More

HE Yong, YANG Qi-fan, TAN Zhi-yi, YAO En-yu. Algorithms for semi on-line multiprocessor scheduling problems[J]. Journal of Zhejiang University Science A, 2002, 3(1): 60-64.

@article{title="Algorithms for semi on-line multiprocessor scheduling problems",
author="HE Yong, YANG Qi-fan, TAN Zhi-yi, YAO En-yu",
journal="Journal of Zhejiang University Science A",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T Algorithms for semi on-line multiprocessor scheduling problems
%A HE Yong
%A YANG Qi-fan
%A TAN Zhi-yi
%A YAO En-yu
%J Journal of Zhejiang University SCIENCE A
%V 3
%N 1
%P 60-64
%@ 1869-1951
%D 2002
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2002.0060

T1 - Algorithms for semi on-line multiprocessor scheduling problems
A1 - HE Yong
A1 - YANG Qi-fan
A1 - TAN Zhi-yi
A1 - YAO En-yu
J0 - Journal of Zhejiang University Science A
VL - 3
IS - 1
SP - 60
EP - 64
%@ 1869-1951
Y1 - 2002
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2002.0060

In the classical multiprocessor scheduling problems, it is assumed that the problems are considered in off-line or on-line environment. But in practice, problems are often not really off-line or on-line but somehow in between. This means that, with respect to the on-line 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 on-line ones. The authors studied two semi on-line multiprocessor scheduling problems, in which, the total processing time of all tasks is known in advance, or all processing times lie in a given interval. They proposed approximation algorithms for minimizing the makespan and analyzed their performance guarantee. The algorithms improve the known results for 3 or more processor cases in the literature.

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


[1] Albers,S., 1997. Better bounds for on-line scheduling. Proc. 29th Annual ACM Symp. on Theory of Computing, p.130-139.

[2] Bartal,Y., Fiat,A., Karloff,A., et al., 1992. New algorithm for an ancient scheduling problem. Proc. 24th Annual ACM Symp. on Theory of Computing, p.51-58.

[3] Chen,B., Vliet,A.van, Woeginger,G., 1995. New lower and upper bounds for on-line scheduling. Oper. Res. Letters, 18: 127-131.

[4] Faigle,U., Kern,W., Tur

[5] Galambos,G., Woeginger,G., 1993. An on-line scheduling heuristic with better worst-case ratio than Graham's list scheduling. SIAM J. on Computing, 22:349-355.

[6] Graham,R.L., 1966. Bounds for certain multiprocessing anomalies. Bell System Tech., 45:1563-1581.

[7] He,Y., 2000. The optimal online parallel machine scheduling. Computers & Mathematics with Applications, 39:117-121.

[8] He,Y., Zhang,G., 1999. Semi on-line scheduling on two identical machines. Computing, 62:179-187.

[9] Karger,D.R., Phillips,S.J., Torng,E., 1996. A better algorithm for an ancient scheduling algorithm. J. of Algorithms, 20:400-430.

[10] Kellerer,H., Kotov,V., Speranza,M., et al., 1997. Semi on-line algorithms for the partition problem. Oper. Res. Letters, 21:235-242.

[11] Liu,W.P., Sidney,J.B., Vliet,A.van, 1996. Ordinal algorithms for parallel machine scheduling. Oper. Res. Letters, 18:223-232.

Open peer comments: Debate/Discuss/Question/Opinion


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