基于免疫遺傳算法的Job Shop調(diào)度問題研究.pdf

1、Job Shop調(diào)度是計(jì)算機(jī)集成制造系統(tǒng)(CIMS)工程中的一個(gè)重要組成部分，它對企業(yè)的生產(chǎn)管理和控制系統(tǒng)有著重要的影響。同時(shí)，Job Shop調(diào)度問題(Job Shop schedulingproblem，JSP)又是一個(gè)典型的NP Hard問題，是組合優(yōu)化問題中最難求解的問題之一。將優(yōu)化方法的理論研究引入到Job Shop生產(chǎn)調(diào)度領(lǐng)域中，改進(jìn)算法性能、拓寬算法應(yīng)用領(lǐng)域，完善算法體系，是一個(gè)同時(shí)具有理論意義和應(yīng)用價(jià)值的課題。
　

2、　 本文分析總結(jié)了一些現(xiàn)有的調(diào)度算法，針對它們的不足，基于免疫理論和遺傳算法，設(shè)計(jì)了一種新穎的自適應(yīng)混合免疫遺傳算法SIGA(Self-adaptive Hybrid Immune GeneticAlgorithm)。為了更有效地求解JSP，基于SIGA提出了改進(jìn)的調(diào)度算法SIGA II。本文的主要工作如下：
　　 1.針對傳統(tǒng)免疫遺傳算法存在過早收斂及后期搜索效率低的問題，提出一種基于濃度的自適應(yīng)混合免疫遺傳算法(SIGA)

3、，該算法有效融合多種群遺傳算法與模擬退火算法的優(yōu)點(diǎn)，同時(shí)在算法中引入生物免疫系統(tǒng)中抗體多樣性的維持機(jī)制，提出了基于濃度的自適應(yīng)交叉變異算子和選擇策略，通過仿真實(shí)驗(yàn)，證明了算法的有效性；
　　 2.將該算法應(yīng)用于求解JSP，給出了一種基于免疫遺傳算法的求解方法，以及染色體的編碼方法和相應(yīng)的免疫遺傳操作，針對Job Shop調(diào)度問題的特殊復(fù)雜性，本文將轉(zhuǎn)換瓶頸算法(Shifting Bottleneck)和禁忌算法(Tabu)兩者相

4、結(jié)合，提出了一種瓶頸禁忌算法(STA)，并將瓶頸禁忌算法引入SIGA中，提出改進(jìn)的自適應(yīng)混合免疫遺傳算法(SIGA II)，加強(qiáng)算法在求解JSP的局部搜索能力，從而進(jìn)一步提高算法的性能。
　　 3.通過對JSP中的經(jīng)典Benchmarks算例問題進(jìn)行仿真實(shí)驗(yàn)，系統(tǒng)地分析了一些關(guān)鍵參數(shù)和算子對算法性能的影響，結(jié)果證明改進(jìn)的自適應(yīng)混合免疫遺傳算法優(yōu)于其他四種算法，具有更好的全局收斂性能。最后將SIGA II應(yīng)用于實(shí)際的生產(chǎn)調(diào)度，滿足