文献类型：期刊文献

中文题名：机器有使用限制的两台同类机排序的在线LS算法

英文题名：Online Algorithms LS of the Two Uniform Machines Scheduling with an Availability Constraint

作者：李红英[1]

机构：[1]华东理工大学数学系,上海200237

年份：2006

卷号：32

期号：9

起止页码：1134

中文期刊名：华东理工大学学报（自然科学版）

外文期刊名：Journal of East China University of Science and Technology

收录：CSTPCD;;EI(收录号：20064610240529);Scopus;北大核心:【北大核心2004】；CSCD:【CSCD2011_2012】；

语种：中文

中文关键词：同类机;使用限制;在线算法;竞争比

外文关键词：uniform machine; availability constraint; online algorithm; competitive ratio

摘要：研究了机器有使用限制的两台同类机排序问题的在线算法,对于Q2 a(M1)Cmax和Q2 a(M2)Cmax问题,证明了LS算法的竞争比分别为1+s12和s2+s12,并举例说明了这两个界是紧的。
The online algorithms of two uniform machines scheduling problem with availability constraint are studied. The competitive ratios of LS algorithms of Q2 ｜ a （M1）｜ Cmax and Q2 ｜ a （M2） ｜ Cmax areproved to be 1＋1/S2 and S2＋1/S2respectively. And the ratios are tight~