两台具有服务等级的可拒绝平行机排序问题

• 作者: 孟昕娜 张国强 荣建华 贡丽霞
• 来源期刊: 曲阜师范大学学报（自然科学版）
• 学科: 数学
• 关键词: 在线算法 拒绝费用 竞争比 服务等级 排序
• 年，卷（期）: 2017,（2）
• 所属期刊栏目: 数学与计算机科学
• 页码范围: 37-40
• 页数: 4页
• 分类号: O223
• 字数: 2369字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-5337.2017.2.037

摘要

研究了工件具有服务等级且可拒绝的平行机排序问题.设有两台平行机,加工速度相同;n个工件分别按列表在线到达,每个工件含有三个参数:加工长度,拒绝费用以及服务等级gj=1,2.当且仅当g (M)≤gj时,工件Jj可由机器Mi加工,且加工不允许中断.进一步,当工件到达时,可以选择被加工,花费一定的加工时间;也可以被拒绝,此时要付出相应的罚值.目标为使被接收工件的最大完工时间与被拒绝工件的总罚值之和最小.文中设计出在线算法H,并证明算法的竞争比为1+(√2/2)≈1.707,下界为5/3≈1.667,上下界大约相差0.04.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	贡丽霞	石家庄铁道大学四方学院基础部	11	6	2.0	2.0
2	荣建华	石家庄铁道大学四方学院基础部	12	1	1.0	1.0
3	张国强	石家庄铁道大学四方学院基础部	6	3	1.0	1.0
4	孟昕娜	石家庄铁道大学四方学院基础部	6	3	1.0	1.0