运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2009年
1期
29-36
,共8页
运筹学%排序%可拒绝%半在线%近似算法%竞争比
運籌學%排序%可拒絕%半在線%近似算法%競爭比
운주학%배서%가거절%반재선%근사산법%경쟁비
Operations research%scheduling%rejection%semi on-line%approximation al-gorithm%competitive ratio
本文讨论一个两台可拒绝同型机半在线排序问题.当工件到达时,可以被拒绝,但要付出一定的罚值,也可以被接收加工,消耗一定的加工时间.其目标是要使所有加工工件生成的makespan和被拒绝工件的总罚值之和最小.加工不允许中断.进一步,机器带有两个并行处理子系统,可以提供两种排序方案,最后选取较好的一种.这是第一个在可拒绝同型机排序模型中使用半在线信息,我们设计出一个近似算法,其竞争比为3/2,另外又给出一个√3+1/2≈1.366的下界.
本文討論一箇兩檯可拒絕同型機半在線排序問題.噹工件到達時,可以被拒絕,但要付齣一定的罰值,也可以被接收加工,消耗一定的加工時間.其目標是要使所有加工工件生成的makespan和被拒絕工件的總罰值之和最小.加工不允許中斷.進一步,機器帶有兩箇併行處理子繫統,可以提供兩種排序方案,最後選取較好的一種.這是第一箇在可拒絕同型機排序模型中使用半在線信息,我們設計齣一箇近似算法,其競爭比為3/2,另外又給齣一箇√3+1/2≈1.366的下界.
본문토론일개량태가거절동형궤반재선배서문제.당공건도체시,가이피거절,단요부출일정적벌치,야가이피접수가공,소모일정적가공시간.기목표시요사소유가공공건생성적makespan화피거절공건적총벌치지화최소.가공불윤허중단.진일보,궤기대유량개병행처리자계통,가이제공량충배서방안,최후선취교호적일충.저시제일개재가거절동형궤배서모형중사용반재선신식,아문설계출일개근사산법,기경쟁비위3/2,령외우급출일개√3+1/2≈1.366적하계.
This paper investigates a semi on-line scheduling problem on two identical machines with rejection. When a job arrives,we can either reject it ,in which case we pay its penalty, or accept it in which case it contributes its processing time to the makespan of the constructed schedule. The objective is to minimize the sum of the makespan of the schedule of all accepted jobs and the penalties of all rejected jobs. No preemption is allowed. In addition, two parallel systems are available. Two schemes could be choosen and we can select the better solution finally. This is the first semi on-line version on iden-tical processors with rejection. We present an approximation algorithm with competitive ratio 3/2 and a lower bound of √3+1/2≈ 1.366 is proposed.
