首页 | 本学科首页   官方微博 | 高级检索  
     检索      

带机器准备时间的平行机ordinal排序及近似算法
引用本文:谈之奕,何勇.带机器准备时间的平行机ordinal排序及近似算法[J].应用数学学报,2002,25(2):223-229.
作者姓名:谈之奕  何勇
作者单位:浙江大学数学系,杭州,310027
基金项目:国家973重点基础研究专项经费(G1998030401(2)),高等学校优秀青年教师教学科研奖励计划资助项目.
摘    要:本文研究带机器准备时间的m台平行机ordinal在线排序问题。讨论了在极小化最大机器完工时间和极小化最大工件完工时间两种目标下的不同下界和相应的在线近似算法。对第一个目标,我们得到了3/2的下界和最坏情况界为2-1/m的近似算法。对第二个目标,我们得到了最坏情况为m的最好近似算法。我们还对一些特殊情况进行了分析。

关 键 词:机器准备时间  平行机  ordinal排序  近似算法  半在线排序  最坏情况界  排序问题

Ordinal On-line Scheduling on Parallel Machines with Machine Release Times
TAN ZHIYI,HE YONG.Ordinal On-line Scheduling on Parallel Machines with Machine Release Times[J].Acta Mathematicae Applicatae Sinica,2002,25(2):223-229.
Authors:TAN ZHIYI  HE YONG
Abstract:Abstract This paper investigates ordinal on-line scheduling on parallel machines with machine release times. Two objects of minimizing the last machine completion time and minimizing the last job completion time are considered. For the first object, we present an algorithm with worst-case ratio of 2 ?1/m. For the second object, we show that the best possible algorithm has a worst-case ratio of m. We further consider three special cases.
Keywords:Semi on-line scheduling  approximation algorithm  worst-case ratio
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号