南昌大学学报（理科版）
南昌大學學報（理科版）
남창대학학보（이과판）
JOURNAL OF NANCHANG UNIVERSITY(NATURAL SCIENCE)
2010年
1期
24-32
,共9页
竞争比%半在线%排序
競爭比%半在線%排序
경쟁비%반재선%배서
考虑带机器准备时间的已知工件总加工时间半在线问题.首先考虑P2,ri|sum|Cmin问题,给出Prsum算法并证明此算法的竞争比为3/2,且是最优算法; 然后考虑Q2,ri|sum|Cmax问题,给出Qrsum算法并证明此算法的竞争比为2,同时给出此问题的一个下界(1+3)/2.显然 Qrsum算法的竞争比与最优算法的竞争比之差小于0.048 2.
攷慮帶機器準備時間的已知工件總加工時間半在線問題.首先攷慮P2,ri|sum|Cmin問題,給齣Prsum算法併證明此算法的競爭比為3/2,且是最優算法; 然後攷慮Q2,ri|sum|Cmax問題,給齣Qrsum算法併證明此算法的競爭比為2,同時給齣此問題的一箇下界(1+3)/2.顯然 Qrsum算法的競爭比與最優算法的競爭比之差小于0.048 2.
고필대궤기준비시간적이지공건총가공시간반재선문제.수선고필P2,ri|sum|Cmin문제,급출Prsum산법병증명차산법적경쟁비위3/2,차시최우산법; 연후고필Q2,ri|sum|Cmax문제,급출Qrsum산법병증명차산법적경쟁비위2,동시급출차문제적일개하계(1+3)/2.현연 Qrsum산법적경쟁비여최우산법적경쟁비지차소우0.048 2.
