工程数学学报
工程數學學報
공정수학학보
CHINESE JOURNAL OF ENGINEERING MATHEMATICS
2010年
1期
53-64
,共12页
排序%半在线%竞争比
排序%半在線%競爭比
배서%반재선%경쟁비
scheuling%semi-online%competitive ratio
本文考虑已知工件最大加工时间的三台同类机半在线问题.三台机器的速度分别为s_1=r,s_2=1,s_3=s＞1,1≤r≤s,工件是一个一个独立地到来,工件的信息是逐个释放的,但所有工件中加工时间为最大的工件的加工时间是已知的,目标函数为极小化最大机器负载.本文证明任何解此问题的算法竞争比的下界为3/2且给出Qmax3算法并证明此算法的竞争比不大于2(r+s+1)/2r+s(1<s≤2)和r+2s+1/r+s(s>2).
本文攷慮已知工件最大加工時間的三檯同類機半在線問題.三檯機器的速度分彆為s_1=r,s_2=1,s_3=s＞1,1≤r≤s,工件是一箇一箇獨立地到來,工件的信息是逐箇釋放的,但所有工件中加工時間為最大的工件的加工時間是已知的,目標函數為極小化最大機器負載.本文證明任何解此問題的算法競爭比的下界為3/2且給齣Qmax3算法併證明此算法的競爭比不大于2(r+s+1)/2r+s(1<s≤2)和r+2s+1/r+s(s>2).
본문고필이지공건최대가공시간적삼태동류궤반재선문제.삼태궤기적속도분별위s_1=r,s_2=1,s_3=s＞1,1≤r≤s,공건시일개일개독입지도래,공건적신식시축개석방적,단소유공건중가공시간위최대적공건적가공시간시이지적,목표함수위겁소화최대궤기부재.본문증명임하해차문제적산법경쟁비적하계위3/2차급출Qmax3산법병증명차산법적경쟁비불대우2(r+s+1)/2r+s(1<s≤2)화r+2s+1/r+s(s>2).
