两台带服务等级的可拒绝同型机可中断在线排序问题的最优算法研究

摘要：

研究两台带服务等级的可拒绝同型机可中断在线排序问题.设有两台同型机M1、M2,速度一致,但具有不同的加工能力,用其服务等级表示,M1的服务等级为1,M2的服务等级为2.工件j 按列表在线到达,每个工件带有三个参数：长度tj 、等级gj =1或2、罚值pj .当j到达时,其可以被拒绝,但要付出相应的罚值pj ,也可以被接受并分配给机器加工,但规定其只能安排给服务等级小于工件等级的机器加工,即等级为1的工件只能分给M1加工,等级为2的工件可以分给任一台机器加工,加工允许中断,目标为极小化加工工件集的最晚完工时间和拒绝工件集的总罚值之和.本文对于该问题给出了一个最优在线算法,其竞争比为1.618.

关键词：在线排序、同型机、服务等级、可中断、可拒绝、竞争比

所属期刊栏目：28

分类号：D648.3(思想政治教育和精神文明建设)

资助基金：浙江省高等学校访问学者专业发展项目FX2014074;嘉兴学院科研重点项目70112023BL;浙江省网络媒体云处理与分析工程技术中心开放课题资助项目2012E10023-4

在线出版日期：2016-12-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：69-73