The week's pick
Reseach Article
A Survey of Static Scheduling Algorithm for Distributed Computing System
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 129 - Number 2 |
| Year of Publication: 2015 |
| Authors: Khushboo Singh, Mahfooz Alam, Sushil Kumar Sharma |
10.5120/ijca2015906828
|
Khushboo Singh, Mahfooz Alam, Sushil Kumar Sharma . A Survey of Static Scheduling Algorithm for Distributed Computing System. International Journal of Computer Applications. 129, 2 ( November 2015), 25-30. DOI=10.5120/ijca2015906828
Abstract
The static scheduling algorithms are widely used to evaluate the performance of distributed computing system. In such systems, purpose of scheduling algorithm is to allocate tasks to available processor so as to efficiently utilize this processor and to reduce the makespan, total computational cost and various other such factors, with the motive of achieving optimal solution. Scheduling algorithms are classified into two broad categories i.e., static scheduling algorithms and dynamic scheduling algorithms. In this paper we are discussing various static scheduling algorithm and numerous problems in various levels of the homogeneous and heterogeneous distributed systems. Also we are comparing these algorithms on the basis of various factors such as speedup, time complexity, scheduling length ratio, normalized scheduling length and so on.
References
- Kalpana A.M., Avinash W., “Comparative Study of Static Task Scheduling Algorithms for Heterogeneous Systems”International Journal on Computer Science and Engineering (IJCSE), Vol. 5, No. 03, 2013.
- Yanyan D and Xiangli Z, “A Synthesized Heuristic Task Scheduling Algorithm”, Hindawi Publishing Corporation The Scientific World Journal, Vol. 2014, 2014.
- Ranjit R, “A Novel Approach for Task Scheduling in Multiprocessor System”, International Journal of Computer Applications, Vol. 44, 2012.
- Ranjit R, C.P .Katti and Nidhi R, “A Modified Task Scheduling Algorithm of Task Graph without Communication Time”, International Journal of New Computer Architectures and their Applications (IJNCAA) Vol.3, 2013.
- Wei Z and Rizos S, “Stochastic DAG scheduling using a Monte Carlo approach”, Journal of Parallel Distributed Computing, Vol. 73 , 2013.
- Mahfooz A and Ankur K.V “A Comparative Study of Interconnection Network”, International Journal of Computer Applications (0975 – 8887) Vol. 127, No. 4, pp.37-43, 2015.
- M. Rathna D and A.Anju, “Multiprocessor Scheduling of Dependent Tasks to Minimize Makespan and Reliability Cost Using NSGA-II”, International Journal in Foundations of Computer Science & Technology (IJFCST), Vol.4, 2014.
- Chitra, Rajaram, and Venkatesh, “Application and comparison of hybrid evolutionary multiobjective optimization algorithms for solving task scheduling problem on heterogeneous systems”, Applied soft computing, Vol. 11, 2011.
- Nirmeen A. B., Magdy A.K., Mervat M. and Fatma O., “A new algorithm for static task scheduling forheterogeneous distributed computing systems”, African Journal of Mathematics and Computer Science Research Vol. 4, 2011.
- Kamaljit K, Amit C, and Gurvinder S, "Heuristics based genetic algorithm for scheduling static tasks in homogeneous parallel system, "International journal of computer science and security, Vol.4, 2010.
- Jin S, Schiavone G, Turgut T, “A performance study of multiprocessor task scheduling algorithms”, Journal of Supercomputing, Vol.43, 2008.
- Sang C K, Sunggu L and Jaegyoon H, “Push-Pull: Deterministic Search-Based DAG Scheduling for HeterogeneousCluster Systems”, IEEE Transactions on Parallel and Distributed Systems, Vol. 18, 2007.
- Haluk T, Salim H, Min-You Wu, “Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing”, IEEE transactions on parallel and Distributed systems, Vol. 13, 2002.
- Hou E S, Ansari N, Ren H, “A Genetic Algorithm for Multiprocessor Scheduling”,IEEE Transactions on Parallel and Distributed Systems,Vol.5, 1994.
- Tarek H, Jan J, “A Near Lower-Bound Complexity Algorithm for Compile-Time Task Scheduling in HeterogeneousComputing Systems”, Proceedings of the ISPDC/HeteroPar’04 IEEE, 2004.
- Topcuoglu H, Hariri S, Wu MY,” Performance-Effective and LowComplexity Task Scheduling for Heterogeneous Computing,” IEEE Transactions on Parallel Distributed Systems, Vol.13, 2005.
- Daoud MI, Nawwaf K, “A High Performance Algorithm For StaticTask Scheduling In Heterogeneous Distributed Computing Systems”, IEEE Transactions on Parallel Distributed Systems, Vol.28, 2007.
- Adam T L, Candy K M, Dickson J,”A Comparison of list Scheduling for parallel processing systems”, Communication of the ACM, Vol.17, 1974.
- Hwang J J, Chow Y C, Anger F D, Lee C Y,” Scheduling precedence graph with interprocessor communication time”, SIAM Journal of Computing, Vol.18, 1989.
- Kruatrachue B, Lewis T G, “Insertion Scheduling Heuristic Algorithm”, Technical Report Oregon State University, 87-60-3, 1987.
- Ahmad, Ishfaq, and Yu-Kwong K, "On parallelizing the multiprocessor scheduling problem, "Parallel and Distributed Systems, IEEE Transactions, Vol.10, 1999.
- Sinclair, J. B., "Efficient computation of optimal assignments for distributed tasks." Journal of Parallel and Distributed Computing, Vol.4, 1987.
- Yeshwant K, “Data Structure Using C”, BPB Publications 2003.
- Kwok, Yu-Kwong, and Ishfaq A, "A Parallel Genetic-Search-Based Algorithm for Scheduling Arbitrary Task Graphs to Multiprocessors”, In Proceedings of the 9th IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS'97), Vol. 13, 1997.
Index Terms
Keywords