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

• 作者: 荣建华
• 来源期刊: 浙江大学学报（理学版）
• 学科: 数学
• 关键词: 在线排序 平行机 拒绝费用 竞争比 服务等级
• 年，卷（期）: 2016,（6）
• 所属期刊栏目: 数学与计算机科学
• 页码范围: 685-688
• 页数: 4页
• 分类号: O223
• 字数: 3290字
• 语种: 中文
• DOI: 10.3785/j.issn.1008-9497.2016.06.012

摘要

研究了将服务等级与拒绝费用2种模型复合起来的平行机排序问题.设有2台平行机M1,M2,加工速度相同;n个工件J1,J2,?,Jn分别按列表在线到达,每个工件Jj含有3个参数:加工长度tj、拒绝费用p j以及服务等级gj=1,2.当工件到达时,可以接收加工,占用一定的加工时间;亦可拒绝,付出相应的罚值.目标为被接收工件的最大完工时间与被拒绝工件的总罚值之和最小.进一步,当且仅当g(Mi)≤gj时,工件Jj可以分配给机器M i加工,即机器M1可以加工所有工件,机器M2只能加工等级为gj=2的工件,允许中断加工.设计了在线算法P H,并证明其竞争比为1+?√2/2≈1.707,下界为1.618,上下界差约为0.089.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	荣建华	石家庄铁道大学四方学院基础部	12	1	1.0	1.0