【文章內(nèi)容簡介】 ， 終止 迭代，從最終種群中 挑選出 適應度最高的染色體，即為最優(yōu) 方案 。 以下 是 整個 過程的流程圖 ： 生產(chǎn) 調(diào)度問題 的 數(shù)學描述 不失一般性，設 n 個作業(yè) m 臺機器的車間作業(yè)調(diào)度問題滿足以下約束條件 （下文中的 “ 工件 ” 與 “ 作業(yè) ” 是同一個概念）： （ 1）每個工件包含若干道工序； （ 2）各工件必須按工藝路線以指定的次序在機器上加工； （ 3）任何一個工件的前一道工序加工完成后，方能進行后一道工序的加工，在同一臺機器上一個加工任務完成之后，方能開始另一個加工任務 。 (4）每道工序從開始到結(jié)束，不會被另外的工序所中斷。 (5) 不考慮工件加工的優(yōu)先權，不考慮加工準備時間。 (6) 一個工件同一時間只能在一臺機器上加工，一臺機器同一時間只能加工一個工件，加工的開始時間為 O。 則 生產(chǎn)調(diào)度 問題可描述如下： （ 1）設 m個工件的集合為 G， G={Gi︱ i=（ 1， 2， ……， n） }； （ 2）設 p臺機器的集合為 J， J= {Ji︱ i=（ 1， 2， ……， p） }； （ 3）工序（ i， j）表示工件 Gi的第 j道工序，工序（ i， j 1）稱為工序（ i， j）的前道工序，工序（ i， j +1）稱為工序（ i， j）的后繼工序， ki表示工件 Gi的總工序數(shù)，記 k=max（ k1， k2， ……， km）； （ 4）矩陣 Q=（ gij） n x k為執(zhí)行工序的機器序號陣， gi表示執(zhí)行工序（ i， j）的機器序號，當 jki時， gi =0； （ 5）矩陣 W=（ wij） n x k為工序的工時陣， wij表示執(zhí)行工序（ i， j）的耗時，當 jki時， wi =0，一個矩陣對（ Q， W）就可以完全描述一個車間作業(yè)調(diào)度問題； （ 6）一個調(diào)度被定義為 S={ (i , j)︱ i=1,2……m， j=1， 2……ki}，其中（ i， j）表示工件 i的第 j道工序。即一個調(diào)度是由 m個工件的所有工序的排列組合，且 m 臺機器上的排列又相互制約，必須遵循：各工件的某道工序加工時，它的前道工序已經(jīng)加工完成； （ 7） TS (a)表示在調(diào)度策略 S 下，機器 Ma上全部工序的完成時間（包括機器的執(zhí)行時間和等待時間），則調(diào)度 S 的完成時間 T（ S） =max（ TS (1)， TS ( 2)， ?， TS ( m)）； （ 8）基于最短完成時間的 JSP 問題的目標函數(shù)為 min（ T（ S）， ∨ S），即尋找一個滿足約束的調(diào)度 S，使得 T(S)最小。 仿真過程 編碼 選擇一種合適的染色體表現(xiàn)型是應用遺傳算法尋優(yōu)的首要和關鍵問題。編碼的方式包括有基于操作的編碼、基于工件的編碼、基于先后表的 二進制 編碼、基于工件對關系的 實數(shù) 編碼和基于機器的編碼等等。本文采用基于工序的編碼，利用十進制直接的表達方式。 下面 是一條染色體示例： 1 2 3 2 1 2 3 1 2 3 在這 條染色體中 ， 各個 基因 依 次表示 第一個 工件的第一道工序、第二個工件的第一道工序 、 第三個工件的第一道工序、第二個工件的第二道工序 、第 一個 工件 的第二 道 工序 、 第二個工件的第三道工序 ?? 簡而言之 ，基因的編號 表示 當前要加工的 工件 ， 他 第幾次出現(xiàn) 表示 這是 該工件 的第幾道 工序。在執(zhí)行 這個 方案 時 ，程序先判斷當前要加工的基因 （ 工序 ）所需的 機器 是否空閑， 若是 ，則立即 進行 這個 工序，并接著 判斷下一個基因 ： 否則 ，等待 該機器 直到 空閑 再 進行該工序。 因此 不難看出染色體的任意排列總能產(chǎn)生可行調(diào)度，而且可以肯定這種編碼方式一定含有最優(yōu)調(diào)度方案。 生成 初始種群 我們 采用的 是 十進制的編碼方式，這里采用隨機產(chǎn)生初始種群的方法。也就是在一個給定的合理的染色體的基礎上， 再將其中基因的 順序打亂，進而產(chǎn)生新的染色體。 這一部分的 C 語言 代碼實現(xiàn) 見 附錄一 。 適應度 函數(shù) 在遺傳算法中，適應度是 判斷 個體對生存環(huán)境的適應程度 的 指標，適應度高的個體將獲得更多的生存機會 ， 最終的種群就是 由 一些適應度 很高 的染色體 組成 。適應度函數(shù)F（ *）的值 在這 里的意義是這種方案比 完全 一道一道工序來所需 的 時間所節(jié)省的時間，可以從目標函數(shù) T（ *）經(jīng)轉(zhuǎn)換得到。遺傳算法中要求適應度函數(shù)的取值為非負數(shù)，因此可用下式表示： ? ? ? ?sTwsF mi kj iji ?? ? ?? ?1 1 然后 有一個很重要的問題 就是 如何計算 T(S)， 最簡單的方法是 模擬 實際 工件 的加工過程， 并且 記錄時間，最后得到總時間 。 但是 這種 方式過于繁瑣，并且不利于編程 實現(xiàn) 。所以 我們 選用了 這部分 的代碼見附錄二。 選擇算子 我們 使用了輪盤賭 的 方法 來 實現(xiàn) “優(yōu)勝劣汰，適者生存 ”的 選擇算子 。具體 方法 是，首先根據(jù)各染色體的適應度換算出它被選中的概率，然后從 N 個 染色體 中按 這個 概率 依次 選出 N 個 （ N 為偶數(shù) ） ， 這樣適應度高的染色體可能出現(xiàn)多次，適應度 低 的就 很可能被 淘汰 。 這個 換算公式是： ? ?? ???? nj ffpvivij1 概率轉(zhuǎn)換部分 的代碼見附錄三。 交叉算子 交叉操作是將父代的良好基因通過信息互換而產(chǎn)生更好的子代。 上一步 得到 的 N 個染色體就獲得了 繁殖 的 機會， 我們 把 N 個染色體 隨機 配成 N/2 對 ， 對每一對 進行 交叉 ，交叉的過程如下：先 在染色體 中 隨機取一個點 ，然后把兩條染色體該 點 以后 的 基因 進行交換 。 直接交換非常容易出現(xiàn)不合理的情況， 即 一個工件出現(xiàn)的次數(shù)超過他實際的工序數(shù)。為了 解決這個 問題，我們規(guī)定交換 是 逐個 基因 交換 ， 交換時判斷是否超出，一旦超出， 這個 位置的 基因 就 保持不變，同時判斷 如果 保持不變 是否超出，如果仍然超出，則從剩下的沒有超出的基因類型中 隨機 選出一個 賦給 這個位置 。 變異 算子 為了 增加 染色體類型 ，我們 仿照 自然規(guī)律，在交叉 以外 增加 了 變異算子， 產(chǎn)生 變異的方式是， 在 交叉完成后 ， 按照 給定 的變異概率， 在 一個染色體 中 隨機選取 一對基因 進行交換。 以上 三步 （ 選擇、交叉 、 變異 過程 ）的代碼見附錄 四 4. 仿真結(jié)果 我們 使用這個 兩個 矩陣來 模擬 實際需求 ， 他們分別是 Q 陣和 W 陣， 橫軸為工序數(shù)，縱軸為 工件 編號， Q 陣 中的元素 是 某 工件的 某道 工序?qū)臋C器， W 陣中的 元素為對應的時間。 下面 是我們使用 的范例 Q= [ 1 2 3 4 5 6； 2 5 4 1 6 3； 5 4 1 2 3 6； 3 5 6 1 2 4； 1 3 5 4 6 2； 3 1 6 5 4 2 ] W= [ 8 3 6 3 1 9； 3 2 7 5 10 4； 9 4 1 9 1 2； 3 4 5 3 5 9； 2 3 5 4 6 1； 10 3 9 1 4 8 ] 輸入 這兩個矩陣以后 ， 我們 使用 這個模型， 迭代 100 次 以后 得到了 一種最優(yōu)方案S= [ 5 2 4 3 1 6 6 3 5 4 5 1 2 4 4 6 5 3 3 2 5 1 2 1 6 4 6 1 2 4 1 2 5 3 6 3]，根據(jù) 這個方案以及 Q 與 W 矩陣 ，我們算出來 T(S)??????=55。 在 迭代 過程中， 每個 種群 中 的 局部最優(yōu)解 的 所需 時間 變化 曲線如下圖： 5. 模型檢驗與魯棒性分析 為了 檢驗模型的魯棒性，我們 更換輸入 矩陣 ，并 畫出 種群 平均 耗時的 曲線圖， 發(fā)現(xiàn)得到了類似的結(jié)果，這說明 我們的 模型具有 比較 好的 魯棒性。 6. 模型的優(yōu)缺點和改進方向 這個 模型采用了遺傳算法來解決 生產(chǎn)調(diào)度問題 ，通過仿真結(jié)果 我們可以發(fā)現(xiàn)， 這種方法耗時短 ，能較快的 獲得 近似 最優(yōu)方案，而且是黑箱操作， 簡潔 有效 。 更重要 的 是 ，采用同時處理群體中多個個體的方法，降低了陷入局部最優(yōu)解的可能性，并易于并