| In distributed systems, with the increasing number of nodes, the complexity of task scheduling will also increase. How to schedule tasks reasonably is very important. Most traditional algorithms which lack of comprehensive measure, only consider single condition, without considering dynamical characteristic of both system and tasks. They are difficult to meet the needs of development of distributed systems. So this paper establishes a distributed task scheduling model based on multi-agent, builds a negotiation scheduling mechanism based on the model. In this model each node has independent decision-making ability.In this paper, distributed multi-objective dynamical task scheduling algorithm (DMOD) is presented to schedule tasks without dependent relation. The algorithm makes a comprehensive evaluation of task completion time, system load and communication traffic. In heterogeneous distributed environment, application will be divided into some tasks with dependent relation. How to schedule these tasks becomes very important. Traditional algorithms will not meet the needs of future development. Some nodes will offer service for many applications but not only one application. When the node is offering services for many applications, the estimation of task completion time will be not very accurate. Thus this paper presents multi-parameter scheduling algorithm (MPSA) according to the minimum value of level of the shared successor, the number of direct successor of tasks and the length from one task to the exit task from DAG structure. And then evaluation function is set according to the parameters. The algorithm avoids the error of estimation of task completion time and will eliminate the influence of the big difference of the parameters by normalization and standardization.In this paper, many groups of sets of tasks are tested. DMOD is compared with MinMin and the algorithm based on tree structure. DMOD achieves less task completion time and reduces communication traffic, meanwhile avoids performance degradation caused by sharp increase of system load and communication traffic, consequently improves system stability and task execution efficiency. MPSA is compared with ETF, LMT and HEFT in makespan and speedup. MPSA achieves better results in both makespan and speedup. |
