用混合遺傳算法解決單機(jī)調(diào)度問題

1、畢業(yè)設(shè)計(jì)（論文）開題報(bào)告用混合遺傳算法解決單機(jī) 論文題目：調(diào)度問題姓 名：學(xué) 號(hào)：學(xué) 院：專 業(yè)：年 級(jí)： 指導(dǎo)教師:畢業(yè)論文開題報(bào)告1.本課題的研究意義在生產(chǎn)調(diào)度研究領(lǐng)域，單機(jī)調(diào)度問題(Single Machine Scheduling, SMS) 一直是研究熱點(diǎn)。單機(jī)調(diào)度問題是一類重要的生產(chǎn)調(diào)度問題，在理論上，單機(jī)調(diào) 度可看作是其它調(diào)度問題的特殊形式，是復(fù)雜的多機(jī)調(diào)度系統(tǒng)的一個(gè)子系統(tǒng)。深 入研究單機(jī)調(diào)度問題可以更好地理解復(fù)雜調(diào)度系統(tǒng)的結(jié)構(gòu)。在生產(chǎn)實(shí)踐中，復(fù)雜 調(diào)度問題往往可以分解為多個(gè)單機(jī)問題來解決。對(duì)單機(jī)調(diào)度問題求解算法的研究 可以為求解復(fù)雜調(diào)度問題提供算法基礎(chǔ)，因此，設(shè)計(jì)一種簡單高效的

2、求解算法是 單機(jī)調(diào)度問題研究的重要方向。因傳統(tǒng)的解決生產(chǎn)調(diào)度的算法如遺傳算法(GA)、模擬退火算法(SA),對(duì)解 決生產(chǎn)調(diào)度問題有一定的局限性。遺傳算法作為一種全局優(yōu)化搜索算法,存在著 運(yùn)算速度慢、易過早收斂、局部搜索能力弱、優(yōu)化效率較低等缺點(diǎn)。而模擬退火 算法雖然有較好的局部搜索能力，但是對(duì)全局解的搜索性能較差。而且，解決 生產(chǎn)調(diào)度問題的經(jīng)濟(jì)性要求也不允許用這類方法來求解。為了適應(yīng)實(shí)際生產(chǎn)調(diào)度的經(jīng)濟(jì)性，增強(qiáng)解決優(yōu)化問題全局和局部意義下的 搜索能力和效率。本課題將采用混合遺傳算法(GASA)對(duì)單機(jī)調(diào)度進(jìn)行求解。以 期通過兩者算法的優(yōu)越性進(jìn)行互補(bǔ)，彌補(bǔ)各自的缺點(diǎn)。得到一種優(yōu)化能力、效率 和可靠性

3、較高的優(yōu)化方法，對(duì)單機(jī)調(diào)度問題進(jìn)行優(yōu)化求解，為解復(fù)雜的多機(jī)調(diào)度 問題提供理論依據(jù)。.本課題的基本內(nèi)容本課題通過對(duì)調(diào)度問題中最基本的單機(jī)調(diào)度問題進(jìn)行深度研究，采用混合遺 傳算法對(duì)該模型進(jìn)行求解。希望通過對(duì)基本的單機(jī)調(diào)度問題的求解，給生產(chǎn)過程 中復(fù)雜的調(diào)度問題提供算法依據(jù)。調(diào)度問題學(xué)習(xí)：通過閱讀前人的書籍以及文獻(xiàn)資料，對(duì)調(diào)度問題進(jìn)行深 入了解，側(cè)重生產(chǎn)調(diào)度問題。對(duì)生產(chǎn)調(diào)度的產(chǎn)生、目前的研究進(jìn)展、在實(shí)際工業(yè) 生產(chǎn)中運(yùn)用進(jìn)行學(xué)習(xí)和理解。單機(jī)調(diào)度1|r. | w.c.分析：選定特定的單機(jī)調(diào)度模型，通過對(duì)該問題學(xué)習(xí) 理解，對(duì)模型進(jìn)行公式化表示，并選取具體的狀態(tài)利用算法進(jìn)行求解。構(gòu)造混合遺傳算法：對(duì)混合遺傳

