一特殊情形的三台可拒绝同型机在线排序问题

作     者：闵啸 MIN Xiao

作者机构：嘉兴学院数学与信息科学学院浙江嘉兴314001 

出 版 物：《嘉兴学院学报》 (Journal of Jiaxing University)

年 卷 期：2006年第18卷第3期

页      码：44-47页

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

主 题 词：同型机 在线排序 可拒绝 近似算法 竞争比 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 07[理学] 070105[070105] 0701[理学-数学类] 

D　O　I：10.3969/j.issn.1008-6781.2006.03.012

馆 藏 号：203125479...