Job-Shop調度問題理論及方法的應用研究.pdf

1、天津大學博士學位論文JobShop調度問題理論及方法的應用研究姓名：童剛申請學位級別：博士專業(yè)：管理科學與工程指導教師：李光泉劉寶坤2000.6.1適合于以最小制造周期為目標函數(shù)調度問題的求解，又適合于以最小提前／拖期懲罰代價為目標函數(shù)調度問題的求解。6在SGTsA算法中，通過對遺傳算法優(yōu)化機理深入研究，結合車間作業(yè)調度問題，提出了一種以工件號進行染色體編碼的編碼規(guī)則。采用這種編碼方式，在進行遺傳變異算子運算時，不必考慮Job—Shop

2、調度問題的約束條件的限制。而在進行遺傳交叉運算時，只須保證交叉段中相同工件的工件編號數(shù)相同。為了保證交叉段中相同工件的工件編號數(shù)相同，我們給出了兩個交叉段的交叉規(guī)則。采用這種編碼方式，可以使在遺傳操作算予運算時，省去大量的約束條件的判斷，使算法運行時間大大縮短；為了求解含有并行機的Job—Shop調度問題，提出了針對這～問題的染色體編碼規(guī)則及把一個染色體轉成可行解的規(guī)則，實現(xiàn)了用遺傳算法求解含有并行機的Job—shop調度問題；為了進～

3、步提高GA的尋優(yōu)能力，把Ts引入GA算法，用Ts作為GA的變異算子，增加個體的多樣性，迫使搜索轉向更好的解空間，以提高GA的爬山能力；為了解決對已產生的個體實施記憶及禁忌，提出了把個體經過壓縮轉化為關鍵字，然后用Hash表進行記憶的方法；7用標準問題和一些隨機產生的問題對本文提出的各種算法的可行性和有效性進行了評估、比較，結果表明所提出的算法是可行的和有效的。最后，對本文所作的工作進行了總結，對Job—shop調度問題的未來研究方向進行