运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2013年
4期
96-102
,共7页
在线排序%平行分批%最大流程时间%竞争比
在線排序%平行分批%最大流程時間%競爭比
재선배서%평행분비%최대류정시간%경쟁비
on-line scheduling%parallel batching%maximum flow-time%competitive ratio
研究单处理机工件按加工长度不增顺序到达的在线分批排序问题.工件按时在线到达,目标是最小化最大流程.流程时间是指工件的完工时间与到达时间的差值,它体现了工件在系统内的逗留时间.对于批容量有界的情形,给出了一个竞争比为1+√5/2的最好可能的在线算法;对于批容量无界的情形,给出了一个竞争比为√2的最好可能的在线算法.
研究單處理機工件按加工長度不增順序到達的在線分批排序問題.工件按時在線到達,目標是最小化最大流程.流程時間是指工件的完工時間與到達時間的差值,它體現瞭工件在繫統內的逗留時間.對于批容量有界的情形,給齣瞭一箇競爭比為1+√5/2的最好可能的在線算法;對于批容量無界的情形,給齣瞭一箇競爭比為√2的最好可能的在線算法.
연구단처리궤공건안가공장도불증순서도체적재선분비배서문제.공건안시재선도체,목표시최소화최대류정.류정시간시지공건적완공시간여도체시간적차치,타체현료공건재계통내적두류시간.대우비용량유계적정형,급출료일개경쟁비위1+√5/2적최호가능적재선산법;대우비용량무계적정형,급출료일개경쟁비위√2적최호가능적재선산법.
