论文部分内容阅读
讨论到达时间任意，加工时间具有上下限约束，目标函数为带折扣的加权总完工时间的单机排序问题1｜rj，Pmin≤Pj≤Pmax｜∑ω（1-e^βCj），给出了此问题在任意半在线算法下的竞争比下界，并提出了求解此问题的一种半在线算法D-αWDSPT，通过贫析算法竞争比说明该算法是一种近似最优算法。同时指出，算法在问题的三种特殊情况下是最优算法。第一种问题是最小加工时间p→0，第二种问题是折扣因子β→0，第三种问题是工件加工时间相同Pmin=Pmax。