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

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

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

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