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

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

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

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

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

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

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