A new greedy algorithm for multi-processor scheduling with gang scheduling

Vol.5 No.1

Year: 2010

Issue: July - September

Title: A new greedy algorithm for multi-processor scheduling with gang scheduling   

Author Name: Sarath B. Siyambalapitiya, M. Sandirigama   

Synopsis:   

In this study, we propose some greedy algorithms for the multi-processor job scheduling problem. A given list of jobs are arranged according to the time duration for processing. Depending on the job processing times, some jobs are divided into multi-threads while others remain as single thread jobs. Multi-thread jobs are processed based on the concept of gang scheduling. A lower bound for the total processing time is computed. The results of the proposed algorithm is presented using a percentage gap from the optimal solution  using this lower bound.