遺傳算法及其在生產(chǎn)調(diào)度中的應(yīng)用.pdf

1、遺傳算法是一種模擬生物進(jìn)化過程的隨機(jī)搜索算法，其自組織、自適應(yīng)、自學(xué)習(xí)和種群進(jìn)化能力使其適合于大規(guī)模復(fù)雜優(yōu)化問題。它將問題的求解表示成“染色體”的適者生存過程，通過種群的一代代不斷進(jìn)化，包括復(fù)制、交叉和變異等操作，最終收斂到“最適應(yīng)環(huán)境”的個體，從而求得問題的最優(yōu)解或者滿意解。隨著計算機(jī)技術(shù)的發(fā)展，遺傳算法越來越受到人們的重視，并在機(jī)器學(xué)習(xí)、模式識別、神經(jīng)網(wǎng)絡(luò)、優(yōu)化控制、組合優(yōu)化等領(lǐng)域得到了成功的應(yīng)用。 生產(chǎn)調(diào)度問題幾乎在現(xiàn)實(shí)環(huán)

2、境中，特別是在工業(yè)工程領(lǐng)域無所不在。許多制造工業(yè)提出的調(diào)度問題從本質(zhì)上講非常復(fù)雜，難以用傳統(tǒng)優(yōu)化方法求解。因此，調(diào)度問題成為遺傳算法領(lǐng)域里的一個熱門話題。原因是該問題表現(xiàn)出約束組合優(yōu)化問題的所有特征，并且成為測試新算法思想的范例。 本文將介紹遺傳算法在生產(chǎn)調(diào)度方面的應(yīng)用，并結(jié)合一個模型，提出我們的共生進(jìn)化遺傳算法。通過大量的試驗(yàn)，說明算法的可行性和有效性。 本文第一部分分別介紹了遺傳算法和生產(chǎn)調(diào)度理論。第一節(jié)介紹了遺傳算

3、法的生物學(xué)基礎(chǔ)，并描述了遺傳算法的一般框架。指出了和傳統(tǒng)優(yōu)化方法相比遺傳算法具有的獨(dú)特優(yōu)點(diǎn)?？偨Y(jié)了遺傳算法在基礎(chǔ)理論研究、算法設(shè)計和應(yīng)用領(lǐng)域的研究情況。第二節(jié)介紹了生產(chǎn)調(diào)度理論的產(chǎn)生、發(fā)展、分類和已有的解決調(diào)度問題的方法，指出各種方法的優(yōu)點(diǎn)缺點(diǎn)。 第二部分提出了本文需要解決的問題：優(yōu)化調(diào)度，使得工件的最大完成時間(makespan)最小。首先給出一種表達(dá)柔性生產(chǎn)調(diào)度的模型，這個模型能方便的表示工序間的相互關(guān)系。針對加工計劃和Jo

4、b-Shop調(diào)度問題緊密結(jié)合的特點(diǎn)，我們基于生物共生進(jìn)化的思想，結(jié)合傳統(tǒng)的啟發(fā)式算法，提出了一個共生進(jìn)化遺傳算法框架。對加工計劃部分，個體編碼采用機(jī)器序列和選擇序列的符號串編碼；遺傳算子采用簡單的單點(diǎn)交叉和單點(diǎn)變異。對Job-Shop調(diào)度部分，個體編碼是基于所有工序的排列串，采用基于排列的交叉和變異算子，并利用結(jié)合Giffler&Thompson算法的過程進(jìn)行解碼，以生成最終的調(diào)度結(jié)果。 由于遺傳算法理論分析上的困難，以及生產(chǎn)調(diào)