CLC number: TP301.6
On-line Access: 2014-06-06
Received: 2013-08-01
Revision Accepted: 2014-01-17
Crosschecked: 2014-04-11
Cited: 1
Clicked: 9610
Hamid Tabatabaee, Mohammad Reza Akbarzadeh-T, Naser Pariz. Dynamic task scheduling modeling in unstructured heterogeneous multiprocessor systems[J]. Journal of Zhejiang University Science C, 2014, 15(6): 423-434.
@article{title="Dynamic task scheduling modeling in unstructured heterogeneous multiprocessor systems",
author="Hamid Tabatabaee, Mohammad Reza Akbarzadeh-T, Naser Pariz",
journal="Journal of Zhejiang University Science C",
volume="15",
number="6",
pages="423-434",
year="2014",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.C1300204"
}
%0 Journal Article
%T Dynamic task scheduling modeling in unstructured heterogeneous multiprocessor systems
%A Hamid Tabatabaee
%A Mohammad Reza Akbarzadeh-T
%A Naser Pariz
%J Journal of Zhejiang University SCIENCE C
%V 15
%N 6
%P 423-434
%@ 1869-1951
%D 2014
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.C1300204
TY - JOUR
T1 - Dynamic task scheduling modeling in unstructured heterogeneous multiprocessor systems
A1 - Hamid Tabatabaee
A1 - Mohammad Reza Akbarzadeh-T
A1 - Naser Pariz
J0 - Journal of Zhejiang University Science C
VL - 15
IS - 6
SP - 423
EP - 434
%@ 1869-1951
Y1 - 2014
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.C1300204
Abstract: An algorithm is proposed for scheduling dependent tasks in time-varying heterogeneous multiprocessor systems, in which computational power and links between processors are allowed to change over time. Link contention is considered in the multiprocessor scheduling problem. A linear switching-state space-modeling paradigm is introduced to enable theoretical analysis from a system engineering perspective. Theoretical analysis of this model shows its robustness against changes in processing power and link failure. The proposed algorithm uses a fuzzy decision-making procedure to handle changes in the multiprocessor system. The efficiency of the proposed algorithm is illustrated by several random experiments and comparison against a recent benchmark approach. The results show up to 18% average improvement in makespan, especially for larger scale systems.
[1]Abraham, A., Grosan, C., Liu, H., et al., 2008. Nature inspired meta-heuristics for grid scheduling: single and multi-objective optimization approaches. In: Xhafa, F., Abraham, A. (Eds.), Metaheuristisc for Scheduling in Distributed Computing Environments, 146(3):247-272.
[2]Al-Sharaeh, S., Wells, B.E., 1996. A Comparison of heuristics for list schedules using the Box-method and P-method for random digraph generation. Proc. 28th Southeastern Symp. on System Theory, p.467-471.
[3]Cheng, S.C., Shiau, D.F., Huang, Y.M., et al., 2009. Dynamic hard-real-time scheduling using genetic algorithm for multiprocessor task with resource and timing constraints. Expert Syst. Appl., 36(1):852-860.
[4]Crăciun, C., Zaharie, D., Zamfirache, F., 2010. Evolutionary task scheduling in static and dynamic environments. Proc. IEEE Int. Joint Conf. on Computational Cybernetics and Technical Informatics, p.619-624.
[5]Daoud, M.I., Kharma, N., 2008. A high performance algorithm for static task scheduling in heterogeneous distributed computing systems. J. Parall. Distr. Comput., 68(4):399-409.
[6]Kong, X., Sun, J., Xu, W., 2008. Permutation-based particle swarm algorithm for tasks scheduling in heterogeneous systems with communication delays. Int. J. Comput. Intell. Res., 4(1):61-70.
[7]Kwok, Y.K., Ahmad, I., 1996. Dynamic critical-path scheduling: an effective technique for allocating task graphs to multiprocessors. IEEE Trans. Parall. Distr. Syst., 7(5):506-521.
[8]Long, Q.Q., Lin, J., Sun, Z.X., 2011. Agent scheduling model for adaptive dynamic load balancing in agent-based distributed simulations. Simul. Modell. Pract. Theory, 19(4):1021-1034.
[9]Page, A.J., Naughton, T.J., 2005. Dynamic task scheduling using genetic algorithms for heterogeneous distributed computing. Proc. 19th IEEE Int. Parallel and Distributed Processing Symp., p.152-159.
[10]Page, A.J., Keane, T.M., Naughton, T.J., 2008. Scheduling in a dynamic heterogeneous distributed system using estimation error. J. Parall. Distr. Comput., 68(11):1452-1462.
[11]Page, A.J., Keane, T.M., Naughton, T.J., et al., 2010. Multi-heuristic dynamic task allocation using genetic algorithms in a heterogeneous distributed system. J. Parall. Distr. Comput., 70(7):758-766.
[12]Prodan, R., Fahringer, T., 2005. Dynamic scheduling of scientific workflow applications on the grid: a case study. Proc. 20th ACM Symp. on Applied Computing, p.687-694.
[13]Shahul, A.Z.S., Sinnen, O., 2010. Scheduling task graphs optimally with A*. J. Supercomput., 51(1):310-332.
[14]Shin, K., Cha, M., Jang, M., et al., 2008. Task scheduling algorithm using minimized duplications in homogeneous systems. J. Parall. Distr. Comput., 68(8):1146-1156.
[15]Sinnen, O., 2007. Task scheduling for parallel systems (1st Ed.). John Wiley & Sons-Interscience.
[16]Sinnen, O., Sousa, L.A., Sandnes, F.E., 2006. Toward a realistic task scheduling model. IEEE Trans. Parall. Distr. Syst., 17(3):263-275.
[17]Sivanandam, S.N., Visalakshi, P., 2009. Dynamic task scheduling with load balancing using hybrid particle swarm optimization. Int. J. Open Probl. Comput. Math., 2(3):475-488.
[18]Tabatabaee-Yazdi, H., Akbarzadeh-T, M.R., 2013. The linear switching state space: a new modeling paradigm for task scheduling problems. Int. J. Innov. Comput. Inform. Contr., 9(4):1651-1677.
[19]Yoo, M., 2009. Real-time task scheduling by multiobjective genetic algorithm. J. Syst. Softw., 82(4):619-628.
[20]Yoo, M., Gen, M., 2007. Scheduling algorithm for real-time tasks using multiobjective hybrid genetic algorithm in heterogeneous multiprocessors system. Comput. Oper. Res., 34(10):3084-3098.
Open peer comments: Debate/Discuss/Question/Opinion
<1>