具有服务等级的两台同型机实时在线排序

doi:10.15960/j.cnki.issn.1007-6093.2016.02.004

Abstract

Abstract:

This paper considers online scheduling problem on two identical machines under a grade of service, where jobs arrive online over time. The objective is to minimize the maximum completion time. We propose an online algorithm with competitive ratio \frac{7}{4}.

Key words: online scheduling, grade of service, release time, competitive ratio

Cite this article

HOU Liying. Online hierarchical service scheduling on two identical machines with release times[J]. Operations Research Transactions, doi: 10.15960/j.cnki.issn.1007-6093.2016.02.004.

share this article

0
/ / Recommend

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.ort.shu.edu.cn/EN/10.15960/j.cnki.issn.1007-6093.2016.02.004

https://www.ort.shu.edu.cn/EN/Y2016/V20/I2/49

References

[1] Graham R L, Lawler E L, Lenstra J K, et al. Optimization and approximation in deterministic sequencing and scheduling: A survey [J]. Annals of Discrete Mathematics, 1979, 5: 287-326.

[2] Chen B, Vestjens A P A. Scheduling on identical machines: How good is LPT in an on-line setting [J]. Operations Research Letters, 1997, 21: 165-169.

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

[4] Bar-Noy A, Freund A, Naor J. On-line load balancing in a hierarchical server topology [J]. SIAM Journal on Computing, 2001, 31: 527-549.

[5] Chassid O, Epstein L. The hierarchical model for load balancing on two machines [J]. Journal of Combinatorial Optimization, 2008, 15: 305-314.

[6] Hwang H C, Chang S Y, Lee K. Parallel machine scheduling under a grade of service provision [J]. Computers \& Operations Research, 2004, 31: 2055-2061.

[7] Park J, Chang S Y, Lee K. Online and semi-online scheduling of two machines under a grade of service provision [J]. Operations Research Letters, 2006, 34: 692-696.

[8] Tan Z Y, Zhang A. A note on hierarchical scheduling on two uniform machines [J]. Journal of Combinatorial Optimization, 2010, 20: 85-95.

[9] Zhang A, Jiang Y W, Tan Z Y. Online parallel machines scheduling with two hierarchies [J]. Theoretical Computer Science, 2009, 410: 3597-3605.

[10] Lee K, Leung J Y T, Pinedo M L. Scheduling jobs with equal processing times subject to machine eligibility constraints [J].Journal of Scheduling, 2010, 14(1): 27-38.

[11] Lee K, Leung J Y T, Pinedo M L. Makespan minimization in online scheduling with machine eligibility [J]. Annals of Operations Research, 2013, 204(1): 189-222.

Related Articles 12

[1]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[2]	LI Wenhua, ZHAI Weina, CHAI Xing, GAO Chao. On-line bounded-batching scheduling of unit-length jobs with two families [J]. Operations Research Transactions, 2019, 23(4): 105-110.
[3]	PENG Nannan, ZHANG Yuzhong, BAI Qingguo, WANG Chengfei. Online batch scheduling problem on uniform machines with agreeable processing times [J]. Operations Research Transactions, 2019, 23(1): 111-118.
[4]	LI Ying, QIAO Longliang, ZHENG Feifeng. A study of online berth and quay crane integrated allocation problem with lookahead ability [J]. Operations Research Transactions, 2018, 22(3): 28-36.
[5]	MIN Xiao, ZHU Junlei, LIU Jing. An online algorithm for hierarchical scheduling on two identical machines with rejection [J]. Operations Research Transactions, 2018, 22(3): 117-124.
[6]	WANG Chengfei, ZHANG Yuzhong. Online batch scheduling with known information in advance [J]. Operations Research Transactions, 2016, 20(1): 84-90.
[7]	LI Wenhua, CHAI Xing, YUAN Hang, YANG Sufang. On-line algorithms for incompatible job families on parallel machines scheduling with lookahead [J]. Operations Research Transactions, 2015, 19(4): 121-126.
[8]	GAO Qiang, LU Xiwen. Scheduling on single machine and identical machines with rejection [J]. Operations Research Transactions, 2014, 18(4): 1-10.
[9]	YAO Ran, CHEN Guangting, ZHANG An, CHEN Yong. Preemptive online algorithms for scheduling on three machines with hierarchies [J]. Operations Research Transactions, 2013, 17(4): 63-68.
[10]	JIAO Chengwen, LI Wenhua. Online parallel batching scheduling for nonincreasing-processing-time jobs to minimize the maximum flow-time [J]. Operations Research Transactions, 2013, 17(4): 96-102.
[11]	YANG Su-Fang, LI Wen-Hua. On-line scheduling on a machine of two families with lookahead [J]. Operations Research Transactions, 2012, 16(2): 115-120.
[12]	YANG Ming, LU Xi-Wen. Two-Machine Flow Shop Problems with Availability Constraints [J]. Operations Research Transactions, 2011, 15(3): 62-69.

Metrics

Viewed

Full text

Abstract

Comments

Abstract
References
Related Articles
Recommended Articles
Metrics
Comments

TOP

Online hierarchical service scheduling on two identical machines with release times

PDF

Knowledge