预知两种信息带准备时间的两台同型机半在线排序  

A Semi-online Scheduling Problem with Two Types of Information on Two Identical Machines with Non-simultaneous Machine Release Times

作　　者：李蒙[1] 孙秋媚[1] 封汉颖[1] 

机构地区：[1]军械工程学院基础部,河北石家庄050003

出　　处：《数学的实践与认识》2011年第20期184-187,共4页Mathematics in Practice and Theory

摘　　要：研究了P2,r_j/decr,opt/Cmax问题,即预知工件大小非增排列decr和最优目标值opt的两台同型机的带准备时间的半在线问题,并给出了竞争比为7/6的半在线算法.This paper considers the problem P2, rj/decr,opt/Cmax, i. e. the semi-online problem on two identical machines with non-increasing sizes of all jobs and the optimal objective function value known in advance. A semi-online algorithm with competitive ratio 7/6 is presented.

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

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