应用于图形处理的一个混合流水作业排序问题的多项式时间近似策略

摘要：

由于早期的图形处理器浮点运算能力不强，所以在处理图形问题时一般由中央处理器处理数据运算环节，然后再由图形处理器进行图像处理。但是最近几年图形处理器的浮点运算能力得到很大提高，相信很快就能胜任原先只有中央处理器才能完成的图形问题中的数据运算任务，为此前瞻性的研究在这样一种新情况下如何合理调度中央处理器和图形处理器来更快的处理图形问题是很有必要的。事实上该问题其实相当于一个两阶段两台处理器的混合流水作业问题：有两台处理器和一批需要加工的工件，每个工件都包含两个任务，前一个任务是为第二个任务做准备的。第一个任务可以选择在任何一台处理器上处理，而第二个任务则必须当第一个任务完成后，在第二台处理器上处理，目标是尽可能早的处理完所有工件。对于该问题，设计了一个多项式时间近似策略(PTAS)来给出最优调度方案。

关键词：调度、多项式时间近似策略、最大完工时间、混合流水作业

分类号：O223(运筹学)

资助基金：浙江省自然科学基金LQ13A010010;宁波市自然科学基金2012A610023

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

页数：共10页

页码：95-104