应用数学学报
應用數學學報
응용수학학보
ACTA MATHEMATICAE APPLICATAE SINICA
2011年
1期
73-80
,共8页
两个客户%竞争排序%多个维护%近似算法
兩箇客戶%競爭排序%多箇維護%近似算法
량개객호%경쟁배서%다개유호%근사산법
研究了单机两个客户竞争排序问题1||∑wAjcAj:fBmax≤Q,证明了该问题与问题1|MAi|∑wjcj及问题1|hi,pmtn|∑wjcj之间是相互等价的.对wj=pj时的特殊情形,指出了问题1||∑wAjcAj:fBmax≤Q存在近似比为2的最长处理时间优先算法(LPT)且该界是紧的,对wj任意的一般情形,指出了问题1||∑wAjcAj:fBmax≤Q存在近似比为4+ε的近似算法.当客户B的工件数是常数时,对问题1||∑wAjcAj:fBmax≤Q则给出了伪多项式时间的动态规划算法.此外,指出了问题1||∑wAjcAj:∑wBjcBj ≤ Q具有多项式时间近似方案(PTAS).
研究瞭單機兩箇客戶競爭排序問題1||∑wAjcAj:fBmax≤Q,證明瞭該問題與問題1|MAi|∑wjcj及問題1|hi,pmtn|∑wjcj之間是相互等價的.對wj=pj時的特殊情形,指齣瞭問題1||∑wAjcAj:fBmax≤Q存在近似比為2的最長處理時間優先算法(LPT)且該界是緊的,對wj任意的一般情形,指齣瞭問題1||∑wAjcAj:fBmax≤Q存在近似比為4+ε的近似算法.噹客戶B的工件數是常數時,對問題1||∑wAjcAj:fBmax≤Q則給齣瞭偽多項式時間的動態規劃算法.此外,指齣瞭問題1||∑wAjcAj:∑wBjcBj ≤ Q具有多項式時間近似方案(PTAS).
연구료단궤량개객호경쟁배서문제1||∑wAjcAj:fBmax≤Q,증명료해문제여문제1|MAi|∑wjcj급문제1|hi,pmtn|∑wjcj지간시상호등개적.대wj=pj시적특수정형,지출료문제1||∑wAjcAj:fBmax≤Q존재근사비위2적최장처리시간우선산법(LPT)차해계시긴적,대wj임의적일반정형,지출료문제1||∑wAjcAj:fBmax≤Q존재근사비위4+ε적근사산법.당객호B적공건수시상수시,대문제1||∑wAjcAj:fBmax≤Q칙급출료위다항식시간적동태규화산법.차외,지출료문제1||∑wAjcAj:∑wBjcBj ≤ Q구유다항식시간근사방안(PTAS).
