使两台和三台平行机的最小完工时间为最大的线性算法

摘要：

讨论使两台和三台平行机的最小完工时间为最大的线性算法--对偶阈值算法DAm(ε),其中ε是参数.对于问题P2‖Cmin,证明对偶阈值算法DA2(1/7)的最坏情况界为6/7,并证明此界为紧界;对于问题P3‖Cmin,进而提出层次对偶阈值算法TDA3(ε),并证明当ε取2/11时,算法的最坏情况界为9/11.这些都是线性时间算法中使最坏情况界值为最小的算法.

关键词：排序、最坏情况界、线性算法

所属期刊栏目：23

分类号：O223(运筹学)

资助基金：国家自然科学基金10371071;上海市高校选拔培养优秀青年教师科研项目SLX306002

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

页数：共8页

页码：84-91