1、 隨著計(jì)算機(jī)應(yīng)用范圍的日益擴(kuò)大，分布式異構(gòu)系統(tǒng)(DHS)逐漸成為解決復(fù)雜應(yīng)用問(wèn)題的有效工具。DHS利用一組異構(gòu)的計(jì)算機(jī)來(lái)協(xié)作完成應(yīng)用任務(wù)，以期獲得最好的執(zhí)行效果。DHS中的任務(wù)調(diào)度問(wèn)題，對(duì)發(fā)揮系統(tǒng)的并行性能和保持負(fù)載平衡具有非常重要的意義。該問(wèn)題已被證明是NP完全問(wèn)題，無(wú)法在多項(xiàng)式時(shí)間內(nèi)找到最優(yōu)解，所以促使人們不懈地研究如何設(shè)計(jì)調(diào)度算法，用有限的代價(jià)獲得更好的解。目前常用的方法就是啟發(fā)式算法和隨機(jī)搜索的近似方法。 在本文中

2、研究了主從式DHS中的調(diào)度算法問(wèn)題，對(duì)其進(jìn)行數(shù)學(xué)建模，定義并分析了主從式DHS在穩(wěn)定運(yùn)行階段的系統(tǒng)特性。對(duì)于樹(shù)形的主從結(jié)構(gòu)，本文給出了達(dá)到穩(wěn)定運(yùn)行階段的集中帶寬(bandwidth-centric)調(diào)度策略，并證明了穩(wěn)定運(yùn)行階段的最優(yōu)性。 在本文中我們提出了兩種主從式DHS下的任務(wù)調(diào)度算法。首先給出了啟發(fā)式算法IMM，該算法可以解決DHS環(huán)境下，獨(dú)立的、帶優(yōu)先權(quán)和時(shí)限的任務(wù)的調(diào)度問(wèn)題。隨后根據(jù)主從式DHS穩(wěn)定運(yùn)行階段的特點(diǎn)，提出