| 机器带准备时间的三台平行机排序问题的线性时间算法 |
| |
| 引用本文： | 范静,杨启帆.机器带准备时间的三台平行机排序问题的线性时间算法[J].浙江大学学报(理学版),2005,32(3):258-263. |
| |
| 作者姓名： | 范静 杨启帆 |
| |
| 作者单位： | 浙江大学,数学系,浙江,杭州,310027 |
| |
| 摘 要： | 对于机器带准备时间的平行机排序问题,研究了3台机器的情况,给出了线性时间的对偶阈值算法族DA3(ε)(其中ε为可选参数),并证明了当ε=1/5时,对偶阈值算法DA3(1/5)的近似比为6/5,且该界为紧的.这是到目前为止最小且时间复杂性为线性时间的算法.
|
| 关 键 词： | 排序 近似比 机器准备时间 线性时间 |
| 文章编号： | 1008-9497(2005)03-258-06 |
| 修稿时间： | 2003年9月5日 |
Linear time algorithm for scheduling on three parallel machines with non-simultaneous machine available times |
| |
| FAN Jing,YANG Qi-fan.Linear time algorithm for scheduling on three parallel machines with non-simultaneous machine available times[J].Journal of Zhejiang University(Sciences Edition),2005,32(3):258-263. |
| |
| Authors: | FAN Jing YANG Qi-fan |
| |
| Abstract: | |
| |
| Keywords: | scheduling performance ratio machine available time linear time |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《浙江大学学报(理学版)》浏览原始摘要信息 |
| 点击此处可从《浙江大学学报(理学版)》下载免费的PDF全文 |
|
