| |
| |
|
|
|
|
| Heuristics Based Genetic Algorithm for Scheduling Static Tasks in Homogeneous Parallel System
|
|
Full
text: |
 PDF(271.9KB) |
|
|
Source |
International Journal of Computer Science and Security (IJCSS) |
|
Table of Contents |
|
|
Download
Complete Issue PDF(4.92MB) |
|
Volume: 4 Issue: 2 |
| |
Pages: 149-264 |
|
Publication
Date: May 2010 |
|
ISSN
(Online): 1985-1553 |
|
|
|
|
|
Pages |
183 - 198 |
|
Author(s) |
|
|
|
Published
Date |
10-06-2010 |
|
Publisher |
CSC
Journals, Kuala Lumpur,
Malaysia |
|
ADDITIONAL
INFORMATION |
| Keywords Abstract References Cited by Related Articles Collaborative
Colleague |
| |
|
| |
KEYWORDS: DAG, multiprocessor scheduling, genetic algorithm, heuristics |
|
|
| |
|
|
| This Manuscript is indexed in the following databases/websites:- |
|
| 1. Directory of Open Access Journals (DOAJ) |
| 2. PDFCAST |
| 3. Scribd |
| 4. Docstoc |
| 5. WorldCat |
| 6. ScientificCommons |
| 7. CiteSeerX |
| 8. Google Scholar |
| 9. Bielefeld Academic Search Engine (BASE) |
| 10. ResearchGATE |
| 11. Academic Index |
| 12. refSeek |
| 13. Socol@r |
| 14. iSEEK |
| 15. Academic Journals Database |
| 16. Libsearch |
| 17. slideshare |
| |
|
| |
|
|
| In the multiprocessor scheduling problem, a given program, represented by a directed acyclic graph (DAG), is to be scheduled in such a way that the program's execution time should be minimized. This problem is being very hard to solve exactly. The scheduling problem is still known to be NP-complete in general, even when the target processors are fully connected and no communication delay is considered among task. Many heuristic methods for finding a suboptimal schedule exist. Performance of genetic algorithm can be improved with the introduction of some knowledge about the scheduling problem represented by the use of heuristics. In this paper the problem of same execution time or completion time and same precedence in the homogeneous parallel system is resolved by using concept of Bottom-level (b-level) or Top-level (t-level). This combined approach named as heuristics based genetic algorithm (HGA) based on MET (Minimum execution time)Min-Min heuristics and b-level or t-level precedence resolution and is compared with a pure genetic algorithm, min-min heuristic, MET heuristic and First Come First Serve (FCFS) approach. Results of the experiments show that the heuristics based genetic algorithm produces much better results in terms of quality of solutions. |
| |
|
| |
|
| |
| 1 |
Ishfaq Ahmad, Yu-Kwong Kwok, Min-You Wu, “Analysis, Evaluation, and Comparison of Algorithms for Scheduling Task Graphs on Parallel Processors”, Proceedings of the 1996 International Symposium on Parallel Architectures, Algorithms and Networks, Page: 207, 1996, ISBN: 0-8186-7460-1, IEEE Computer Society Washington, DC, USA.
|
|
|
| 2 |
Yu-Kwong Kwok and Ishfaq Ahmad, “Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors”, ACM Computing Surveys, vol. 31, Issue. 4, December 1999, ISSN: 0360-0300, ACM New York, NY, USA.
|
|
|
| 3 |
D. E. Goldberg, “Genetic algorithms in search, optimization & machine learning”, Addison Wesley, 1990.
|
|
|
| 4 |
Melanie Mitchell, “An Introduction to Genetic algorithms”, The MIT Press, February 1998.
|
|
|
| 5 |
Tracy D. Braunt, Howard Jay Siegel, Noah Beck, Bin Yao, Richard F. Freund, “A Comparison Study of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems”, Journal of Parallel and Distributed Computing, Volume 61, Issue 6, June 2001, Pages: 810-837, ISSN: 0743-7315, Academic Press, Inc. Orlando, FL, USA.
|
|
|
| 6 |
Ricardo C. Correa, Afonso Ferreira, Pascal Rebreyend, “Scheduling Multiprocessor Tasks With Genetic Algorithms”, IEEE Transactions on Parallel and Distributed Systems, Vol. 10, Issue. 8, August 1999, Pages: 825-837, ISSN: 1045-9219, IEEE Press Piscataway, NJ, USA.
|
|
|
| 7 |
Edwin S. H. Hou, Nirwan Ansari, Hong Ren, “A Genetic Algorithm for Multiprocessor Scheduling”, IEEE Transactions on Parallel and Distributed Systems, vol. 5, Issue. 2, February2003, Pages: 113-120, ISSN: 1045-9219, IEEE Press Piscataway, NJ, USA.
|
|
|
| 8 |
Amir Masoud Rahmani, Mohammad Ali Vahedi, “A novel Task Scheduling in Multiprocessor Systems with Genetic Algorithm by using Elitism stepping method”, Science and Research branch, Tehran, Iran, May 26, 2008.
|
|
|
| 9 |
Martin Grajcar, “Genetic List Scheduling Algorithm for Scheduling and Allocating on a Loosely Coupled Heterogeneous Multiprocessor System”, Proceedings of the 36th annual ACM/IEEE Design Automation Conference, New Orleans, Louisiana, United States, Pages: 280 – 285, 1999, ISBN: 1-58133-109-7, ACM New York, NY, USA.
|
|
|
| 10 |
Martin Grajcar, “Strengths and Weaknesses of Genetic List Scheduling for Heterogeneous Systems”, IEEE Computer Society, Proceedings of the Second International Conference on Application of Concurrency to System Design, Page: 123, ISBN: 0-7695-1071-X, IEEE Computer Society Washington, DC, USA, 2001.
|
|
|
| 11 |
Hesam Izakian, Ajith Abraham, Vaclav Snasel, “Comparison of Heuristics for scheduling Independent Tasks on Heterogeneous Distributed Environments”, Proceedings of the 2009 International Joint Conference on Computational Sciences and Optimization, Volume 01, Pages: 8-12, 2009, ISBN:978-0-7695-3605-7, IEEE Computer Society Washington, DC, USA.
|
|
|
| 12 |
Yi-Hsuan Lee and Cheng Chen, “A Modified Genetic Algorithm for Task Scheduling in Multiprocessor Systems”, Proc. of 6th International Conference Systems and Applications, pp. 382-387, 1999.
|
|
|
| 13 |
Amir Masoud Rahmani and Mojtaba Rezvani, “A Novel Genetic Algorithm for Static Task Scheduling in Distributed Systems”, International Journal of Computer Theory and Engineering, Vol. 1, No. 1, April 2009, 1793-8201.
|
|
|
| 14 |
Michael Rinehart, Vida Kianzad and Shuvra S. Bhattacharyya, “A modular Genetic Algorithm for Scheduling Task Graphs”, Technical Report UMIACS-TR-2003-66, Institute for Advanced Computer Studies University of Maryland at College Park, June 2003.
|
|
|
| 15 |
Pai-Chou Wang, W. Korfhage, “Process Scheduling with Genetic Algorithms”, Proceedings of the 7th IEEE Symposium on Parallel and Distributed Processing, Page: 638, ISBN: 0-8186-7195-5, October 2005, IEEE Computer Society Washington, DC, USA.
|
|
|
| 16 |
Prof. Sanjay R Sutar, Jyoti P. Sawant, Jyoti R. Jadhav, “Task Scheduling For Multiprocessor Systems Using Memetic Algorithms”, http://www.comp.brad.ac.uk/het-net/tutorials/P27.pdf
|
|
|
| 17 |
Andrew J. Page and Thomas J. Naughton, “Framework for Task scheduling in heterogeneous distributed computing using genetic algorithms”, 15th Artificial Intelligence and Cognitive Science Conference, 2004, Castlebar, Co. Mayo, Ireland, isbn = 1-902277-89-9 pages = 137-146.
|
|
|
| 18 |
Clayton S. Ferner and Robert G. Babb, “Automatic Choice of Scheduling Heuristics for Parallel/Distributed Computing”, IOS Press Amsterdam, The Netherlands, Volume 7, Issue 1, Pages: 47 – 65, January 1999, ISSN:1058-9244.
|
|
|
| 19 |
C.L. McCreary, A.A. Khan, J. Thompson, M.E. McArdle, “A Comparison of Heuristics for Scheduling DAGs on Multiprocessors”, Eighth International Proceedings on Parallel Processing Symposium, pages: 446-451, Location: Cancun, ISBN: 0-8186-5602-6, DOI: 10.1109/IPPS.2002.288264, 06 August 2002.
|
|
|
| 20 |
Javier Carretero, Fatos Xhafa, Ajith Abraham, “Genetic Algorithm Based Schedulers for Grid Computing Systems”, International Journal of Innovative Computing, Information and Control, ICIC International, Vol.3, No. 6, ISSN 1349-4198, pp. 1053-1071, December 2007.
|
|
|
| 21 |
Annie s. Wu, Han Yu, Shiyuan Jin, Kuo-Chi Lin, and Guy Schiavone, “An Incremental Genetic Algorithm Approach to Multiprocessor Scheduling”, IEEE Transactions on Parallel and Distributed Systems, Vol.15, No. 9, On page(s): 824 – 834, ISSN: 1045-9219, INSPEC Accession Number:8094176, Digital Object Identifier: 10.1109/TPDS.2004.38, 13 September 2004.
|
|
|
| 22 |
Michael Bohler, Frank Moore, Yi Pan, “Improved Multiprocessor Task Scheduling Using Genetic Algorithms”, Proceedings of the Twelfth International FLAIRS Conference, WPAFB, OH 45433, American Association for Artificial Intelligence, 1999.
|
|
|
| 23 |
Marin Golub, Suad Kasapovic, “Scheduling Multiprocessor Tasks with Genetic Algorithms”, OACTA Press, from proceeding (351) Applied Informatics, 2002.
|
|
|
| 24 |
M. Nikravan and M. H. Kashani, “A Genetic Algorithm for Process Scheduling in Distributed Operating Systems considering Load Balancing”, Proceedings 21st European Conference on Modelling and Simulation Ivan Zelinka, Zuzana Oplatkova, Alessandra Orsoni, ECMS 2007, ISBN 978-0-9553018-2-7, ISBN 978-0-9553018-3-4 (CD).
|
|
|
| 25 |
Shuang E Zhou, Yong Liu, Di Jiang, “A Genetic-Annealing Algorithm for Task Scheduling Based on Precedence Task Duplication”, CIT, Proceedings of the Sixth IEEE International Conference on Computer and Information Technology, Page: 117, 2006, ISBN: 0-7695-2687-X, IEEE Computer Society Washington, DC, USA.
|
|
|
| |
|
| |
|
| |
| 1 |
H. Sukoco and K. Okamura, “Grouping Packet Scheduling for Virtual Networks by Genetic Algorithm”, inProceedings of the 6th International Conference on Future Internet Technologies ACM New York, USA, 2011.
|
|
|
| 2 |
M. R. Mohamed and M. H. A. Awadalla, “Hybrid Algorithm for Multiprocessor Task Scheduling”, International Journal of Computer Science Issues, 8(3), pp. 79-89, May 2011.
|
|
|
| 3 |
Prof. M. Abo-Zahhad , S. M. Ahmed , N. Sabor and A. F. Al-Ajloun, “The Convergence Speed of Single- And Multi-Objective Immune Algorithm Based Optimization Problems”, Signal Processing: An International Journal (SPIJ) , 4(5), pp. 247 – 266, 2010.
|
|
|
| |
|
| |
|
| |
| 1 |
shendusou.com
|
| 2 |
lw20
|
| |
|
| |
|
| |
|
| Kamaljit Kaur : Colleagues
|
|
| Amit Chhabra : Colleagues
|
|
| Gurvinder Singh : Colleagues
|
|
|
|
|
|
|
|
|
|
|
