运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2011年
3期
107-114
,共8页
分批排序%恶化效应%竞争比%在线算法
分批排序%噁化效應%競爭比%在線算法
분비배서%악화효응%경쟁비%재선산법
研究一类具有线性恶化效应的单机在线分批排序问题,工件Jj的加工时间为Pj=bj +αt,其中bj为基本加工时间,α＞0为恶化率,t是开工时间.工件的到达时间是未知的,工件的基本加工时间只有在工件到达之后才能知道.多个工件可以作为一批被机器同时加工,批的加工时间为该批中工件最大加工时间.对于目标为极小化makespan的批容量无限的单机问题给出一个在线算法βH∞,并证明其竞争比和问题的下界相同,进而算法是最优的.
研究一類具有線性噁化效應的單機在線分批排序問題,工件Jj的加工時間為Pj=bj +αt,其中bj為基本加工時間,α＞0為噁化率,t是開工時間.工件的到達時間是未知的,工件的基本加工時間隻有在工件到達之後纔能知道.多箇工件可以作為一批被機器同時加工,批的加工時間為該批中工件最大加工時間.對于目標為極小化makespan的批容量無限的單機問題給齣一箇在線算法βH∞,併證明其競爭比和問題的下界相同,進而算法是最優的.
연구일류구유선성악화효응적단궤재선분비배서문제,공건Jj적가공시간위Pj=bj +αt,기중bj위기본가공시간,α＞0위악화솔,t시개공시간.공건적도체시간시미지적,공건적기본가공시간지유재공건도체지후재능지도.다개공건가이작위일비피궤기동시가공,비적가공시간위해비중공건최대가공시간.대우목표위겁소화makespan적비용량무한적단궤문제급출일개재선산법βH∞,병증명기경쟁비화문제적하계상동,진이산법시최우적.
