平行机的实时到达on-line算法下界的改进

摘要：

本文考虑了平行机实时到达的在线问题.模型中,工件是陆续到达的,工件的个数、到达时间是事先未知的,而且只有当工件到达,才知其加工时间,目标是使所有工件都加工完的时间达到最小.Chen与Vestjens(1996年)证明了该在线问题不存在性能比小于1.3473的on-line算法.本文将此界改进为(5-√5)/2.

关键词：排序、on-line算法、性能比

所属期刊栏目：14

分类号：O223(运筹学)

资助基金：中国科学院资助项目19701028;科技部科研项目

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

页数：共4页

页码：315-318