基于MAS的應(yīng)急系統(tǒng)任務(wù)調(diào)度問(wèn)題研究.pdf

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

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

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