CAJ | 학술논문

研究三台带服务等级的同型平行机可拒绝在线排序问题.设有三台同型机Mi,i=1,2,3,机器速度一致,并具有两个不同的加工等级g(Mi)=1,2,等级为1的机器数为k,等级为2的机器数为3-k.工件j按列表在线到达,每个工件具有三个参数:长度tj,罚值Pi及等级gj=1,2.当工件到达时,可以被接受且分配给某台机器加工,也可以被拒绝,付出相应的罚值.另外,当且仅当g(Mi)≤gj时,j可以分配给Mi加工,加工不允许中断.目标是使接受加工工件的最大完工时间和被拒绝工件的总罚值最小.针对k=1及k=2两种情况分别给出在线算法HI和H2,其竞争比为2,同时给出该问题的一个下界1.839.
연구삼태대복무등급적동형평행궤가거절재선배서문제.설유삼태동형궤Mi,i=1,2,3,궤기속도일치,병구유량개불동적가공등급g(Mi)=1,2,등급위1적궤기수위k,등급위2적궤기수위3-k.공건j안렬표재선도체,매개공건구유삼개삼수:장도tj,벌치Pi급등급gj=1,2.당공건도체시,가이피접수차분배급모태궤기가공,야가이피거절,부출상응적벌치.령외,당차부당g(Mi)≤gj시,j가이분배급Mi가공,가공불윤허중단.목표시사접수가공공건적최대완공시간화피거절공건적총벌치최소.침대k=1급k=2량충정황분별급출재선산법HI화H2,기경쟁비위2,동시급출해문제적일개하계1.839.