运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2009年
3期
58-66
,共9页
陶冶%陶继平%巢志骏%席裕庚
陶冶%陶繼平%巢誌駿%席裕庚
도야%도계평%소지준%석유경
运筹学%折扣加权总完工时间%排序%半在线%竞争比
運籌學%摺釦加權總完工時間%排序%半在線%競爭比
운주학%절구가권총완공시간%배서%반재선%경쟁비
讨论到达时间任意,加工时间具有上下限约束,目标函数为带折扣的加权总完工时间的单机排序问题1|rj,Pmin≤Pj≤Pmax|∑ωj(1-e-βCj),给出了此问题在任意半在线算法下的竞争比下界,并提出了求解此问题的一种半在线算法D-αWDSPT,通过分析算法竞争比说明该算法是一种近似最优算法.同时指出,算法在问题的三种特殊情况下是最优算法.第一种问题是最小加工时间P→0,第二种问题是折扣因子β→0,第三种问题是工件加工时间相同Pmin=Pmax
討論到達時間任意,加工時間具有上下限約束,目標函數為帶摺釦的加權總完工時間的單機排序問題1|rj,Pmin≤Pj≤Pmax|∑ωj(1-e-βCj),給齣瞭此問題在任意半在線算法下的競爭比下界,併提齣瞭求解此問題的一種半在線算法D-αWDSPT,通過分析算法競爭比說明該算法是一種近似最優算法.同時指齣,算法在問題的三種特殊情況下是最優算法.第一種問題是最小加工時間P→0,第二種問題是摺釦因子β→0,第三種問題是工件加工時間相同Pmin=Pmax
토론도체시간임의,가공시간구유상하한약속,목표함수위대절구적가권총완공시간적단궤배서문제1|rj,Pmin≤Pj≤Pmax|∑ωj(1-e-βCj),급출료차문제재임의반재선산법하적경쟁비하계,병제출료구해차문제적일충반재선산법D-αWDSPT,통과분석산법경쟁비설명해산법시일충근사최우산법.동시지출,산법재문제적삼충특수정황하시최우산법.제일충문제시최소가공시간P→0,제이충문제시절구인자β→0,제삼충문제시공건가공시간상동Pmin=Pmax
