两台可拒绝同型机半在线排序问题(英文)  

Semi On-Line Scheduling on Two Identical Machines with Rejection

作　　者：闵啸[1] 孔祥庆[1] 

机构地区：[1]嘉兴学院数学与信息科学学院,浙江嘉兴314001

出　　处：《运筹学学报》2009年第1期29-36,共8页Operations Research Transactions

摘　　要：本文讨论一个两台可拒绝同型机半在线排序问题.当工件到达时,可以被拒绝,但要付出一定的罚值,也可以被接收加工,消耗一定的加工时间.其目标是要使所有加工工件生成的makespan和被拒绝工件的总罚值之和最小.加工不允许中断.进一步,机器带有两个并行处理子系统,可以提供两种排序方案,最后选取较好的一种.这是第一个在可拒绝同型机排序模型中使用半在线信息,我们设计出一个近似算法,其竞争比为3/2,另外又给出一个3^(1/3)+1/2≈1.366的下界.Abstract 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 identical 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.

关 键 词：运筹学 排序 可拒绝 半在线 近似算法 竞争比 

分 类 号：O223[理学—运筹学与控制论] TN710.2[理学—数学]