| Q2‖Cmax的对偶近似算法 |
| |
| 引用本文： | 何勇.Q2‖Cmax的对偶近似算法[J].应用数学学报,1999,22(1):123-129. |
| |
| 作者姓名： | 何勇 |
| |
| 作者单位： | 浙江大学应用数学系!杭州310027 |
| |
| 摘 要： | 本文讨论两台同类平行机排序问题，首先给出Ｍｕｌｔｉｆｉｔ算法在不同迭代初值下的紧界，然后利用一个新设计的对偶贪婪子过程构造出线性时间６／５－复合近似算法。
|
| 关 键 词： | 同类机排序 近似算法 排序 对偶近似算法 |
THE DUAL APPROXIMATE APPROACH FOR SCHEDULING PROBLEM Q_2|| C_(max) |
| |
| HE YONG.THE DUAL APPROXIMATE APPROACH FOR SCHEDULING PROBLEM Q_2|| C_(max)[J].Acta Mathematicae Applicatae Sinica,1999,22(1):123-129. |
| |
| Authors: | HE YONG |
| |
| Abstract: | In this paper, we consider the scheduling problem Q2 Cmax. We devise a linear time compound algorithm LCQ1 with a worst case analysis bound of Since MF algorithm has a worst case bound and time complexity O(n log n), LCQ1 algorithm is the best one of known simple approximation algorithms. |
| |
| Keywords: | Uniform machine scheduling approximation algorithm worst case analysis |
| 本文献已被 CNKI 维普 等数据库收录！ |
