【摘要】 讨论到达时间任意,加工时间具有上下限约束,目标函数为带折扣的加权总完工时间的单机排序问题1|r_j,p_min≤p_j≤p_max|∑w_j(1-e^-βC_j),给出了此问题在任意半在线算法下的竞争比下界,并提出了求解此问题的一种半在线算法D-αWDSPT,通过分析算法竞争比说明该算法是一种近似最优算法.同时指出,算法在问题的三种特殊情况下是最优算法.第一种问题是最小加工时间p→0,第二种问题是折扣因子β→0,第三种问题是工件加工时间相同p_min=p_max更多还原

【Abstract】 In this paper,we investigate a single machine scheduling problem with arbitrary release times,bounded processing times to minimize total weighted completion time with discounted factor 1|r_j,p_min≤p≤p_max|∑ω_j(1-e^βG_j).A lower bound of the competitive ratio of any semi-online algorithm is presented.And a near-optimal semi-online algorithm D-αWDSPT with the competitive ratio is given as well.D-αWDSPT is proven to be optimal under three special circumstances that is p→0,β→0 and p_min=p_max.更多还原