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

运筹学学报 ›› 2013, Vol. 17 ›› Issue (4): 63-68.

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

姚然¹, 陈光亭^1,2, 张安^1,*, 陈永¹

1. 杭州电子科技大学理学院数学系，杭州 310018； 2. 台州学院，浙江台州 317000；

出版日期:2013-12-15 发布日期:2013-12-15
通讯作者: 张安 E-mail:anzhang@hdu.edu.cn
基金资助:
国家自然科学基金 (No. 11201105), 数学天元基金 (No. 11226235)

Preemptive online algorithms for scheduling on three machines with hierarchies

YAO Ran¹, CHEN Guangting^1,2, ZHANG An^1,*, CHEN Yong¹

1. Department of Mathematics, College of Sciences, Hangzhou Dianzi University, Hangzhou 310018, China; 2. Taizhou University, Taizhou 317000, Zhejiang, China

Online:2013-12-15 Published:2013-12-15

摘要/Abstract

摘要： 研究具有等级约束的三台机在线排序问题. 机器和工件的等级数均为1或2，工件只能在等级数不超过自身等级的机器上加工，且加工允许中断，目标是极小化最大工件完工时间. 如果有两台机器等级为1，给出竞争比为3/2的在线算法，并证明算法是最好可能的；如果只有一台等级为1的机器，也给出竞争比为3/2的在线算法.

关键词: 在线排序, 可中断, 等级, 竞争比

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

中图分类号:

O224

姚然, 陈光亭, 张安, 陈永. 具有等级约束的三台机排序问题的可中断在线算法[J]. 运筹学学报, 2013, 17(4): 63-68.

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.

参考文献

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]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[2]	李文华, 翟威娜, 柴幸, 高超. 具有两个不相容工件族单位工件的有界分批在线排序问题[J]. 运筹学学报, 2019, 23(4): 105-110.
[3]	彭南南, 张玉忠, 柏庆国, 王成飞. 工件满足一致性的同类机在线分批排序问题[J]. 运筹学学报, 2019, 23(1): 111-118.
[4]	李英, 乔龙亮, 郑斐峰. 具有预知信息的集装箱码头泊位与岸桥联合调度在线模型[J]. 运筹学学报, 2018, 22(3): 28-36.
[5]	闵啸，朱俊蕾，刘静. 两台带服务等级的可拒绝同型机排序问题的在线算法[J]. 运筹学学报, 2018, 22(3): 117-124.
[6]	侯丽英. 具有服务等级的两台同型机实时在线排序[J]. 运筹学学报, 2016, 20(2): 49-58.
[7]	王成飞, 张玉忠. 提前预知信息的在线分批排序问题[J]. 运筹学学报, 2016, 20(1): 84-90.
[8]	李文华, 柴幸, 袁航, 杨素芳. 平行机上带有前瞻区间的不相容工件组在线排序问题[J]. 运筹学学报, 2015, 19(4): 121-126.
[9]	高强, 鲁习文. 带有拒绝的单机和同型机排序问题[J]. 运筹学学报, 2014, 18(4): 1-10.
[10]	焦成文, 李文华. 工件按加工长度不增序到达的最小化最大流程在线分批排序[J]. 运筹学学报, 2013, 17(4): 96-102.
[11]	杨素芳, 李文华. 具有前瞻区间的两个工件组单机在线排序问题[J]. 运筹学学报, 2012, 16(2): 115-120.
[12]	杨名, 鲁习文. 有使用限制的二台机器流水作业问题[J]. 运筹学学报, 2011, 15(3): 62-69.
[13]	王成飞, 张玉忠, 柏庆国. 具有线性恶化效应的在线分批排序问题[J]. 运筹学学报, 2011, 15(3): 107-114.