Full Text:
<2253>
CLC number: TP393
On-line Access:
Received: 2000-12-18
Revision Accepted: 2001-03-18
Crosschecked: 0000-00-00
Cited: 0
Clicked: 4602
Algorithms for semi on-line multiprocessor scheduling problems
| |||||||||||||
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",
volume="3",
number="1",
pages="60-64",
year="2002",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.2002.0060"
}
%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
TY - JOUR
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
Abstract: 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.
[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
<1>