拒绝可缓冲的2台同类机半在线排序问题的近似算法

• 作者: 刘静 姜明 朱俊蕾 闵啸
• 来源期刊: 浙江大学学报（理学版）
• 学科: 数学
• 关键词: 同类机 半在线 可拒绝 排序 缓冲区 竞争比
• 年，卷（期）: 2014,（4）
• 所属期刊栏目: 数学与计算机科学
• 页码范围: 399-405
• 页数: 7页
• 分类号: O223
• 字数: 5975字
• 语种: 中文
• DOI: 10.3785/j.issn.1008-9497.2014.04.007

摘要

研究了2个拒绝可缓冲的同类机半在线排序问题.设有2台同类机M1,M2,速度分别为1和s∈[1,+∞),加工不允许中断,工件Jj按照列表在线到达,每个工件带有2个参数:加工长度tj、拒绝罚值pj(模型1中)或拒绝获益pj(模型2中),当工件到达时,可以被接受并分给某台机器加工,也可以被拒绝,需付出一定的罚值(模型1)或取得一定的收益(模型2),目标是在第1个模型中要求极小化机器最大负荷和拒绝工件的总罚值之和;第2个模型中要求极大化机器最小负荷和总收益之和.此外,在接受或拒绝的决策环节上提供一个缓冲区B,其容量为k≥1,任一时刻至多可以存放k个工件,当工件到达时,若缓冲区未饱和,则可暂时存入B;若已饱和,则必须在新工件和缓冲区内工件中选择一个进行接受或拒绝的决策.本模型所研究的是经典可拒绝模型中的一个松弛问题,属半在线可拒绝模型.最后针对以上2个模型,分别给出了s在区间[1,+∞)上的近似算法,并证明了各自关于s的参数竞争比.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	姜明	杭州电子科技大学软件与智能技术研究所	44	555	11.0	22.0
2	闵啸	嘉兴学院数理与信息工程学院	20	105	7.0	9.0
3	刘静	嘉兴学院数理与信息工程学院	27	89	4.0	8.0
4	朱俊蕾	嘉兴学院数理与信息工程学院	11	4	1.0	1.0