可拒绝的同类机在线排序(英文)  

On-line Scheduling with Rejection on Uniform Parallel Machines

作　　者：刘守鹏[1] 高明海[1] 张玉忠[2] 

机构地区：[1]滨州医学院卫生管理学院,烟台264003 [2]曲阜师范大学运筹与管理学院,日照276826

出　　处：《大学数学》2012年第1期27-32,共6页College Mathematics

基　　金：The Natural Science Foundation of China under Grant(11001117)

摘　　要：考虑了带拒绝费用的在线同类机排序模型.工件一个一个的到达,到达后或被接受,或以一定的费用被拒绝,目标是最小化最大完工时间与总的拒绝费用之和.我们提供了一个在线算法和分析了算法的竞赛比.We consider the version of on-line uniform machines scheduling with rejection penalty. The jobs arrive one by one and can be either accepted and scheduled, or be rejected at a certain penalty. The objective is to minimize the sum of the makespan of the accepted jobs and the total penalty of the rejection jobs. We propose an on-line algorithm and analyze the competitive ratio.

关 键 词：在线排序 竞赛比 同类机 

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