基于MAS的應急系統(tǒng)任務調度問題研究.pdf

1、本文在分析各種應急系統(tǒng)的基礎之上，提煉出它們的主要特征，并根據(jù)這些特征構建基于MAS的應急系統(tǒng)框架，然后利用網絡流和NP完全等相關知識，探討基于MAS的應急系統(tǒng)的任務調度問題，具體工作包括下面幾個方面： (1)提出基于MAS的應急系統(tǒng)(MAS based Emergency System，MAS-ES)框架 首先從整體上提出了基于MAS的應急系統(tǒng)的系統(tǒng)架構，然后詳細分析了框架中的各組成部分，同時還闡述了部件設計的合理性。

2、 (2)提出并解決了MAS-ES中的可調度問題 首先定義了任務調度，基本可調度問題和基于效用的可調度問題。然后，利用流網絡對該任務可調度問題進行建模，證明了最大流算法和最小費用流算法分別可以用于求解基本可調度問題和基于效用的可調度問題。 (3)提出MAS-ES中的最優(yōu)調度問題 首先定義了基本最優(yōu)調度問題和基于效用的最優(yōu)調度問題，通過將X3C問題多項式規(guī)約到基本最優(yōu)調度問題，證明了它們都是NP完全的。然后定

3、義了帶約束的最優(yōu)調度問題，即任務之間存在某種序關系，并指明該問題可以迭代利用最小費用流算法在多項式時間求解。 (4)設計了近似算法求解最優(yōu)調度問題 在帶約束的最優(yōu)調度問題的基礎上，通過貪心策略設計了三種求解最優(yōu)調度問題的近似算法：1)遞增貪婪算法(lncreased Greedy Algorithm，IGA);2)遞減貪婪算法(Decreased Greedy Algorithm，DGA);3)迭代最小費用流算法(Rev