链组约束下部分批处理平行机在线排序  

On-Line Scheduling on Partial Batch Parallel Machine with Chains Precedence Constraints

作　　者：姚青华[1] 邱本花[1] 

机构地区：[1]郑州科技学院基础部,河南郑州450064

出　　处：《河南教育学院学报（自然科学版）》2011年第2期37-39,共3页Journal of Henan Institute of Education(Natural Science Edition)

基　　金：河南省基础与前沿技术研究计划资助项目(082300410070)

摘　　要：研究了一台是批处理机而另一台是正常机器、工件具有链组约束、最小化时间表长的两台恒同机在线排序问题.给出该问题竞争比为(5+1)/2的最好可能的在线算法.Abstract： Studied on-line scheduling of two identical parallel machines, one of which is processing machine and the other is normal. The jobs are chains-precedence constraints; the goal is to minimize the makespan. Provided a best possible on-line algorithm for the problem with competitive ration （√5＋ 1 ）/2.

关 键 词：在线排序 平行分批 链约束 竞争比 下界 

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