Semi on-line preemptive scheduling on two uniform machines with rejection(两台可中断同类机可拒绝半在线排序问题的近似算法)

MINXiao(闵啸); LIUJing(刘静); WANGYu-qing(王玉青)

doi:10.3785/j.issn.1008-9497.2010.05.009

Zhejiang Daxue xuebao. Lixue ban (Sep 2010)

Semi on-line preemptive scheduling on two uniform machines with rejection(两台可中断同类机可拒绝半在线排序问题的近似算法)

MINXiao(闵啸),
LIUJing(刘静),
WANGYu-qing(王玉青)

Affiliations

MINXiao(闵啸): Department of Mathematics and Information Engineering, Jiaxing College, Jiaxing 314001, Zhejiang Province, China(嘉兴学院数学与信息工程学院，浙江　嘉兴　314001)
LIUJing(刘静): Department of Mathematics and Information Engineering, Jiaxing College, Jiaxing 314001, Zhejiang Province, China(嘉兴学院数学与信息工程学院，浙江　嘉兴　314001)
WANGYu-qing(王玉青): Department of Mathematics and Information Engineering, Jiaxing College, Jiaxing 314001, Zhejiang Province, China(嘉兴学院数学与信息工程学院，浙江　嘉兴　314001)

DOI: https://doi.org/10.3785/j.issn.1008-9497.2010.05.009
Journal volume & issue: Vol. 37, no. 5
pp. 519 – 523

Abstract

Read online

研究一个两台同类机可拒绝半在线排序问题,机器速度一个为1,另一个为s∈[1, +∞),加工允许中断.当工件到达时,可以将其接受加工,占用一定的机器负荷,也可以将其拒绝,付出相应的罚值,目标为使被接受工件集产生的makespan和被拒绝工件集的总罚值之和最小.问题进一步假定每个工件在选择是否加工时有两个拒绝尺度,各自独立决策,最后选择较好的结果作为最终输出.笔者设计了算法H,得到其关于s的参数竞争比为,优于只有一个拒绝尺度的经典情形.最后又给出问题的一个下界,上下界的最大差距在s=1时达到0.167.

Published in Zhejiang Daxue xuebao. Lixue ban

ISSN: 1008-9497 (Print)
Publisher: Zhejiang University Press
Country of publisher: China
LCC subjects: Science: Mathematics: Instruments and machines: Electronic computers. Computer science; Science: Physics
Website: https://www.zjujournals.com/sci/EN/1008-9497/home.shtml

About the journal

Abstract

Keywords