三台同类机在线排序问题一种特殊情形的研究

摘要：

研究三台平行同类机排序问题的一种特殊情形,即三台同类机的加工速度分别为s1=s2=s≥1,s3=1.证明了对该问题来说,经典的LS算法的竞争比为min”4s+1/2s+1,3s+1/2s”;同时证明当s≥3,该问题的下界为3s+1/2s,从而说明了LS算法是可能存在的最好的在线算法.此外,对1≤s＜3时问题的下界也做了一些讨论,这时虽然不能确定LS算法仍然是可能存在的最好的在线算法,但可知道这时LS算法与可能存在的最好的在线算法在竞争比上相差少于0.4299.

关键词：在线、同类机、竞争比

所属期刊栏目：26

分类号：O223(运筹学)

在线出版日期：2006-08-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：41-46