摘要
研究了机器有使用限制的两台同类机排序问题的在线算法,对于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~
出处
《华东理工大学学报（自然科学版）》
EI
CAS
CSCD
北大核心
2006年第9期1134-1137,共4页
Journal of East China University of Science and Technology
关键词
同类机
使用限制
在线算法
竞争比
uniform machine
availability constraint
online algorithm
competitive ratio
