i-manager Publications

Comparison of some Algorithms for Multi-Processor Job Scheduling Problem based on the Random Nature of Job Completion Times

Ruwanthini Siyambalapitiya*, Manjula Sandirigama**

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

** Senior Lecturer, Department of Computer Engineering, University of Peradeniya, Sri Lanka.

Periodicity:March - May'2014
DOI : https://doi.org/10.26634/jcom.2.1.2845

Abstract

In this paper, the authors wish to report some further computational results related to two algorithms proposed earlier for the multi-processor job scheduling problem. Here, they have compared the performance of an FCFS-based algorithm for multi-processor scheduling with a greedy-based algorithm known as Decreasing-Ascend algorithm. They have considered the random nature of job completion times, to get a deeper insight into the performance of the algorithms. More than 20,000 data sets were created with varying combinations of jobs with shorter job lengths and longer job lengths. They keep the total execution time (sum of individual job durations) as fixed for all the instances considered and have showed that even if we consider this random situation, the performance level of the algorithms reported earlier is still applicable.

Keywords

Makespan, Lower Bound, Approximation Algorithms, Problem Size Ratio.

How to Cite this Article?

Siyambalapitiya, R., and Sandirigama, M. (2014). Comparison of Some Algorithms for Multi-Processor Job Scheduling Problem Based on the Random Nature of Job Completion Times. i-manager’s Journal on Computer Science, 2(1), 6-12. https://doi.org/10.26634/jcom.2.1.2845

References

[1]. Davis, R.I., and Burns, A. (2011). A survey of hard realtime scheduling for multiprocessor systems, ACM Computing Surveys, Vol.43, pp.35-44.

[2]. 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.

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

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

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

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

[7]. 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.

[8]. 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, pp.50-54.

[9]. Siyambalapitiya, R., and Sandirigama, M. (2013). Performance evaluation of some greedy based multiprocessor Scheduling algorithms, i-manager’s Journal on Software Engineering, Vol.7, No.4, April-June, pp. 1-12.

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.