Notification: Our email services are now fully restored after a brief, temporary outage caused by a denial-of-service (DoS) attack. If you sent an email on Dec 6 and haven't received a response, please resend your email.
CFP last date
20 December 2024
Reseach Article

Task Scheduling and Idle-Time Balancing in Homogeneous Multi Processors: A Comparison between GA and SA

by Mohammad Amin Pishdar, Abbas Akkasi
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 123 - Number 13
Year of Publication: 2015
Authors: Mohammad Amin Pishdar, Abbas Akkasi
10.5120/ijca2015905656

Mohammad Amin Pishdar, Abbas Akkasi . Task Scheduling and Idle-Time Balancing in Homogeneous Multi Processors: A Comparison between GA and SA. International Journal of Computer Applications. 123, 13 ( August 2015), 39-45. DOI=10.5120/ijca2015905656

@article{ 10.5120/ijca2015905656,
author = { Mohammad Amin Pishdar, Abbas Akkasi },
title = { Task Scheduling and Idle-Time Balancing in Homogeneous Multi Processors: A Comparison between GA and SA },
journal = { International Journal of Computer Applications },
issue_date = { August 2015 },
volume = { 123 },
number = { 13 },
month = { August },
year = { 2015 },
issn = { 0975-8887 },
pages = { 39-45 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume123/number13/22021-2015905656/ },
doi = { 10.5120/ijca2015905656 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T23:12:38.791701+05:30
%A Mohammad Amin Pishdar
%A Abbas Akkasi
%T Task Scheduling and Idle-Time Balancing in Homogeneous Multi Processors: A Comparison between GA and SA
%J International Journal of Computer Applications
%@ 0975-8887
%V 123
%N 13
%P 39-45
%D 2015
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Task scheduling problem has a special significance in multiprocessors due to efficient use of the processor and also spending less time. Tasks should be assigned to processors in such a way to minimizing makespan. In this paper, we use genetic algorithm and simulated annealing to solve task scheduling problem on multi homogenous processors with minimizing completion time. In addition we introduce another fitness function as processors idle-time balancing which should be less than a predetermined value. These algorithms are used to determine suitable priorities that lead to a sub-optimal solution. And finally to compare the performance of these algorithms, we design 9 test problem based on two fitness function.

References
  1. Dahal, K. and Hossain, A. and Varghese, B. and Abraham, A. and Xhafa, F. and Daradoumis, A. (2008). Scheduling in Multiprocessor System Using Genetic Algorithms. 7th Computer Information Systems and Industrial Management Applications.
  2. Miryani, M. R. and Naghibzadeh, M. “Hard Real-Time Multiobjective Scheduling in Heterogeneous Systems Using Genetic Algorithms,” Proceedings of the 14th International CSI Computer Conference (CSICC'09)., 2009, pp. 437-445.
  3. Turner, H. and White, J. (2013). Multi-core Deployment Optimization Using Simulated Annealing and Ant Colony Optimization. 12th IEEE International Conference on Trust, Security and Privacy in Computing and Communications.
  4. Houshmand, M. and Soleymanpour, E. and Salami, H. and Amerian, M. and Deldari, H. (2010). Efficient Scheduling of Task Graphs to Multiprocessors Using A Combination of Modified Simulated Annealing and List based Scheduling. Third International Symposium on Intelligent Information Technology and Security Informatics.
  5. Gupta, S. and Agarwal, G. and Kumar, V. (2010). Task Scheduling in Multiprocessor System Using Genetic Algorithm. Second International Conference on Machine Learning and Computing.
  6. Omara, F. A. and Arafa, M. M. (2010.). Genetic algorithms for task scheduling problem. J. Parallel Distrib. Comput. 70, pp. 13-22. Available: www.elsevier.com/locate/jpdc
  7. Wen, Y. and Xu, H. and Yang, J. (2011.). A heuristic-based hybrid genetic-variable neighborhood search algorithm for task scheduling in heterogeneous multiprocessor system. Information Sciences. 181, pp. 567-581. Available: www.elsevier.com/locate/ins
  8. Wu, A. S. and Yu, H. and Jin, S. and Lin, K. and Schiavone, G. (2004, Sep.). An Incremental Genetic Algorithm Approach to Multiprocessor Scheduling. IEEE Transactions on Parallel and Distributed Systems. 15(9), pp. 824-834.
  9. Roy, P. and Alam, M. M. and Das, N. (2012, July.). Heuristic Based Task Scheduling In Multiprocessor Systems With Genetic Algorithm By Choosing The Eligible Processor. International Journal of Distributed and Parallel Systems (IJDPS). 3(4), pp. 111-121.
  10. Thanushkodi, K. and Deeba, K. (2011, May.). On Performance Comparisons of GA, PSO and proposed Improved PSO for Job Scheduling in Multiprocessor Architecture. International Journal of Computer Science and Network Security (IJCSNS). 11(5), pp. 27-34.
  11. Kaur, R. and Singh, G. 2012. Genetic Algorithm Solution for Scheduling Jobs in Multiprocessor Environment. India Conference (INDICON).
  12. http://cs.nyu.edu/courses/fall12/CSCI-GA.2965-001/geneticalg.
Index Terms

Computer Science
Information Sciences

Keywords

Genetic algorithm multiprocessor task scheduling parallel processing simulated annealing.