Full Text:   <2143>

CLC number: TP393; O223

On-line Access: 

Received: 2006-01-28

Revision Accepted: 2006-05-03

Crosschecked: 0000-00-00

Cited: 3

Clicked: 4502

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2007 Vol.8 No.1 P.127-133

http://doi.org/10.1631/jzus.2007.A0127


Online algorithms for scheduling with machine activation cost on two uniform machines


Author(s):  HAN Shu-guang, JIANG Yi-wei, HU Jue-liang

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

Corresponding email(s):   jywzju@163.com

Key Words:  Online algorithm, Competitive analysis, Uniform machine scheduling, Machine activation cost


HAN Shu-guang, JIANG Yi-wei, HU Jue-liang. Online algorithms for scheduling with machine activation cost on two uniform machines[J]. Journal of Zhejiang University Science A, 2007, 8(1): 127-133.

@article{title="Online algorithms for scheduling with machine activation cost on two uniform machines",
author="HAN Shu-guang, JIANG Yi-wei, HU Jue-liang",
journal="Journal of Zhejiang University Science A",
volume="8",
number="1",
pages="127-133",
year="2007",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.2007.A0127"
}

%0 Journal Article
%T Online algorithms for scheduling with machine activation cost on two uniform machines
%A HAN Shu-guang
%A JIANG Yi-wei
%A HU Jue-liang
%J Journal of Zhejiang University SCIENCE A
%V 8
%N 1
%P 127-133
%@ 1673-565X
%D 2007
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2007.A0127

TY - JOUR
T1 - Online algorithms for scheduling with machine activation cost on two uniform machines
A1 - HAN Shu-guang
A1 - JIANG Yi-wei
A1 - HU Jue-liang
J0 - Journal of Zhejiang University Science A
VL - 8
IS - 1
SP - 127
EP - 133
%@ 1673-565X
Y1 - 2007
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2007.A0127


Abstract: 
In this paper we investigate a variant of the scheduling problem on two uniform machines with speeds 1 and s. For this problem, we are given two potential uniform machines to process a sequence of independent jobs. Machines need to be activated before starting to process, and each machine activated incurs a fixed machine activation cost. No machines are initially activated, and when a job is revealed, the algorithm has the option to activate new machines. The objective is to minimize the sum of the makespan and the machine activation cost. We design optimal online algorithms with competitive ratio of (2s+1)/(s+1) for every s≥1.

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

Reference

[1] Aspnes, J., Azar, Y., Fiat, A., Plotkin, S., Waarts, O., 1997. On-line load balancing with applications to machine scheduling and virtual circuit routing. Journal of the ACM, 44(3):486-504.

[2] Berman, P., Charikar, M., Karpinski, M., 1997. On-line Load Balancing for Related Machines. Proceedings of the 5th Workshop on Algorithms and Data Structures. Springer-Verlag, Berlin, 1272:116-125.

[3] Cao, D., Chen, M., Wan, G., 2005. Parallel machine selection and job scheduling to minimize machine cost and job tardiness. Computer & Operations Research, 32(8):1995-2012.

[4] Cho, Y., Sahni, S., 1980. Bounds for list schedules on uniform processors. SIAM Journal on Computing, 9(1):91-103.

[5] Dessouky, M.M., Dessouky, M.I., Verma, S., 1998. Flowshop scheduling with identical jobs and uniform parallel machines. European Journal of Operational Research, 109(3):620-631.

[6] Dósa, G., He, Y., 2004. Better online algorithms for scheduling with machine cost. SIAM Journal on Computing, 33(5):1035-1051.

[7] Epstein, L., Noga, J., Seiden, S., Sgall, J., Woeginger, G.J., 2001. Randomized on-line scheduling on two uniform machines. Journal of Scheduling, 4(2):71-92.

[8] Epstein, L., Sgall, J., 2000. A lower bound for on-line scheduling on uniformly related machines. Operations Research Letters, 26(1):17-22.

[9] He, Y., Han, S.G., Jiang, Y.W., 2006. Online algorithms for scheduling with machine activation cost. Asia-Pacific Journal of Operations research, in press.

[10] Imreh, C., Noga, J., 1999. Scheduling with Machine Cost. Proc. RANDOM APPROX’99. Lecture Notes in Computer Science, 1671:168-176.

[11] Jiang, Y.W., He, Y., 2005. Preemptive online algorithms for scheduling with machine cost. Acta Informatica, 41(6):315-340.

[12] Jiang, Y.W., He, Y., 2006. Semi-online algorithms for scheduling with machine cost. Journal of Computer Science & Technology, 21(6):984-988.

[13] Noga, J., Seiden, S.S., 2001. An optimal online algorithm for scheduling two machines with release times. Theoretical Computer Science, 268(1):133-143.

[14] Panwalkar, S., Liman, S.D., 2002. Single operation earliness-tardiness scheduling with machine activation cost. IIE Transactions, 34(5):509-513.

[15] Sgall, J., 1998. On-line Scheduling. In: Fiat, A., Woeginger, G.J. (Eds.), Online Algorithms: The State of the Art. Springer-Verlag, Berlin, 1442:196-231.

[16] Tan, Z., He, Y., 2002. Optimal online algorithm for scheduling on two identical machines with machine availability constraints. Information Processing Letters, 83(6):323-329.

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