具有等级约束的三台机排序问题的可中断在线算法

Abstract

Abstract: We consider online scheduling on three machines with hierarchies. Each job, as well as each machine, has a hierarchy of either 1 or 2 associated with it. A job can be scheduled on a machine only when its hierarchy is no smaller than that of the machine. Preemption is allowed. The objective is to minimize the maximum completion time of jobs. If there are two machines of hierarchy 1, then we give an online algorithm with competitive ratio 3/2 and prove that it is best possible. If only one machine has a hierarchy of 1, then a 3/2-competitive algorithm is also provided.

Key words: online scheduling, preemptive, hierarchy, competitive ratio

CLC Number:

O224

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.

References

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

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

Tan Z Y, Zhang A. Online hierarchical scheduling: an approach using mathematical programming [J]. Theoretical Computer Science, 2011, 412: 246-256.

Jiang Y W, He Y, Tang C M. Optimal online algorithms for scheduling on two identical machines under a grade of service [J]. Journal of Zhejiang University Science A, 2006, 7: 309-314.

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

Jiang Y W. Online scheduling on parallel machines with two GoS levels [J]. Journal of Combinatorial Optimization, 2008, 16: 28-38.

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

Hou L Y, Kang L Y. Online scheduling on uniform machines with two hierarchies [J]. Journal of Combinatorial Optimization, 2012, 24: 593-612.

Hou L Y, Kang L Y. Online and semi-online hierarchical scheduling for load balancing on uniform machines [J]. Theoretical Computer Science, 2011, 412: 1092-1098.

Dosa G, Epstein L. Preemptive scheduling on a small number of hierarchical machines [J]. Information and Computation, 2008, 206: 602-619.

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

Chen B, Viet A, Woeginger G J. An optimal algorithm for preemptive on-line scheduling [J]. Operations Research Letters, 1995, 18: 127-131.

Lee K, Leung J Y-T, Pinedo M. Makespan minimization in online scheduling with machine eligibility [J]. 4OR-A Quarterly Journal of Operations Research, 2010, 8: 331-364.

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

[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]	ZHANG Hongbo, ZHOU Gaojun, FENG Pinghua. Analysis for a preemptive priority queue with finite capacity [J]. Operations Research Transactions, 2016, 20(3): 11-20.
[7]	HOU Liying. Online hierarchical service scheduling on two identical machines with release times [J]. Operations Research Transactions, 2016, 20(2): 49-58.
[8]	WANG Chengfei, ZHANG Yuzhong. Online batch scheduling with known information in advance [J]. Operations Research Transactions, 2016, 20(1): 84-90.
[9]	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.
[10]	GAO Qiang, LU Xiwen. Scheduling on single machine and identical machines with rejection [J]. Operations Research Transactions, 2014, 18(4): 1-10.
[11]	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.
[12]	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.
[13]	YANG Ming, LU Xi-Wen. Two-Machine Flow Shop Problems with Availability Constraints [J]. Operations Research Transactions, 2011, 15(3): 62-69.

Preemptive online algorithms for scheduling on three machines with hierarchies

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 13

Recommended Articles

Metrics

Comments