The week's pick
Random Articles
Reseach Article
Optimization of Multiprocessor Scheduling using Genetic Algorithm
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 78 - Number 4 |
| Year of Publication: 2013 |
| Authors: Poonam Panwar, Shreya Chauhan |
10.5120/13475-1161
|
Poonam Panwar, Shreya Chauhan . Optimization of Multiprocessor Scheduling using Genetic Algorithm. International Journal of Computer Applications. 78, 4 ( September 2013), 6-9. DOI=10.5120/13475-1161
Abstract
Multiprocessor architectures are becoming more attractive for embedded systems, primarily because major processor manufacturers like Intel and AMD are designing cost effective processors even for personal computers and laptops. This makes such architectures very desirable for embedded system applications with high computational workloads, where additional, cost-effective processing capacity is often needed. This increased usage of multiprocessor attracted the researchers for multiprocessor scheduling problems. Multiprocessor scheduling is a NP hard problem. In this paper a Genetic Algorithm (GA) based multiprocessor scheduling algorithm is proposed whose implementation is simple and the obtained results are optimal for the studied set of problems.
References
- Anderson J. and Srinivasan A. June 2001. Mixed Pfair/ ERfair scheduling of asynchronous periodic tasks in proceedings of the 13th Euromicro Conference on Real-time Systems, 76–85.
- Moir M. and Ramamurthy S. 1999. Pfair scheduling of fixed and migrating periodic tasks on multiple resources in proceedings of the 20th IEEE Real-time Systems Symposium, 294–303.
- Srinivasan A. , Holman P. , Anderson J. , and Baruah S. 2003. The case for fair multiprocessor scheduling in proceedings of the 11th International Workshop on Parallel and Distributed Real-time Systems.
- Baruah S. , Cohen N. , Plaxton C. G. , and Varvel. D. 1996. Proportionate progress: A notion of fairness in resource allocation. In Algorithmica, 15:600–625.
- Andersson B. , Baruah S. , and Jansson J. 2001. Static-priority scheduling on multiprocessors in proceedings of the 22nd IEEE Real-time Systems Symposium, 193–202.
- Srinivasan A. and Baruah S. 2002. Deadline-based scheduling of periodic task systems on multiprocessors in Information Processing Letters, 84(2):93–98.
- Topcuoglu H. , Hariri S. 2002. Performance Effective and Low Complexity Task Scheduling for Heterogenous Computing in IEEE Transactions on Parallel and Distributed Systems, Vol-13 No. 3.
- Anderson J. and Srinivasan A. 2000. Early-release fair scheduling in Proc. of the 12th Euromicro Conference on Real-Time Systems, 35–43.
- Mitchell M. 1995. Genetic Algorithms: An Overview in An Introduction to Genetic Algorithms, Chapter 1. MIT Press.
- Konfrst Z. 2004. Parallel Genetic Algorithms: Advances, Computing Trends, Applications and Perspectives in18th International Parallel and Distributed Processing.
- Baskiyar S. and SaiRanga P. C. 2003. Scheduling Directed A-cyclic Task Graphs on Heterogeneous Network of Workstations to Minimize Schedule Length in Proceedings of the IEEE International Conference on Parallel Processing Workshops (ICPPW?03).
- Blythe J. , Jain S. , Deelman E. , Gil Y. , Vahi K, Mandal A, and Kennedy K. 2005. Task scheduling strategies for workflow based applications in grids in CCGRID, 759-767.
- Gen M, Cheng R. 2000. Genetic algorithm and engineering optimization. NewYork:Wiley.
- ESH, Ansari N, Hong R. 1994. A genetic algorithm for multiprocessor scheduling in IEEE Transactions on Parallel and Distributed Systems; 5(2):113–20.
- Hwang R, Gen M. 2004. Multiprocessor scheduling using genetic algorithm with priority-based coding in Proceedings of IEEJ conference on electronics, information and systems.
- Reakook H. , Mitsuo G. and Hiroshi K. . 2008. A comparison of multiprocessor task scheduling algorithms with communication costs in Computers and Operations Research; 35, 976-993.
- Ilavarasan E. , Thambidurai P. and Mahilmannan. 2005. Performance Effective Task Scheduling Algorithm for Heterogeneous Computing System in proceedings of the 4th International Symposium on Parallel and Distributed Computing.
- Kwok Y. K. and Ahmad I. 1999. Static Scheduling algorithms for allocating directed task graphs to multiprocessors in ACM Comput. Surv. 31(4), 406-471.
- EI-Rewini H. , Lewis T. G. , and Ali H. H. 1994. Task Scheduling in parallel and distributed Systems in Prentice Hall, Englewood Cliffs.
- Topcuoglu H. , Hariri S. and Min-You Wu. 2002. Performance-Effective and Low-Complexity Task Scheduling for Heterogenous Computing in IEEE transactions on Parallel and Distributed Systems, Vol. 13, no. 3.
- Tsujimura Y, Gen M. 1995. Genetic algorithms for solving multiprocessor scheduling problems. In: Simulated evolution and learning. Heidelberg: Springer; 106–15.
- Yang J. XiaochuanMa, Chaohuan Hou and Zheng Yao. 2008. A Static Multiprocessor Scheduling Algorithm for Arbitrary Directed Task Graphs in Uncertain Environments in Springer-Verlag Berlin Heidelberg.
Index Terms
Keywords