Scheduling Parallel Tasks with Intra-Communication Overhead in a Grid Computing Environment
With the improvements in wide-area network performance and powerful computers, it is possible to integrate a large number of distributed machines belonging to different organizations as a single system, for example, a grid computing environment. A grid computing environment involves cooperation and sharing resources among distributed machines. In this paper, a heuristic algorithm for this problem is proposed, and the performance bounds of the heuristic algorithm for scheduling parallel tasks in the environment with message passing machines and in the environment with shared memory machines are derived as 9/2 and 5/2 respectively. Although this problem is mainly about assigning tasks to a grid computing environment, however, by proper transformation it can be applied to the workforce assignment problem.