Performance Evaluation Of Some Greedy Based Multi-Processor Scheduling Algorithms

Vol. 7 No. 4

Year: 2013

Issue : Apr-Jun

Title : Performance Evaluation Of Some Greedy Based Multi-Processor Scheduling Algorithms

Author Name : Ruwanthini Siyambalapitiya, Manjula Sandirigama

Synopsis :

Multi-processor scheduling problem has been shown to be NP-hard and therefore, no exact optimal solution algorithms could be constructed. In this study, we present the computational experience and performance evaluation of some greedy based algorithms to solve the multi-processor scheduling problem. These algorithms are approximation algorithms in which we compute lower bounds and percentage gaps to show that our solutions are close to relevant optimal solutions. We shall also show that the performance of these algorithms improves as the problem size grows. We make use of the principle of cumulative moving averages to show that the algorithms can be applied to large scale problem instances as well. These algorithms are very fast so that they can be applied to solve large scale problems found in practice, without much computational burden.