期刊文章详细信息
一特殊情形的三台可拒绝同型机在线排序问题
A Special Case of Nonpreemptive On-line Scheduling on Three Identical Machines with Rejection
文献类型：期刊文章
机构地区：[1]嘉兴学院数学与信息科学学院,浙江嘉兴314001
年 份：2006
卷 号：18
期 号：3
起止页码：44-47
语 种：中文
收录情况：NSSD、普通刊
摘 要：给定三台同型平行机,工件逐个到达,每个工件带有两个参数(tj,Pj),可以被接受加工,消耗一定的加工时间tj,也可以被拒绝,但要付出一定的罚值Pj,目标是要使被加工工件的最大完工时间makespan和拒绝工件的罚值之和最小．文中进一步假定每个工件的罚值和加工长度成固定的比例α∈[0,＋∞),针对工件加工不可中断情形,设计出近似算法PRL,证明其关于α的参数竞争比,进一步给出该问题的下界,它们均为α的分段函数．该算法在α∈[0,1/2)∪[1,＋∞)已达到最优．
关 键 词：同型机 在线排序 可拒绝 近似算法 竞争比
分 类 号：O223]
参考文献：
正在载入数据...
二级参考文献：
正在载入数据...
耦合文献：
正在载入数据...
引证文献：
正在载入数据...
二级引证文献：
正在载入数据...
同被引文献：
正在载入数据...
