浙江大学学报（理学版）
浙江大學學報（理學版）
절강대학학보（이학판）
JOURNAL OF ZHEJIANG UNIVERSITY
2010年
5期
519-523
,共5页
同类机%半在线%可拒绝%竞争比
同類機%半在線%可拒絕%競爭比
동류궤%반재선%가거절%경쟁비
研究一个两台同类机可拒绝半在线排序问题,机器速度一个为1,另一个为s∈[1,+∞),加工允许中断.当工件到达时,可以将其接受加工,占用一定的机器负荷,也可以将其拒绝,付出相应的罚值,目标为使被接受工件集产生的makespan和被拒绝工件集的总罚值之和最小.问题进一步假定每个工件在选择是否加工时有两个拒绝尺度,各自独立决策,最后选择较好的结果作为最终输出.笔者设计了算法H,得到其关于s的参数竞争比为s+2s+1,优于只有一个拒绝尺度的经典情形.最后又给出问题的一个下界(s+1)2s2+s+1,上下界的最大差距在s=1时达到0.167.
研究一箇兩檯同類機可拒絕半在線排序問題,機器速度一箇為1,另一箇為s∈[1,+∞),加工允許中斷.噹工件到達時,可以將其接受加工,佔用一定的機器負荷,也可以將其拒絕,付齣相應的罰值,目標為使被接受工件集產生的makespan和被拒絕工件集的總罰值之和最小.問題進一步假定每箇工件在選擇是否加工時有兩箇拒絕呎度,各自獨立決策,最後選擇較好的結果作為最終輸齣.筆者設計瞭算法H,得到其關于s的參數競爭比為s+2s+1,優于隻有一箇拒絕呎度的經典情形.最後又給齣問題的一箇下界(s+1)2s2+s+1,上下界的最大差距在s=1時達到0.167.
연구일개량태동류궤가거절반재선배서문제,궤기속도일개위1,령일개위s∈[1,+∞),가공윤허중단.당공건도체시,가이장기접수가공,점용일정적궤기부하,야가이장기거절,부출상응적벌치,목표위사피접수공건집산생적makespan화피거절공건집적총벌치지화최소.문제진일보가정매개공건재선택시부가공시유량개거절척도,각자독립결책,최후선택교호적결과작위최종수출.필자설계료산법H,득도기관우s적삼수경쟁비위s+2s+1,우우지유일개거절척도적경전정형.최후우급출문제적일개하계(s+1)2s2+s+1,상하계적최대차거재s=1시체도0.167.
