Approximation algorithms for general parallel task scheduling |
| |
Authors: | Oh-Heum Kwon Kyung-Yong Chwa |
| |
Affiliation: | a Electronics, Computer, and Communication Division, Pukyong National University, Daeyeon-dong 599-1, Nam-gu, Pusan 608-737, South Korea b Department of Computer Science, KAIST, Kusong-dong 373-1, Yusong-gu, Taejon 305-701, South Korea |
| |
Abstract: | A general parallel task scheduling problem is considered. A task can be processed in parallel on one of several alternative subsets of processors. The processing time of the task depends on the subset of processors assigned to the task. We first show the hardness of approximating the problem for both preemptive and nonpreemptive cases in the general setting. Next we focus on linear array network of m processors. We give an approximation algorithm of ratio O(logm) for nonpreemptive scheduling, and another algorithm of ratio 2 for preemptive scheduling. Finally, we give a nonpreemptive scheduling algorithm of ratio O(log2m) for m×m two-dimensional meshes. |
| |
Keywords: | Algorithms Parallel task scheduling Approximation algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|