JSE_V7_N4_RP1 Ruwanthini Siyambalapitiya Manjula Sandirigama Journal on Software Engineering 2230–7168 7 4 1 12 Performance, Approximation Algorithms, Makespan, Lower Bound, Percentage Gap 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. April - June 2013 Copyright © 2013 i-manager publications. All rights reserved. i-manager Publications http://www.imanagerpublications.com/Article.aspx?ArticleId=2315