论文部分内容阅读
给定三台同型平行机，工件逐个到达，每个工件带有两个参数（tj，Pj），可以被接受加工，消耗一定的加工时间tj，也可以被拒绝，但要付出一定的罚值Pj，目标是要使被加工工件的最大完工时间makespan和拒绝工件的罚值之和最小．文中进一步假定每个工件的罚值和加工长度成固定的比例α∈[0，＋∞），针对工件加工不可中断情形，设计出近似算法PRL，证明其关于α的参数竞争比，进一步给出该问题的下界，它们均为α的分段函数．该算法在α∈[0，1/2）∪[1，＋∪）已达到最优．