Similar articles

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.