机器有两种不同速度的平行工件半在线排序研究  

Semi Online Scheduling of Parallel Jobs on Uniform Machines with Two Different Speeds

作　　者：高建军[1] 秦小锋[1] 

机构地区：[1]郑州防空兵指挥学院,河南郑州450052

出　　处：《洛阳师范学院学报》2009年第2期24-26,共3页Journal of Luoyang Normal University

摘　　要：本文提出了新模型Q2m︱rj=0,on-line-ncv︱C max,并通过分析模型的特点,设计出了半在线算法,引进等效化(Virtualization)概念证明了当P≥m(s+1)max/(i∈τ)mjPj时(其中P为工件集的总负荷),算法的竞争比为2-s/(m(s+1)).In this paper, a new model Q2m｜rj=0,mj,on-line-ncv｜Cmax is presented. Based on this model, a semi online algorithm is designed. With the definition of virtualization, this paper demonstrates the algorithm has competitive ratio of 2- s/m（s ＋1） when assuming that the total processing time P≥m（s＋1）ma i∈τ x mjpj.

关 键 词：平行工件 平行机 半在线排序 快机器 慢机器 

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