Hybrid Real-Time Task Scheduling Algorithm in Overload Situation for Multiprocessor System

A. Hatami, S. Chuprat, H. Md Sarkan, N. Firdaus Mohd Azmi

Abstract


Real-time systems are reactive systems which should meet major constraints in scheduling tasks like time limitation and resources allocation for scheduling the task effectively when the system in overloaded condition. Failure of system in scheduling tasks when system is overloaded can result in catastrophic impacts. The goal of this research is to propose a task scheduling algorithm that able to perform better than traditional Earliest Deadline First (EDF) and minimize the overall completion time when the system in overloaded condition. The proposed scheduling algorithm is built based on three new improved scheduling algorithms namely: (1) Hybrid Particle Swarm Optimization (PSO) and Hybrid Invasive Weed Optimization (HPIO), (2) Enhanced Initial Swarm (EIS), and (3) Hybrid EDF, EIS and HPIO Optimization (HEDFPIO). The author proves that more successful tasks is scheduled by using HPIO in multiprocessor system in over loaded situation among PSO and ACO. The author uses EIS algorithm in order to improve local search in HPIO and have fair load balance among processors. Finally the author presents a new hybrid algorithm that combines HPIO, EIS and EDF which is called HEDFPIO, It is observed that we could achieve higher successful ratio in task scheduling and with shorter calculation time in overloaded situation.

Keywords


Enhanced Initial Swarm; Hybrid; Invasive Weed Optimization; Particle Swarm Optimization Overload;

Full Text:

PDF

References


M. Karimi and H. Motameni, “Tasks scheduling in computational grid using a hybrid discrete particle swarm optimization,” International Journal of Grid and Distributed Computing, vol. 6, no. 2, pp. 29–38, 2013.

A. R. Mehrabain and C. Lucas, “Novel Numerical optimization algorithm inspired from invasive weed colonization,” Ecological Informatics., vol. 1, no. 4, pp. 355–366, 2006.

A. Shah and K. Kotecha, “ACO based dynamic scheduling algorithm for real-time multiprocessor systems,” Internationa. Journal.of Grid and High Performance Computing., vol. 3, no. 3, pp. 20–30, 2011.

A. Shah, K. Kotecha, and D. Shah, “Dynamic Scheduling for real-time distributed systems using ant colony optimization,” International Journal of Intelligent Computing and Cybernetics., vol. 3, no. 2, pp. 279–292, 2010.

A. Shah and K. Kotecha, “Adaptive scheduling algorithm for real-time multiprocessor systems,” in Proc. IEEE International Conference Advance Computing, Patiala, India, 2009, pp. 6–7.

M. Karimi, “Hybrid discrete particle swarm optimization for task scheduling in grid computing,” International Journal of Grid and Distributed Computing, vol. 7, no. 4, pp. 93–104, 2014.

J. Nandanwar and U. Shrawankar, “An adaptive real time task scheduler,” International Journal of Computer Science Issues, vol. 9, no. 6, pp. 335–340, 2012.

F. Xhafa and A. Abraham, “Nature inspired schedulers in computational grids,” CSI Communications, vol. 34, no. 11, pp. 28–30, 2011.

M. R. Ghalenoei, H. Hajimirsadeghi, and C. Lucas, “Discrete invasive weed optimization algorithm: Application to cooperative multiple task assignment of UAVs,” in Proceedings of the 48th IEEE Conference on Decision and Control,Shanghai, 2009, pp. 1665–1670.

V. E. Balas, L. C. Jain, and B. Kovačević, “Soft computing applications,” in Proceedings of the 6th International Workshop Soft Computing Applications, vol. 1, pp. 338–345, 2015.

K. M. Passino and T. D. Seeley, “Modeling and analysis of nest-site selection by honeybee swarms: The speed and accuracy trade-off,” Behav. Ecol. Sociobiol., vol. 59, pp. 427–442, 2006.

M. Karimi and H. Motameni, “Tasks scheduling in computational grid using a hybrid discrete particle swarm optimization,” International Journal of Grid and Distributed Computing, vol. 6, no. 2, pp. 29–38, 2013.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

ISSN: 2180-1843

eISSN: 2289-8131