| 使两台和三台平行机的最小完工时间为最大的线性算法 |
| |
| 引用本文： | 范静,张峰.使两台和三台平行机的最小完工时间为最大的线性算法[J].上海第二工业大学学报,2006,23(2):84-91. |
| |
| 作者姓名： | 范静 张峰 |
| |
| 作者单位： | 上海第二工业大学理学院,上海,201209 |
| |
| 基金项目： | 国家自然科学基金资助项目(No.10371071)，上海高校选拔培养优秀青年教师科研专项基金资助项目(No.SLX306002) |
| |
| 摘 要： | 讨论使两台和三台平行机的最小完工时间为最大的线性算法——对偶阈值算法DA m(ε),其中ε是参数。对于问题P2||Cmin,证明对偶阈值算法DA2(1/7)的最坏情况界为6/7,并证明此界为紧界;对于问题P3||Cmin,进而提出层次对偶阈值算法TDA3(ε),并证明当ε取2/11时,算法的最坏情况界为9/11。这些都是线性时间算法中使最坏情况界值为最小的算法。
|
| 关 键 词： | 排序 最坏情况界 线性算法 |
| 文章编号： | 1001-4543（2006）02-0084-08 |
| 收稿时间： | 2006-02-28 |
| 修稿时间： | 2006-05-25 |
Linear Algorithms for Maximizing the Minimum Machine Completion Time on Two and Three Parallel Machines |
| |
| FAN Jing,ZHANG Feng.Linear Algorithms for Maximizing the Minimum Machine Completion Time on Two and Three Parallel Machines[J].Journal of Shanghai Second Polytechnic University,2006,23(2):84-91. |
| |
| Authors: | FAN Jing ZHANG Feng |
| |
| Affiliation: | School of Science, Shanghai Second Polytechnic University, Shanghai 201209, P.R.China |
| |
| Abstract: | |
| |
| Keywords: | scheduling worst-case ratio linear time algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《上海第二工业大学学报》浏览原始摘要信息 |
|
点击此处可从《上海第二工业大学学报》下载全文 |
|
