International Research journal of Management Science and Technology

  ISSN 2250 - 1959 (online) ISSN 2348 - 9367 (Print) New DOI : 10.32804/IRJMST

Impact Factor* - 6.2311


**Need Help in Content editing, Data Analysis.

Research Gateway

Adv For Editing Content

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

A LABEL SCHEDULING ALGORITHM FOR TASKS ALLOCATION WITH PRECEDENCE RELATION IN MULTIPROCESSOR SYSTEM

    1 Author(s):  JUGMENDRA SINGH

Vol -  7, Issue- 2 ,         Page(s) : 37 - 45  (2016 ) DOI : https://doi.org/10.32804/IRJMST

Abstract

The problem of allocating and scheduling real-time tasks, with precedence constraints on multiprocessor architecture in order to meet the timing constraints is known to be NP complete. Due to the growing complexity of real-time applications there is a need to find scheduling methods that can handle large task sets in reasonable time. Also, scheduling methods should consider precedence and exclusion relations in order to support parallelism within tasks and to resolve mutual exclusion situations. 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.

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, pp. 138-153, 1990.
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),pp. 3-14, 1999.
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, pp. 260-274, Mar. 2002.
15. Hartigan, John A., and Manchek A. Wong. "Algorithm AS 136: A k-means clustering algorithm." Applied statistics (1979): 100-108.
16. 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, pp. 9-14. IEEE, 2001.
17. Robinson, Jacob, and Yahya Rahmat-Samii. "Particle swarm optimization in electromagnetics." Antennas and Propagation, IEEE Transactions on 52, no. 2 (2004): 397-407.
18. 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.
19. 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.
20. 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.
21. Price, W. L. "Global optimization by controlled random search." Journal of Optimization Theory and Applications 40, no. 3 (1983): 333-348.
22. 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