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

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, 2016, 20(2): 49-58.

share this article

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 15

[1]	MENG Lanmeng, MA Ran, ZHANG Yuzhong. Single-machine online scheduling with NDP constraint and deterioration [J]. Operations Research Transactions, 2026, 30(1): 179-187.
[2]	Qian XIA, Xingong ZHANG. Online scheduling problem of two flow shop with lookahead interval and incompatible job family [J]. Operations Research Transactions, 2025, 29(4): 103-111.
[3]	Kaiyuan JIN, Feifeng ZHENG, Ming LIU. Online scheduling model of batch processing machine considering order types and setup time [J]. Operations Research Transactions, 2025, 29(4): 231-240.
[4]	Wenjie LI, Zhihui DU, Menglong SU. Research on the NDP-constraint online scheduling of jobs have agreeable processing times and delivery times [J]. Operations Research Transactions, 2024, 28(4): 18-28.
[5]	Chengwen JIAO. Online scheduling on a single parallel-batch machine with linear lookahead [J]. Operations Research Transactions, 2024, 28(4): 111-116.
[6]	Juannian XU, Ran MA, Wenwen HAN, Yuzhong ZHANG. Single-machine online scheduling to minimize maximum weighted completion time with limited weights [J]. Operations Research Transactions, 2024, 28(2): 71-80.
[7]	Yubo DAI, Yihong DUAN, Longcheng LIU, Zihao WANG. Randomized approximation algorithms for a class of one-dimensional online unit clustering problem [J]. Operations Research Transactions, 2022, 26(3): 143-150.
[8]	Wenjie LI, Yujing LI, Hailing LIU. Research on the single-machine online schedule in which the jobs' release times and processing times are agreeable [J]. Operations Research Transactions, 2022, 26(2): 55-63.
[9]	Libo WANG, Wenhua LI, Dan YU. Online scheduling on single batch machine with variable lookahead interval [J]. Operations Research Transactions, 2022, 26(1): 134-140.
[10]	JIANG Xiaoyan, SHUAI Tianping. Online MapReduce scheduling on two uniform machines [J]. Operations Research Transactions, 2020, 24(3): 57-66.
[11]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[12]	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.
[13]	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.
[14]	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.
[15]	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.

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