| Linear Time Algorithms for Parallel Machine Scheduling |
| |
| 作者姓名： | Zhi Yi TAN Yong HE |
| |
| 作者单位： | [1]Department of Mathematics, State Key Lab of CAD ＆ CG, Zhejiang University, Hangzhou 310027, P. R. China [2]Department of Mathematics, Zhejiang University, Hangzhou 310027, P. R. China |
| |
| 基金项目： | Supported by tile National Natural Science Foundation of China （10301028, 60021201）. A preliminary version of this paper appeared in the proceedings of the 1st International Conference on Algorithmic Applications in Management, Lecture Notes in Computer Science 3521 |
| |
| 摘 要： |
|
| 关 键 词： | 时序安排 设计算法 分析算法 计算数学 |
| 修稿时间： | 2005-02-042006-01-26 |
Linear Time Algorithms for Parallel Machine Scheduling |
| |
| Zhi Yi TAN Yong HE.Linear Time Algorithms for Parallel Machine Scheduling[J].Acta Mathematica Sinica,2007,23(1):137-146. |
| |
| Authors: | Zhi Yi Tan Yong He |
| |
| Institution: | (1) Department of Mathematics, State Key Lab of CAD & CG, Zhejiang University, Hangzhou 310027, P. R. China;(2) Department of Mathematics, Zhejiang University, Hangzhou 310027, P. R. China |
| |
| Abstract: | This paper addresses linear time algorithms for parallel machine scheduling problems. We introduce a kind of threshold algorithms and discuss their main features. Three linear time threshold algorithm classes DT, PT and DTm are studied thoroughly. For all classes, we study their best possible algorithms among each class. We also present their application to several scheduling problems, The new algorithms are better than classical algorithms in time complexity and/or worst-case ratio. Computer-aided proof technique is used in the proof of main results, which greatly simplifies the proof and decreases case by case analysis. |
| |
| Keywords: | scheduling design and analysis of algorithm worst-case ratio computer-aided proof |
| 本文献已被 维普 SpringerLink 等数据库收录！ |
|
