CAJ | 학술논문

由于早期的图形处理器浮点运算能力不强，所以在处理图形问题时一般由中央处理器处理数据运算环节，然后再由图形处理器进行图像处理。但是最近几年图形处理器的浮点运算能力得到很大提高，相信很快就能胜任原先只有中央处理器才能完成的图形问题中的数据运算任务，为此前瞻性的研究在这样一种新情况下如何合理调度中央处理器和图形处理器来更快的处理图形问题是很有必要的。事实上该问题其实相当于一个两阶段两台处理器的混合流水作业问题：有两台处理器和一批需要加工的工件，每个工件都包含两个任务，前一个任务是为第二个任务做准备的。第一个任务可以选择在任何一台处理器上处理，而第二个任务则必须当第一个任务完成后，在第二台处理器上处理，目标是尽可能早的处理完所有工件。对于该问题，设计了一个多项式时间近似策略(PTAS)来给出最优调度方案。
유우조기적도형처리기부점운산능력불강，소이재처리도형문제시일반유중앙처리기처리수거운산배절，연후재유도형처리기진행도상처리。단시최근궤년도형처리기적부점운산능력득도흔대제고，상신흔쾌취능성임원선지유중앙처리기재능완성적도형문제중적수거운산임무，위차전첨성적연구재저양일충신정황하여하합리조도중앙처리기화도형처리기래경쾌적처리도형문제시흔유필요적。사실상해문제기실상당우일개량계단량태처리기적혼합류수작업문제：유량태처리기화일비수요가공적공건，매개공건도포함량개임무，전일개임무시위제이개임무주준비적。제일개임무가이선택재임하일태처리기상처리，이제이개임무칙필수당제일개임무완성후，재제이태처리기상처리，목표시진가능조적처리완소유공건。대우해문제，설계료일개다항식시간근사책략(PTAS)래급출최우조도방안。
The floating point computing power of early graphic processing unit(GPU) is not strong. So it can’t do data processing. In other words, in early graphics processing, central processing unit(CPU) do data processing chain firstly, then GPU do image processing chain. But until now, much more GPU having stronger performance have been designed. In accordance with this trend, in near future, these powerful GPU can accomplish most work previously accomplished by CPU such as data processing. Prospectively studying how reasonable dispatch CPU and GPU to faster processing graphics issues in such a new case is interesting. Actually, this new problem is equal to a two-stage two-machine hybrid flow shop problem: There are two machines and n jobs. Each job has two tasks, the first task can be processed on either machine, called flexible task, while the second task can’t be processed unless the first task is completed and must be processed on the second machine. The objective of the problem is minimizing the makespan. A polynomial time approximation scheme (PTAS) for this problem is given in this paper.