系统科学与数学
繫統科學與數學
계통과학여수학
JOURNAL OF SYSTEMS SCIENCE AND MATHEMATICAL SCIENCES
2006年
6期
729-736
,共8页
半在线%同类机%竞争比
半在線%同類機%競爭比
반재선%동류궤%경쟁비
考虑已知工件最大加工时间的两台同类机半在线问题.机器M1,M2的速度分别为s1=1,s2=s(s ≥ 1),工件是一个一个独立地到来,工件的信息是逐个释放的,但所有工件中加工时间为最大的工件的加工时间是已知的,目标函数为极小化最大机器负载.此模型简记为Q2/known largest job/Cmax.作者给出了Qmax2算法并证明此算法的竞争比为2(s+1)/(s+2)(1≤s≤2)和(s+1)/s(s＞2),且是紧的.同时给出Q2/known largest job/Cmax问题的一个下界,并且证明Qmax2算法的竞争比与最优算法竞争比之差不大于1/4.
攷慮已知工件最大加工時間的兩檯同類機半在線問題.機器M1,M2的速度分彆為s1=1,s2=s(s ≥ 1),工件是一箇一箇獨立地到來,工件的信息是逐箇釋放的,但所有工件中加工時間為最大的工件的加工時間是已知的,目標函數為極小化最大機器負載.此模型簡記為Q2/known largest job/Cmax.作者給齣瞭Qmax2算法併證明此算法的競爭比為2(s+1)/(s+2)(1≤s≤2)和(s+1)/s(s＞2),且是緊的.同時給齣Q2/known largest job/Cmax問題的一箇下界,併且證明Qmax2算法的競爭比與最優算法競爭比之差不大于1/4.
고필이지공건최대가공시간적량태동류궤반재선문제.궤기M1,M2적속도분별위s1=1,s2=s(s ≥ 1),공건시일개일개독입지도래,공건적신식시축개석방적,단소유공건중가공시간위최대적공건적가공시간시이지적,목표함수위겁소화최대궤기부재.차모형간기위Q2/known largest job/Cmax.작자급출료Qmax2산법병증명차산법적경쟁비위2(s+1)/(s+2)(1≤s≤2)화(s+1)/s(s＞2),차시긴적.동시급출Q2/known largest job/Cmax문제적일개하계,병차증명Qmax2산법적경쟁비여최우산법경쟁비지차불대우1/4.
