異構(gòu)系統(tǒng)多工作流在線調(diào)度算法研究.pdf

1、論文依托國家自然科學基金項目“面向協(xié)同設計的AUV多學科設計優(yōu)化計算框架關(guān)鍵技術(shù)研究”，針對項目開發(fā)的自主水下機器人(AUV)協(xié)同設計平臺中存在的工作流在線調(diào)度問題進行了深入研究，將該問題建模為異構(gòu)系統(tǒng)多工作流在線調(diào)度問題，并提出了一種基于前瞻的多工作流在線調(diào)度算法。仿真實驗結(jié)果顯示該算法能夠縮短多工作流的總完成時間，從而提高了AUV協(xié)同設計平臺的工作效率。
　　AUV協(xié)同設計平臺下的多工作流調(diào)度問題是一個異構(gòu)系統(tǒng)在線調(diào)度問題，通

2、常該問題不能在多項式時間內(nèi)求得最優(yōu)解，因而被公認為是一個NP問題。本文首先介紹了AUV協(xié)同設計平臺的項目背景，然后對任務調(diào)度算法進行了深入的研究，詳細介紹了MCT(Minimum Completion Time)算法、MET(Minimum Execution Time)算法、SA（Switching Algorithm）算法和KPB(K-percent Best)算法四種經(jīng)典在線任務調(diào)度算法，以及Min-min算法、Max-min算法

3、和Sufferage三種離線任務調(diào)度算法，比較了各個算法的優(yōu)缺點。結(jié)合AUV協(xié)同設計平臺的任務調(diào)度特點，針對MCT算法進行改進。
　　本文中定義了前瞻，并根據(jù)前瞻思想提出了一個在線多工作流調(diào)度算法。針對異構(gòu)環(huán)境以及多工作流的特殊性，采用小范圍內(nèi)窮舉方法的策略，利用工作流中等待隊列的信息，對當前可調(diào)度任務及其后續(xù)任務的分配方式進行局部最優(yōu)化，避免了由于前面任務占用有限資源造成后續(xù)任務的長時間等待問題，使得任務的分配更加合理，使得資源