图形处理中一类Flow-shop问题的改进算法

摘要：

考虑图形处理中的一类两台处理器上的Flow-shop调度问题,目标是极小化最早完工时间.每个任务包含两道工序,第一道工序可以在两台处理器中的任何一台上处理,而第二道则只能在第二台处理器上处理,且必须在第一道工序完工之后才能进行.对该问题,设计了一个改进的多项式时间近似算法,在绝对性能方面,该算法的最坏情况界为3/2;而从实例计算的平均效果方面,该算法所得的结果比原有的贪婪算法所得的结果要好20％左右.

关键词：调度、近似算法、最早完成时间、流水作业

所属期刊栏目：37

分类号：TP391.41(计算技术、计算机技术)

资助基金：国家自然科学基金11001242;11071220;浙江省自然科学基金Y6090175;Y6090554

在线出版日期：2012-03-20（万方平台首次上网日期，不代表论文的发表时间）

页码：1381-1386