折扣加权总完工时间问题的半在线排序算法  

A Semi-Online Algorithm for Solving the Single Machine Scheduling Problem to Minimize Total Weighted Completion Time with Discounted Factor

作　　者：陶冶[1] 陶继平[1] 巢志骏[1] 席裕庚[1] 

机构地区：[1]上海交通大学电子信息与电气工程学院,上海200240

出　　处：《运筹学学报》2009年第3期58-66,共9页Operations Research Transactions

基　　金：国家自然科学基金(No.60504026);高校博士项目专向基金(No.20070248004)资助

摘　　要：讨论到达时间任意,加工时间具有上下限约束,目标函数为带折扣的加权总完工时间的单机排序问题1|r_j,p_(min)≤p_j≤p_(max)|∑w_j(1-e^(-βC_j)),给出了此问题在任意半在线算法下的竞争比下界,并提出了求解此问题的一种半在线算法D-αWDSPT,通过分析算法竞争比说明该算法是一种近似最优算法.同时指出,算法在问题的三种特殊情况下是最优算法.第一种问题是最小加工时间p→0,第二种问题是折扣因子β→0,第三种问题是工件加工时间相同p_(min)=p_(max)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｜rj,Pmin≤Pj≤Pmax｜∑ω（1-e^βCj）. 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 Pmin=Pmax.

关 键 词：运筹学 折扣加权总完工时间 排序 半在线 竞争比 

分 类 号：O223[理学—运筹学与控制论] TP301.6[理学—数学]