Full Text:
<2416>
CLC number: TP393; O223
On-line Access:
Received: 2005-02-10
Revision Accepted: 2005-04-19
Crosschecked: 0000-00-00
Cited: 18
Clicked: 5197
Optimal online algorithms for scheduling on two identical machines under a grade of service
| |||||||||||||
Jiang Yi-wei, He Yong, Tang Chun-mei. Optimal online algorithms for scheduling on two identical machines under a grade of service[J]. Journal of Zhejiang University Science A, 2006, 7(3): 309-314.
@article{title="Optimal online algorithms for scheduling on two identical machines under a grade of service",
author="Jiang Yi-wei, He Yong, Tang Chun-mei",
journal="Journal of Zhejiang University Science A",
volume="7",
number="3",
pages="309-314",
year="2006",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.2006.A0309"
}
%0 Journal Article
%T Optimal online algorithms for scheduling on two identical machines under a grade of service
%A Jiang Yi-wei
%A He Yong
%A Tang Chun-mei
%J Journal of Zhejiang University SCIENCE A
%V 7
%N 3
%P 309-314
%@ 1673-565X
%D 2006
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2006.A0309
TY - JOUR
T1 - Optimal online algorithms for scheduling on two identical machines under a grade of service
A1 - Jiang Yi-wei
A1 - He Yong
A1 - Tang Chun-mei
J0 - Journal of Zhejiang University Science A
VL - 7
IS - 3
SP - 309
EP - 314
%@ 1673-565X
Y1 - 2006
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2006.A0309
Abstract: This work is aimed at investigating the online scheduling problem on two parallel and identical machines with a new feature that service requests from various customers are entitled to many different grade of service (GoS) levels, so each job and machine are labelled with the GoS levels, and each job can be processed by a particular machine only when its GoS level is no less than that of the machine. The goal is to minimize the makespan. For non-preemptive version, we propose an optimal online algorithm with competitive ratio 5/3. For preemptive version, we propose an optimal online algorithm with competitive ratio 3/2.
[1] Azar, Y., Naor, J., Rom, R., 1995. The competitiveness of on-line assignments. Journal of Algorithms, 18(2):221-237.
[2] Epstein, L., Favrholdt, L., 2002. Optimal preemptive semi-online scheduling to minimize makespan on two related machines. Operations Research Letters, 30(4):269-275.
[3] He, Y., Jiang, Y.W., 2004. Optimal algorithms for semi-online preemptive scheduling problems on two uniform machines. Acta Informatica, 40(5):367-383.
[4] Hwang, H., Chang, S., Lee, K., 2004. Parallel machine scheduling under a grade of service provision. Computers & Operations Research, 31(12):2055-2061.
[5] Lee, C.Y., 1991. Parallel machine scheduling with non-simultaneous machine available time. Discrete Applied Mathematics, 30(1):53-61.
[6] Lee, C.Y., He, Y., Tang, G.C., 2000. A note on “Parallel machine scheduling with non-simultaneous machine available time”. Discrete Applied Mathematics, 100(1-2):133-135.
[7] Lenstra, J.K., Shmoys, D.B, Tardos, N.E., 1990. Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming, 46(1-3):259-271.
[8] Lin, G., He, Y., Yao, Y., Lu, H., 1997. Exact bounds of the modified LPT algorithms applying to parallel machines scheduling with non-simultaneous machine available times. Applied Math.-JCU, 12B:109-116.
Open peer comments: Debate/Discuss/Question/Opinion
<1>