东篱科研大数据发现系统（DRDS）

位置：成果数据库 > 期刊 > 期刊详情页

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

ISSN号：1001-4543
期刊名称：上海第二工业大学学报
时间：2006
页码：84-91
期号：02
便笺：31-1496/T
分类：O223[理学—运筹学与控制论;理学—数学]
作者地址：上海第二工业大学理学院,上海第二工业大学理学院上海201209,上海201209
作者机构：[1]上海第二工业大学理学院,上海201209
相关基金：国家自然科学基金资助项目（No.10371071）.上海高校选拔培养优秀青年教师科研专项基金资助项目（No.SLX306002）

作者：范静;张峰;

关键词：排序, 最坏情况界, 线性算法, scheduling, worst-case ratio, linear time algorithm

中文摘要：

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

英文摘要：

Linear time algorithms for maximizing the minimum machine completion time on two and three parallel machines have been researched. For P2‖Cmin, the worst-case ratio of Dual-Threshold Algorithm DA2（1/7） 6/7, which is the tight one, is proved. Moreover, for P2‖Cmin, Two-lay-Dual-Threshold Algorithms TDA3（ E ）, where ε is a optional parameter, is obtained, and modify the worst-case ratio to 9/11 if ε is equal to 2/11. Up to now, these algorithms are the best algorithms with the least worst-case ratio among linear time algorithms.

关于范静：