多Agent系统中的任务可调度问题  

Task schedulable problem in multi-agent system

作　　者：章小卫[1] 李斌[1] 吴俊[1] 

机构地区：[1]扬州大学信息工程学院,扬州225009

出　　处：《东南大学学报（自然科学版）》2008年第A01期150-153,共4页Journal of Southeast University：Natural Science Edition

基　　金：江苏省自然科学基金资助项目(06KJB520132);江苏省教育厅自然科学基金资助项目(06KJB520132)

摘　　要：为了将Agent方法应用于应急系统等新领域,在对该类系统研究的基础上提炼出它们的公共特征,根据这些特征设计出一种MAS系统模型,并在该模型的基础上定义了相应的任务可调度问题.利用网络流模型对可调度问题进行了建模,证明了最大流算法可以求解该可调度问题,由此说明该问题是可多项式时间求解的.并且对于给定该问题的一个可调度实例,利用最大流算法还可在系统中找到一组Agent完成所有任务.通过对该网络流模型的进一步分析,得出并且证明了任务可调度判定的充分必要条件,利用这个结论可以快速判断当前任务是否可调度.In order to apply the Agent method to new areas such as emergency system, some common characteristics are refined by investigating such systems, a multi-agent system model is built according to these common characteristics, and the corresponding task schedulable problem is also defined based on this multi-agent system model. The task schedulable problem is modeled using the flow network model, and it is proved that the maximum flow algorithm can be used to solve such problem, which means that the problem can be solved in polynomial time. This also means that for a given instance of the problem which is schedulable, the maximum flow algorithm can find a group of agents to accomplish all the tasks. Finally, by further analyzing the flow network model, a necessary and sufficient condition is gained and proved, which can be used to efficiently determine whether the tasks can be scheduled.

关 键 词：多AGENT系统 任务调度 网络流 最大流算法 

分 类 号：U459.2[建筑科学—桥梁与隧道工程]