预知两种信息带准备时间的平行机半在线排序  

Parallel Machine Scheduling with Machine Release Times under Two Types of Information

作　　者：谭金芝[1] 胡觉亮[2] 

机构地区：[1]浙江大学数学系 [2]浙江理工大学信息与计算科学系,浙江杭州310033

出　　处：《管理工程学报》2006年第4期17-19,共3页Journal of Industrial Engineering and Engineering Management

基　　金：浙江省自然科学基金(Y605316)

摘　　要：本文研究了P2,rj/sum&max/Cmax问题,即预知所有工件加工时间总和sum和最大工件加工时间max的两台处理器的带准备时间的半在线问题,并给出了竞争比为6/5的最优半在线算法。This paper considers the problem P2 , rj/sum ＆ max/Cmax, i. e. the semi-online problem on two identical machines with the total and the largest processing time of all jobs known in advance. An optimal semi-online algorithm with competitive ratio 6/5 is presented.

关 键 词：平行机排序 半在线 近似算法 竞争比 

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