论文部分内容阅读
面对突如其来的疫情、自然灾害或事故灾难,如何高效利用有限资源,提高政府对紧急事件快速反应和抗风险的能力,为企业和人民提供更及时有效的预警和紧急救助服务,日益成为提高政府管理水平的重要内容。当事故发生后,为了尽可能减少生命和财产损失,就必须合理且迅速调度应急资源执行各种任务。因此在应急响应过程中,任务调度是影响应急系统效率的一个关键因素。由于MAS(Multi-agent System)具有协作性、灵活性、智能性、鲁棒性和可扩展性等特征,很多学者提出把MAS应用于构建应急系统。虽然目前有很多研究者对MAS中的任务调度问题作了深入研究,并提出了大量有效的任务调度算法,但是这些方法大多只针对MAS的一般特征提出的,而对于应急系统这种特殊应用领域来说,MAS必须满足如快速反应等特殊需求,因此在基于MAS的应急系统中上述任务调度方法均不再适用。本文在分析各种应急系统的基础之上,提炼出它们的主要特征,并根据这些特征构建基于MAS的应急系统框架,然后利用网络流和NP完全等相关知识,探讨基于MAS的应急系统的任务调度问题,具体工作包括下面几个方面:(1)提出基于MAS的应急系统(MAS based Emergency System,MAS-ES)框架首先从整体上提出了基于MAS的应急系统的系统架构,然后详细分析了框架中的各组成部分,同时还阐述了部件设计的合理性。(2)提出并解决了MAS-ES中的可调度问题首先定义了任务调度,基本可调度问题和基于效用的可调度问题。然后,利用流网络对该任务可调度问题进行建模,证明了最大流算法和最小费用流算法分别可以用于求解基本可调度问题和基于效用的可调度问题。(3)提出MAS-ES中的最优调度问题首先定义了基本最优调度问题和基于效用的最优调度问题,通过将X3C问题多项式规约到基本最优调度问题,证明了它们都是NP完全的。然后定义了带约束的最优调度问题,即任务之间存在某种序关系,并指明该问题可以迭代利用最小费用流算法在多项式时间求解。(4)设计了近似算法求解最优调度问题在带约束的最优调度问题的基础上,通过贪心策略设计了三种求解最优调度问题的近似算法:1)递增贪婪算法(Increased Greedy Algorithm, IGA); 2)递减贪婪算法(Decreased Greedy Algorithm, DGA); 3)迭代最小费用流算法(RevisedMinimum Cost Algorithm, RMCA),并进行了仿真实验。结果表明,IGA算法时间性能最好,但解的最优性稍差于RMCA算法;DGA算法在资源比率较小的情况下最优性很差,在资源比率较高的情况下性能较好,且时间性能最差;RMCA算法解的最优性最好。