Full Text:   <1177>

CLC number: TP393; O223

On-line Access: 

Received: 2005-02-10

Revision Accepted: 2005-04-19

Crosschecked: 0000-00-00

Cited: 18

Clicked: 3277

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2006 Vol.7 No.3 P.309~314

http://doi.org/10.1631/jzus.2006.A0309


Optimal online algorithms for scheduling on two identical machines under a grade of service


Author(s):  Jiang Yi-wei, He Yong, Tang Chun-mei

Affiliation(s):  Laboratory of Information and Optimization Technologies, Ningbo Institute of Technology, Zhejiang University, Ningbo 315100, China; more

Corresponding email(s):   jywzju@163.com

Key Words:  Online algorithm, Competitive analysis, Parallel machine scheduling, Grade of service (GoS)


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.

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

Reference

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

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