曲阜师范大学学报(自然科学版)
麯阜師範大學學報(自然科學版)
곡부사범대학학보(자연과학판)
JOURNAL OF QUFU NORMAL UNIVERSITY(NATURAL SCIENCE)
2003年
3期
1-5
,共5页
丁际环%曲桂东%张伟%岳丽%张玉忠
丁際環%麯桂東%張偉%嶽麗%張玉忠
정제배%곡계동%장위%악려%장옥충
在线排序%近似算法%最坏情况
在線排序%近似算法%最壞情況
재선배서%근사산법%최배정황
研究带机器准备时间的m台同类机(uniform machines)在线和半在线排序问题,目标函数为极小化最大机器(工件)完工时间. 对于在线情形,证明了LS算法的最坏情况为ρ=(1+5)/2, m=2,1+2m-2/2, m≥3, 并且当m=2时,LS算法是最好的近似算法;当m=2,3,...,6时界是紧的,特别地,当s1=s2=...=sm-1,sm≥1时,证明了LS算法的最坏情况界为ρ=(1+5)/2, m=2,3-4/(m+1), m≥3, 而且界是紧的;对于已知加工时间递减的半在线排序问题,证明了LS算法的最坏情况界为2-2/(m+1).
研究帶機器準備時間的m檯同類機(uniform machines)在線和半在線排序問題,目標函數為極小化最大機器(工件)完工時間. 對于在線情形,證明瞭LS算法的最壞情況為ρ=(1+5)/2, m=2,1+2m-2/2, m≥3, 併且噹m=2時,LS算法是最好的近似算法;噹m=2,3,...,6時界是緊的,特彆地,噹s1=s2=...=sm-1,sm≥1時,證明瞭LS算法的最壞情況界為ρ=(1+5)/2, m=2,3-4/(m+1), m≥3, 而且界是緊的;對于已知加工時間遞減的半在線排序問題,證明瞭LS算法的最壞情況界為2-2/(m+1).
연구대궤기준비시간적m태동류궤(uniform machines)재선화반재선배서문제,목표함수위겁소화최대궤기(공건)완공시간. 대우재선정형,증명료LS산법적최배정황위ρ=(1+5)/2, m=2,1+2m-2/2, m≥3, 병차당m=2시,LS산법시최호적근사산법;당m=2,3,...,6시계시긴적,특별지,당s1=s2=...=sm-1,sm≥1시,증명료LS산법적최배정황계위ρ=(1+5)/2, m=2,3-4/(m+1), m≥3, 이차계시긴적;대우이지가공시간체감적반재선배서문제,증명료LS산법적최배정황계위2-2/(m+1).
