带准备时间的两台同类机半在线排序  

Semi On-Line Schedule on Two Uniform Machines with Machines Available Times

作　　者：李鹏举[1] 朱辉[1] 

机构地区：[1]苏州工业园区软件与服务外包职业学院,江苏苏州215123

出　　处：《江南大学学报（自然科学版）》2009年第3期375-378,共4页Joural of Jiangnan University (Natural Science Edition)　

摘　　要：针对机器速度和准备时间不同,探讨了带机器准备时间的两台同类机半在线排序问题,以达到优化工作效率的目的。目标为极小化最大机器完工时间,对于所有工件中最大工件的加工时间已知的这种半在线情形,给出了一个竞争比不少于(s+1)/(2s+1)的M IN半在线算法。In the paper, we consider a semi-on-line scheduling problem on two uniform system （different machine speed） with different machine available time, to reach the optimizing availability, where the objective is to minimize makespan of the schedule. For that the maximum processing time in known advance, we propose a semi on-line algorithm machine purpose the case with the competitive ratio, which is not less than （s ＋ 1）/（2s ＋ 1）.

关 键 词：半在线算法 竞争比 准备时间 

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