Home   >   CSC-OpenAccess Library   >    Manuscript Information
Heuristics Based Genetic Algorithm for Scheduling Static Tasks in Homogeneous Parallel System
Kamaljit Kaur, Amit Chhabra, Gurvinder Singh
Pages - 183 - 198     |    Revised - 30-04-2010     |    Published - 10-06-2010
Volume - 4   Issue - 2    |    Publication Date - May 2010  Table of Contents
MORE INFORMATION
KEYWORDS
DAG, multiprocessor scheduling, genetic algorithm, heuristics
ABSTRACT
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.
CITED BY (37)  
1 Pop, F., Tutueanu, R. I., Barbieru, C., Vasile, M. A., & Kolodziej, J. (2016). Adaptive Resource Allocation in Cloud Computing Based on Agreement Protocols. In Intelligent Agents in Data-intensive Computing (pp. 193-213). Springer International Publishing.
2 Kalra, M., & Singh, S. (2015). A review of metaheuristic scheduling techniques in cloud computing. Egyptian Informatics Journal, 16(3), 275-295.
3 Pop, F., Dobre, C., Cristea, V., Bessis, N., Xhafa, F., & Barolli, L. (2015). Reputation-guided evolutionary scheduling algorithm for independent tasks in inter-clouds environments. International Journal of Web and Grid Services, 11(1), 4-20.
4 Neves, D., Lourenco, N., & Horta, N. (2015, September). Scheduling evaluation tasks for increased efficiency of parallel analog IC synthesis. In Synthesis, Modeling, Analysis and Simulation Methods and Applications to Circuit Design (SMACD), 2015 International Conference on (pp. 1-4). IEEE.
5 Mao, Y., Zhong, H., & Li, X. (2015, August). Hierarchical model-based associate tasks scheduling with the deadline constraints in the cloud. In Information and Automation, 2015 IEEE International Conference on (pp. 268-273). IEEE.
6 Aujla, S., & Ummat, A. Task scheduling in Cloud Using Hybrid Cuckoo Algorithm. International Journal of Computer Networks and Applications (IJCNA), 2(3), 144-150.
7 Vasile, M. A., Pop, F., Tutueanu, R. I., Cristea, V., & Kolodziej, J. (2014). Resource-aware hybrid scheduling algorithm in heterogeneous distributed computing. Future Generation Computer Systems.
8 Singh, S., & Kalra, M. (2014, November). Scheduling of Independent Tasks in Cloud Computing Using Modified Genetic Algorithm. In Computational Intelligence and Communication Networks (CICN), 2014 International Conference on (pp. 565-569). IEEE.
9 Sharma, A., Singh, N., Hans, A., & Kumar, K. (2014, November). Review of task scheduling algorithms using genetic approach. In Computational Intelligence on Power, Energy and Controls with their impact on Humanity (CIPECH), 2014 Innovative Applications of (pp. 169-172). IEEE.
10 Kara, N., Soualhia, M., Belqasmi, F., Azar, C., & Glitho, R. (2014). Genetic-based algorithms for resource management in virtualized IVR applications. Journal of Cloud Computing, 3(1), 1-18.
11 YUSUF, A. B. (2014). application of genetic algorithm in modeling university admission decision support system (doctoral dissertation).
12 Patel, P. S. (2014). Multi-Objective Job Scheduler using Genetic Algorithm in Grid Computing. International Journal of Computer Applications, 92(14).
13 Kang, Y., Zhang, Y., Lin, Y., & Lu, H. (2014). An Improved Ant Colony System for Task Scheduling Problem in Heterogeneous Distributed System. In Computer Engineering and Networking (pp. 83-90). Springer International Publishing.
14 Pan Yang, Qiu Jianlin, Yang Na, Biancai Feng, & Lu Pengcheng. (2014). Multiprocessor task scheduling algorithm based on tabu search. Computer Engineering and Design, 35 (12), 4186-4190.
15 Sivasankar, S., Jeyapaul, R., & Kunhahamed, P. K. (2013). Performance study of tool materials and optimisation of pulse duration on EDM of zirconium di boride. International Journal of Machining and Machinability of Materials, 14(2), 123-141.
16 Na'mneh, A., & Darabkh, K. (2013, November). A new genetic-based algorithm for scheduling static tasks in homogeneous parallel systems. In Robotics, Biomimetics, and Intelligent Computational Systems (ROBIONETICS), 2013 IEEE International Conference on (pp. 46-50). IEEE.
17 Kaur, A., & Singh, B. (2013). Enhancement of Power Aware Job Scheduling with Minimum Completion Time Algorithm. International Journal of Engineering Science and Technology, 5(7), 1465.
18 Geetha, T., Mahalakshmi, K., Ummusalma, I., & Kumaran, K. M. (2013). An Observational Analysis of Genetic Operators. International Journal of Computer Applications, 63(18), 24-34.
19 Vasile, M. A., Pop, F., Tutueanu, R. I., & Cristea, V. (2013). HySARC2: Hybrid Scheduling Algorithm Based on Resource Clustering in Cloud Environments. In Algorithms and Architectures for Parallel Processing (pp. 416-425). Springer International Publishing.
20 Awadall, M., Ahmad, A., & Al-Busaidi, S. (2013). Min–min GA Based Task Scheduling In Multiprocessor Systems. International Journal of Soft Computing and Engineering (IJSCE). ISSN, 2231-2307.
21 Kaur, P., & Kaur, A. Implementation of Dynamic Level Scheduling Algorithm using Genetic Operators. International Journal of Application or Innovation in Engineering & Management (IJAIEM) Volume, 2.
22 Tutueanu, R. I., Pop, F., Vasile, M. A., & Cristea, V. (2013). Scheduling Algorithm Based on Agreement Protocol for Cloud Systems. In Algorithms and Architectures for Parallel Processing (pp. 94-101). Springer International Publishing.
23 Kaur, A., & Kaur, P. (2013). Implementation of Mapping Heuristic Genetic Algorithm. International Journal of Advanced Research in Computer and Communication Engineering, 3224-3229.
24 Kamal, S., & Singh, B. H. (2013). Scheduling Of Parallel Constrained Task Graphs On Multiprocessor Systems. American International Journal of Research in Science, Technology, Engineering and Mathematics, 153-158.
25 Khan, F. N., & Govil, K. (2013). Distributed Task Allocation Scheme for Performance Improvement in Mobile Computing Network. International Journal of Trends in Computer Science, 2(3), 809-817.
26 Mocanu, E. M., Florea, M., Andreica, M. I., & Tapus, N. (2012, March). Cloud computing—task scheduling based on genetic algorithms. In Systems Conference (SysCon), 2012 IEEE International (pp. 1-6). IEEE.
27 Plateau, Gu Xing, Yang Juan, & Ke Yang Ho. (2012). Heterogeneous systems improved genetic scheduling algorithm. Computer Engineering, 38 (19), 142-146.
28 Strickland, S., & Sanders, T. A Genetic Algorithm for Task Scheduling.
29 Remmersmann, T., Schade, U., & Schlick, C. (2012, October). Supervisory control of multi-robot systems by disaggregation and scheduling of quasi-natural language commands. In Systems, Man, and Cybernetics (SMC), 2012 IEEE International Conference on (pp. 315-320). IEEE.
30 Gao, Y., Gu, X., Yang, Q., & Ke, H. Y. (2012). Improved Genetic Scheduling Algorithm in Heterogeneous System. Jisuanji Gongcheng/ Computer Engineering, 38(19).
31 Singh, S. N., Thakur, A. K., & Kumar, N. (2012). International Journal of Emerging Technologies in Computational and Applied Sciences (IJETCAS) www. iasir. net. development, 13, 19.
32 Delavar, A. G., Boroujeni, A. R. K., & Bayrampoor, J. (2012). A Balanced Scheduling Algorithm with Fault Tolerant and Task Migration based on Primary Static Mapping (PSM) in Grid. International Journal of Computer Applications, 52(8).
33 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.
34 Chen, Y., Jaekel, A., & Bari, A. (2011). A new model for allocating resources to scheduled lightpath demands. Computer Networks, 55(13), 2821-2837.
35 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.
36 Sukoco, H., & Okamura, K. (2010, March). Genetic Algorithm for Optimizing and Arrangement of Queue in Virtual Networks. In World Congress on Engineering 2012. July 4-6, 2012. London, UK. (Vol. 2188, pp. 670-675). International Association of Engineers.
37 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 Google Scholar 
2 Academic Journals Database 
3 ScientificCommons 
4 Academic Index 
5 CiteSeerX 
6 refSeek 
7 iSEEK 
8 Socol@r  
9 ResearchGATE 
10 Libsearch 
11 Bielefeld Academic Search Engine (BASE) 
12 Scribd 
13 WorldCat 
14 SlideShare 
15 PDFCAST 
16 PdfSR 
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.
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.
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.
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.
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.
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.
D. E. Goldberg, “Genetic algorithms in search, optimization & machine learning”, Addison Wesley, 1990.
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.
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.
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.
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.
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).
Marin Golub, Suad Kasapovic, “Scheduling Multiprocessor Tasks with Genetic Algorithms”, OACTA Press, from proceeding (351) Applied Informatics, 2002.
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.
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.
Melanie Mitchell, “An Introduction to Genetic algorithms”, The MIT Press, February 1998.
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.
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.
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.
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
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.
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.
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.
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.
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.
Mr. Kamaljit Kaur
- India
kamal.aujla86@gmail.com
Mr. Amit Chhabra
- India
Mr. Gurvinder Singh
- India


CREATE AUTHOR ACCOUNT
 
LAUNCH YOUR SPECIAL ISSUE
View all special issues >>
 
PUBLICATION VIDEOS