INTERNATIONAL RESEARCH JOURNAL OF SCIENCE ENGINEERING AND TECHNOLOGY

( Online- ISSN 2454 -3195 ) New DOI : 10.32804/RJSET

Impact Factor* - 6.2311


**Need Help in Content editing, Data Analysis.

Research Gateway

Adv For Editing Content

   No of Download : 102    Submit Your Rating     Cite This   Download        Certificate

A CLUSTERING ALGORITHM FOR TASKS ALLOCATION ON DAG

    1 Author(s):  JUGMENDRA SINGH

Vol -  6, Issue- 1 ,         Page(s) : 44 - 53  (2016 ) DOI : https://doi.org/10.32804/RJSET

Abstract

The need for a scheduling algorithm arises from the requirement for most modern systems to perform multitasking. A multiprocessor system can be homogeneous (i.e. having all processors of same capability) or heterogeneous (i.e. having processors of different capabilities) nature. In literature several algorithms are proposed to find optimal solution of multiprocessor task scheduling algorithms. Here we present an optimal non preemptive scheduling algorithm involving arbitrary precedence relations among tasks represented in the form of a DAG. We have shown here that a two phase algorithm is better than a single phase algorithm and also that our algorithm is better than the contemporary optimal algorithms in case of a two processor system and has polynomial time complexity.

  1. Xu, Yuming, Kenli Li, Jingtong Hu, and Keqin Li. "A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues." Information Sciences 270 (2014): 255-287.
  2. Panwar, Poonam, A. K. Lal, and Jugmendra Singh. "A Genetic Algorithm Based Technique for Efficient Scheduling of Tasks on Multiprocessor System." In Proceedings of the International Conference on Soft Computing for Problem Solving (SocProS 2011) December 20-22, 2011, pp. 911-919. Springer India, 2012.
  3. Ramamrithan K., “ Allocation and scheduling of precedence related periodic tasks”, IEEE transaction on parallel and distributed systems, vol 6, no 4, pp412-420, Apr. 1995.
  4. Ronngren S., B.A. Shirazi, “ Static multiprocessor scheduling of periodic real-time tasks          with    precedence constraints and communication costs”, in proceedings of 28th Hawai International Conference on system sciences (HICSS’95), Hawaii, USA, Jan 04-07, 1995.
  5. Wang Q., and K.H. Cheng, “A heuristic of scheduling parallel tasks and its analysis,”  SIAM J.Computing, vol. 21, no-2, pp. 281-294, Apr. 1992.
  6. Dhingra, Sunita, Satinder Bal Gupta, and Ranjit Biswas. "Comparative analysis of heuristics for multiprocessor task scheduling problem with homogeneous processors." Advances in Applied Science Research 5, no. 3 (2014): 280-285.
  7. Kaur, Kamaljit, Amit Chhabra, and Gurvinder Singh. "Modified genetic algorithm for task scheduling in homogeneous parallel system using heuristics."International Journal of Soft Computing 5, no. 2 (2010): 42-51.
  8. Topcuoglu, Haluk, Salim Hariri, and Min-you Wu. "Performance-effective and low-complexity task scheduling for heterogeneous computing." Parallel and Distributed Systems, IEEE Transactions on 13, no. 3 (2002): 260-274.
  9. Arabnejad, Hamid, and Jorge G. Barbosa. "List scheduling algorithm for heterogeneous systems by an optimistic cost table." Parallel and Distributed Systems, IEEE Transactions on 25, no. 3 (2014): 682-694.
  10. Goh, Chi Keong, Eu Jin Teoh, and K. C. Tan. "A hybrid evolutionary approach for heterogeneous multiprocessor scheduling." Soft Computing 13, no. 8-9 (2009): 833-846.
  11. H. El-Rewini and T.G. Lewis, “Scheduling Parallel Program Tasks onto Arbitrary Target Machines,” J. Parallel and Distributed Computing,vol. 9, no. 2, (1990) : 138-153.
  12. Mtibaa, Abdellatif, Bouraoui Ouni, and Mohamed Abid. "An efficient list scheduling algorithm for time placement problem." Computers & Electrical Engineering 33, no. 4 (2007): 285-298.
  13. H. Topcuoglu, S. Hariri, and M. Wu, “Task Scheduling Algorithms for Heterogeneous Processors,”Proc. Eighth Heterogeneous Computing Workshop (HCW), (1999): 3-14.
  14. H. Topcuoglu, S. Hariri, and M. Wu, “Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing,” IEEE Trans. Parallel and Distributed Systems, vol. 13, no. 3, 2002: 260-274.
  15. Park, Chan-Ik, and Tae-Young Choe. "An optimal scheduling algorithm based on task duplication." In Parallel and Distributed Systems, 2001. ICPADS 2001. Proceedings. Eighth International Conference on IEEE, (2001):9-14.
  16. Robinson, Jacob, and Yahya Rahmat-Samii. "Particle swarm optimization in electromagnetics." Antennas and Propagation, IEEE Transactions on 52, no. 2 (2004): 397-407.
  17. Sim, Kwang Mong, and Weng Hong Sun. "Ant colony optimization for routing and load-balancing: survey and new directions." Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on 33, no. 5 (2003): 560-572.
  18. Rolland, Erik, David A. Schilling, and John R. Current. "An efficient tabu search procedure for the p-median problem." European Journal of Operational Research 96, no. 2 (1997): 329-342.
  19. Romero, R., R. A. Gallego, and A. Monticelli. "Transmission system expansion planning by simulated annealing." Power Systems, IEEE Transactions on 11, no. 1 (1996): 364-369.
  20. Price, W. L. "Global optimization by controlled random search." Journal of Optimization Theory and Applications 40, no. 3 (1983): 333-348.
  21. J.C.Liou and M.A.Palis, "An efficient clustering heuristics for scheduling DAGs on multiprocessor system" in proceedings of 8th symposium on parallel and distributed processing, New Orleans, Louisiana, Oct., 1996.
  22. A.Gerasoulis and T.Yang, “On the granularity and clustering of directed acyclic graphs” IEEE transaction on parallel and distributed systems, vol. 4, no.6, (1993) : 322-328.
  23. M.Y.Wu and W Shu, "Efficient local search for DAG scheduling", transactions on parallel and distributed systems, (2001): 617-627.
  24. A.Gerasoulis and T.Yang, "A comparison of clustering heuristics for scheduling DAG on multiprocessors", journal of parallel and distributed computing, vol. 16, (1995):276-291,.
  25. Q.Wang, and K.H. Cheng, “A heuristic of scheduling parallel tasks and its analysis,”, SIAM J. Computing, vol. 21, no-2, (1992) : 281-294,  .
  26. Sivanandam, S. N., and S. N. Deepa. Introduction to genetic algorithms. Springer Science & Business Media, 2007.

*Contents are provided by Authors of articles. Please contact us if you having any query.






Bank Details