Research On Task Scheduling Problems For MAS Based Emergency System

It has been an increasingly important aspect of improving government's management capability of, by effectively using limited resources, achieving rapid reaction to emergency incidents and improving anti-risk ability of government to provide timely and effective post-warning and emergency rescue services for the enterprise and people in the face of sudden plague, natural disasters or man-made disasters. In order to minimize the casualties and property losses, emergency resource must be reasonably and rapidly assigned to accomplish tasks when accident happens. Therefore, task scheduling is a key factor which affects efficiency of the emergency system in the emergency response process.Many researchers suggest that Multi-agent System is suitable for building emergency system because of its characteristics such as social ability, collaborativeness, flexibility, intelligence, robustness and scalability and so on. At present, the task scheduling problem in Multi-agent System has been deeply studied, and a lot of effective methods have been proposed. However, most of these methods are targeted at the general characteristics of Multi-agent System without considering the application backgrounds of it. For some special applications such as emergency system, Multi-agent System must meet some special needs such as rapid-reaction capability etc., therefore the task scheduling methods mentioned above are no longer applicable in these applications. In this dissertation, based on analysis of many kinds of existing emergency system, their main characteristics are refined, and framework of emergency system based on Multi-agent System according to these characteristics is proposed, then with the help of related knowledge such as flow network and NP complete, the task scheduling problem in Multi-agent System is discussed when it is applied to emergency system. The main works are presented in this dissertation are as follows:(1) Framework of emergency system based on Multi-agent System (MAS-ES)Firstly, the overall architecture of the emergency system based on Multi-agent system is proposed. Then, each component of the framework is analysed and explained in detail.(2) Task scheduling problem in MAS-ES Firstly, task scheduling problem, basic task schedulable problem and task schedulable problem with utility are defined. Then, task scheduling problem is modeled through flow network, and it is proved that maximum flow algorithm and minimum cost flow algorithm can be used to solve basic task schedulable problem and task schedulable problem with utility respectively.(3) Optimal task scheduling problem in MAS-ESFirstly, the basic maximum task scheduling problem (MAX-S) and optimal task scheduling problem with utility (UOTSP) are defined. Then, it is proved that both MAX-S and UOTSP are NP complete by reduce X3C problem to basic task scheduling problem in polynomial time. Lastly, the constrained optimal scheduling problem in which there is a sequence relationship between tasks is defined, and it is specified that the problem can be solved in polynomial time by iteratively using minimum cost flow algorithm.(4) Design approximation algorithms for optimal scheduling problemsIn order to gain the approximate solution of the optimal task scheduling problems, three approximation algorithms are proposed through greedy strategy based on the constrained optimal problem, which named Increased Greedy Algorithm (IGA), Decreased Greedy Algorithm (DGA) and Revised Minimum Cost Algorithm (RMCA). Then, a simulation experiment is carried out, and the experiment results show that the time performance of IGA algorithm is the best, but the solution optimality of it is poorer than that of RMCA algorithm. The time performance of DGA algorithm is the worst, and the solution optimality is poor in the case of relatively low ratio of resources. The solution optimality of RMCA algorithm is best of all.