4、算法的主要思想和基本原理進(jìn)行闡述。通 過對(duì)該模型的分析，歸納適合該模型的混合遺傳算法。同時(shí)選定編碼及初始種群 的生成方式，適應(yīng)度函數(shù)計(jì)算，算子設(shè)計(jì)，收斂條件等。描繪基于單機(jī)調(diào)度的混 合算法流程圖。實(shí)驗(yàn)程序編寫：將混合遺傳算法的具體流程通過c語言表達(dá)出來，并進(jìn)行 模擬實(shí)驗(yàn)，將獲得的最優(yōu)解與實(shí)際模型分析以及遺傳算法和模擬退火算法進(jìn)行比 較，不斷改進(jìn)遺傳算法的參數(shù)，最終獲得預(yù)期的最優(yōu)解。.本課題的重點(diǎn)和難點(diǎn)單機(jī)調(diào)度模型分析選取基于調(diào)度問題對(duì)于現(xiàn)實(shí)工業(yè)操作的重要性和實(shí)際工業(yè)生產(chǎn)的指導(dǎo)作用，如何 選定有意義的單機(jī)調(diào)度模型，使得其具有很好的現(xiàn)實(shí)意義，同時(shí)能夠確保在畢業(yè) 設(shè)計(jì)時(shí)間段能夠完成對(duì)其的研究。是本課

5、題的一大難點(diǎn)?；旌线z傳算法的設(shè)計(jì)深入學(xué)習(xí)了車間調(diào)度問題的特點(diǎn)及分類、遺傳算法和模擬退火算法的理論原 理、特點(diǎn)及操作流程，在分析遺傳算法和模擬退火算法特點(diǎn)的基礎(chǔ)上，學(xué)習(xí)了解基 于遺傳算法和模擬退火算法相結(jié)合的混合遺傳算法。應(yīng)用混合遺傳算法求解典型 的單機(jī)調(diào)度問題,算法在設(shè)計(jì)時(shí)，確定生成初始種群、交叉變異算子、產(chǎn)生隨機(jī)數(shù)、 收斂條件等的方式。確定混合算法流程圖，并通過c語言表示出來。最后，將混 合遺傳算法應(yīng)用在單機(jī)調(diào)度模型中，獲得最優(yōu)解，并在算法參數(shù)相同的情形下，和 標(biāo)準(zhǔn)遺傳算法及模擬退火算法進(jìn)行實(shí)驗(yàn)結(jié)果對(duì)比。通過對(duì)比實(shí)驗(yàn),證實(shí)混合遺傳 算法具有更優(yōu)良的尋優(yōu)性能。C語言編寫混合遺傳算法對(duì)于復(fù)雜算法

6、、原始數(shù)據(jù)眾多、進(jìn)行大規(guī)模數(shù)據(jù)操作的算法的編寫。不管是 對(duì)計(jì)算機(jī)性能以及對(duì)編寫者本人都是不小的挑戰(zhàn)。全局變量的設(shè)計(jì)、產(chǎn)生隨機(jī)數(shù) 的方式、全局空間的分配和釋放、具體函數(shù)的時(shí)間復(fù)雜度和空間復(fù)雜度等等都是 要考慮的問題。.論文提綱緒論（一）研究的背景與意義（二）求解單機(jī)問題的研究現(xiàn)狀（三）研究的主要內(nèi)容和論文章節(jié)安排混合遺傳算法（一）遺傳算法（二）模擬退火算法（三）混合遺傳算法單機(jī)調(diào)度的混合遺傳算法操作模型（一）單機(jī)調(diào)度問題描述及數(shù)學(xué)模型（二）單機(jī)調(diào)度問題的染色體編碼（三）適應(yīng)度評(píng)價(jià)函數(shù)（四）交叉與變異算子（五）混合遺傳算法流程四基于混合遺傳算法的單機(jī)調(diào)度算法設(shè)計(jì)（一）編碼、解碼（二）交叉操作算子（三）變異操作算子（四）收斂條件（五）算法參數(shù)設(shè)定及實(shí)現(xiàn)方法五基于混合遺傳算法的單機(jī)調(diào)度實(shí)現(xiàn)及仿真（一）環(huán)境選擇（二）GASA算法設(shè)計(jì)實(shí)現(xiàn)（三）GASA與GA、SA結(jié)果分析比對(duì)（四）總體實(shí)驗(yàn)結(jié)果分析六總結(jié)與