i-manager Publications

Performance Evaluation Of Some Greedy Based Multi-Processor Scheduling Algorithms

Ruwanthini Siyambalapitiya*, Manjula Sandirigama**

* Lecturer, Department of Statistics and Computer Science, University of Peradeniya, Sri Lanka.

** Head, Department of Computer Engineering, University of Peradeniya, Sri Lanka.

Periodicity:April - June'2013
DOI : https://doi.org/10.26634/jse.7.4.2315

Abstract

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.

Keywords

Performance, Approximation Algorithms, Makespan, Lower Bound, Percentage Gap.

How to Cite this Article?

Ruwanthini Siyambalapitiya and Manjula Sandirigama (2013). Performance Evaluation Of Some Greedy Based Multi-Processor Scheduling Algorithms.i-manager’s Journal on Software Engineering, 7(4), 1-12. https://doi.org/10.26634/jse.7.4.2315

References

[1]. Abraham, B., and Ledoletr, J. (2005). Statistical Methods for Forecasting, John Wiley.

[2]. Astrachan, O. (2003). Bubble Sort: An Archaeological Algorithmic Analysis, ACM SIGCSE Bulletin, 1-5.

[3]. Davis, R.I., and Burns, A. (2011). A survey of hard real-time scheduling for multiprocessor systems, ACM Computing Surveys 43, 35-44.

[4]. Feitelson, D.G. (1994). A survey of scheduling in multiprogrammed parallel systems, Technical Report RC 19790 (87657), IBM T.J. Watson Research Centre,.

[5]. Feitelson, D.G., and Rudolph, L. (1995). Parallel job scheduling issues and approaches, in Job Scheduling Strategies for Parallel Processing, Springer Verlag, Lecture Notes in Computer Science, 949, 1-18.

[6]. Graham, R.L. et al. (1979). Optimization and approximation in deterministic sequencing and scheduling: A Survey, Annals of Discrete Mathematics, 4, 287-326.

[7]. Johnson, D.S. (1974). Approximation algorithms for combinatorial problems, Journal of Computer and System Sciences, 9, 256-278.

[8]. Knuth, D. (1997). The art of computer programming, Volume 3: Sorting and searching, Third Edition, Addison-Wesley.

[9]. Lenstra, J.K., and Kan, A.H.G. (1981). Complexity of vehicle routing and scheduling problems, Networks, 11, 221-227.

[10]. Papadimitriou, C.H. (1993). Computational Complexity, Addison-Wesley, Redwood City, California.

[11]. Schulz, A.S. et al., (1997). Approximation algorithms, in Proceedings National Academy of Sciences, 94, 12734-12735.

[12]. Schwiegelshohn, U., and Yahyapour, R. (1998). Analysis of first-come-first-serve parallel job scheduling, in Proceedings of the Ninth SIAM Symposium on Discrete Algorithms, 629-638.

[13]. Siyambalapitiya, R., and Sandirigama, M. (2010). Efficient greedy algorithms for multi-processor scheduling, i-manager’s Journal on Software Engineering, Vol.4, No.4, April-June, 50-54, 2010.

[14]. Wolf, W. (2004). The Future of multiprocessor systems-on-chips, Proceedings of the 41st Annual Design Automation.

If you have access to this article please login to view the article or kindly login to purchase the article

Single Article

	North Americas,UK, Middle East,Europe		India	Rest of world
	USD	EUR	INR	USD-ROW
Online	15	15

ADD TO CART

Options for accessing this content:

If you would like institutional access to this content, please recommend the title to your librarian.
If you already have i-manager's user account: Login above and proceed to purchase the article.
New Users: Please register, then proceed to purchase the article.