基于置換群的遺傳算法在允許搶先的開放式車間調(diào)度中的應(yīng)用研究.pdf

1、經(jīng)典的車間調(diào)度問題主要包含：流水線車間調(diào)度、任務(wù)車間調(diào)度和開放式車間調(diào)度，其中開放式車間調(diào)度又分為允許搶先和不允許搶先。這些調(diào)度問題均屬于NP—hard問題，且每個(gè)調(diào)度模型均在企業(yè)生產(chǎn)中有很多應(yīng)用。因此研究車間調(diào)度問題意義重大。而允許搶先的開放式車間調(diào)度問題又是最復(fù)雜的調(diào)度問題，因此本文以此為著手點(diǎn)，提出解決問題的方法。
　　 本文從車間調(diào)度問題的背景和研究現(xiàn)狀入手，給出了三類車間調(diào)度問題的一般化模型。對于這三類模型，其本質(zhì)事實(shí)

2、上都是一樣的，都是排序方式的選擇，只是對排序的要求有所不同。對于開放式車間調(diào)度，由于工序的加工順序沒有任何約束，因此此問題是最復(fù)雜的。對于有10個(gè)工件10臺(tái)機(jī)器的任務(wù)來說，問題就已經(jīng)變得難以求解?？梢圆扇l(fā)式算法進(jìn)行求解，但此算法最終只能得到一個(gè)盡可能的滿意解，即Pareto最優(yōu)解。鑒于此問題的現(xiàn)實(shí)意義和重要性，有必要再尋求更精確的可行解。為了得到精確地最優(yōu)解，本文介紹了一種Gonzalez和Sahni的迭代算法以及該算法的可實(shí)踐性。

3、因此本文應(yīng)運(yùn)而生。
　　 遺傳算法自上世紀(jì)70年代產(chǎn)生以來，就一直受到關(guān)注。它應(yīng)用廣泛，已有眾多學(xué)者將其應(yīng)用到函數(shù)優(yōu)化問題、組合優(yōu)化問題、自動(dòng)控制、機(jī)器人智能控制、組合圖像處理和模式識(shí)別等方面。并且遺傳算法思路簡單，操作性強(qiáng)，而且具有很好的魯棒性。而置換群又是一系列排列組成的群，對于群的運(yùn)算有著良好的性質(zhì)，因此本文將置換群和遺傳算法相結(jié)合，提出了一種新的求解Gonzalez和Sahni的迭代算法的方法。因此文章在介紹Gonzal

4、ez和Sahni的迭代算法的實(shí)現(xiàn)方法之前，簡要介紹了遺傳算法以及置換群的基本思想。
　　 本文提出的新的遺傳算法在編碼方式、交叉和變異的法則上，均與傳統(tǒng)的遺傳算法不同。并且通過置換群的定義和性質(zhì)論證了這種新的編碼、交叉和變異的法則是現(xiàn)實(shí)可行的，且便于操作的。新的遺傳算法適用的范圍也很大，在一般的規(guī)劃模型中，只要約束條件是包含了每行每列有且只有一個(gè)元素能取到的所有0—1規(guī)劃模型均可應(yīng)用。如本文提出的允許搶先的開放式車間調(diào)度問題，以