机器带准备时间的三台平行机排序问题的线性时间算法  被引量:12

Linear time algorithm for scheduling on three parallel machines with non-simultaneous machine available times.

在线阅读下载全文

作  者:范静[1] 杨启帆[1] 

机构地区:[1]浙江大学数学系,浙江杭州310027

出  处:《浙江大学学报(理学版)》2005年第3期258-263,共6页Journal of Zhejiang University(Science Edition)

基  金:国家自然科学基金资助项目 (10 2 71110 )

摘  要:对于机器带准备时间的平行机排序问题,研究了3台机器的情况,给出了线性时间的对偶阈值算法族DA3(ε)(其中ε为可选参数) ,并证明了当ε=15 时,对偶阈值算法DA315 的近似比为65 ,且该界为紧的.这是到目前为止最小且时间复杂性为线性时间的算法.As to the scheduling problem of parallel machines with non-simultaneous machine available times, three machines are investigated. The linear time algorithm called Dual-Threshold Algorithm Class DA3(ε), where ε is an optional parameter, is proposed. Moreover, it is proved that if ε equals 15, the performance ratio of Dual-Threshold Algorithm DA315 is 65, which is the tight one. And up to now, this algorithm is the best algorithm with the least performance ratio and linear time.

关 键 词:排序 近似比 机器 住备时间 线性时间 

分 类 号:O223[理学—运筹学与控制论]

 

参考文献:

正在载入数据...

 

二级参考文献:

正在载入数据...

 

耦合文献:

正在载入数据...

 

引证文献:

正在载入数据...

 

二级引证文献:

正在载入数据...

 

同被引文献:

正在载入数据...

 

相关期刊文献:

正在载入数据...

相关的主题
相关的作者对象
相关的机构对象