후처리 태스크 스케줄링 알고리즘을 통한 스케줄링 개선 = Scheduling Improvement using Post-processing Task Scheduling Algorithm

다국어 초록 (Multilingual Abstract)

Task scheduling algorithm allocates tasks of an application to multiple processors in order to reduce the completion time of the application. In heterogeneous computing systems, task scheduling is more complicated problem than one in homogeneous computing system Though task scheduling problem in the heterogeneous system is NP-hard, it becomes popular in computer science because of its importance. Among many heuristic task scheduling algorithms, TANH algorithm possesses wide conditions for optimal schedule. Unfortunately, the algorithm has a flaw that some DAGs cannot be scheduled optimally despite they satisfy the conditions. We propose a post-processing task scheduling algorithm PCST that improves the schedules of DAGs fallen in the flaw. Thanks to the generality of PCST, the algorithm can be applied after any task scheduling algorithm in heterogeneous computing systems.