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

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

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

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

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