应用数学
應用數學
응용수학
MATHEMATICA APPLICATA
2008年
3期
518-523
,共6页
排序%在线%半在线%近似算法%竞争比
排序%在線%半在線%近似算法%競爭比
배서%재선%반재선%근사산법%경쟁비
本文研究了目标为极大化机器最早完工时间的带机器准备时间的m台平行机在线和半在线排序问题.对于在线排序问题,本文证明了LS算法的竞争比为m.对于已知所有工件加工时间总和(sum)和最大工件加工时间(max)的两个半在线模型,本文分析了它们的下界,并给出了竞争比均为m-1的最优算法.
本文研究瞭目標為極大化機器最早完工時間的帶機器準備時間的m檯平行機在線和半在線排序問題.對于在線排序問題,本文證明瞭LS算法的競爭比為m.對于已知所有工件加工時間總和(sum)和最大工件加工時間(max)的兩箇半在線模型,本文分析瞭它們的下界,併給齣瞭競爭比均為m-1的最優算法.
본문연구료목표위겁대화궤기최조완공시간적대궤기준비시간적m태평행궤재선화반재선배서문제.대우재선배서문제,본문증명료LS산법적경쟁비위m.대우이지소유공건가공시간총화(sum)화최대공건가공시간(max)적량개반재선모형,본문분석료타문적하계,병급출료경쟁비균위m-1적최우산법.
