【文章內(nèi)容簡介】 ， 終止 迭代，從最終種群中 挑選出 適應(yīng)度最高的染色體，即為最優(yōu) 方案 。 以下 是 整個 過程的流程圖 ： 生產(chǎn) 調(diào)度問題 的 數(shù)學(xué)描述 不失一般性，設(shè) n 個作業(yè) m 臺機器的車間作業(yè)調(diào)度問題滿足以下約束條件 （下文中的 “ 工件 ” 與 “ 作業(yè) ” 是同一個概念）： （ 1）每個工件包含若干道工序； （ 2）各工件必須按工藝路線以指定的次序在機器上加工； （ 3）任何一個工件的前一道工序加工完成后，方能進行后一道工序的加工，在同一臺機器上一個加工任務(wù)完成之后，方能開始另一個加工任務(wù) 。 (4）每道工序從開始到結(jié)束，不會被另外的工序所中斷。 (5) 不考慮工件加工的優(yōu)先權(quán)，不考慮加工準備時間。 (6) 一個工件同一時間只能在一臺機器上加工，一臺機器同一時間只能加工一個工件，加工的開始時間為 O。 則 生產(chǎn)調(diào)度 問題可描述如下： （ 1）設(shè) m個工件的集合為 G， G={Gi︱ i=（ 1， 2， ……， n） }； （ 2）設(shè) 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）的機器序號，當(dāng) jki時， gi =0； （ 5）矩陣 W=（ wij） n x k為工序的工時陣， wij表示執(zhí)行工序（ i， j）的耗時，當(dāng) 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īng)用遺傳算法尋優(yōu)的首要和關(guān)鍵問題。編碼的方式包括有基于操作的編碼、基于工件的編碼、基于先后表的 二進制 編碼、基于工件對關(guān)系的 實數(shù) 編碼和基于機器的編碼等等。本文采用基于工序的編碼，利用十進制直接的表達方式。 下面 是一條染色體示例： 1 2 3 2 1 2 3 1 2 3 在這 條染色體中 ， 各個 基因 依 次表示 第一個 工件的第一道工序、第二個工件的第一道工序 、 第三個工件的第一道工序、第二個工件的第二道工序 、第 一個 工件 的第二 道 工序 、 第二個工件的第三道工序 ?? 簡而言之 ，基因的編號 表示 當(dāng)前要加工的 工件 ， 他 第幾次出現(xiàn) 表示 這是 該工件 的第幾道 工序。在執(zhí)行 這個 方案 時 ，程序先判斷當(dāng)前要加工的基因 （ 工序 ）所需的 機器 是否空閑， 若是 ，則立即 進行 這個 工序，并接著 判斷下一個基因 ： 否則 ，等待 該機器 直到 空閑 再 進行該工序。 因此 不難看出染色體的任意排列總能產(chǎn)生可行調(diào)度，而且可以肯定這種編碼方式一定含有最優(yōu)調(diào)度方案。 生成 初始種群 我們 采用的 是 十進制的編碼方式，這里采用隨機產(chǎn)生初始種群的方法。也就是在一個給定的合理的染色體的基礎(chǔ)上， 再將其中基因的 順序打亂，進而產(chǎn)生新的染色體。 這一部分的 C 語言 代碼實現(xiàn) 見 附錄一 。 適應(yīng)度 函數(shù) 在遺傳算法中，適應(yīng)度是 判斷 個體對生存環(huán)境的適應(yīng)程度 的 指標，適應(yīng)度高的個體將獲得更多的生存機會 ， 最終的種群就是 由 一些適應(yīng)度 很高 的染色體 組成 。適應(yīng)度函數(shù)F（ *）的值 在這 里的意義是這種方案比 完全 一道一道工序來所需 的 時間所節(jié)省的時間，可以從目標函數(shù) T（ *）經(jīng)轉(zhuǎn)換得到。遺傳算法中要求適應(yīng)度函數(shù)的取值為非負數(shù)，因此可用下式表示： ? ? ? ?sTwsF mi kj iji ?? ? ?? ?1 1 然后 有一個很重要的問題 就是 如何計算 T(S)， 最簡單的方法是 模擬 實際 工件 的加工過程， 并且 記錄時間，最后得到總時間 。 但是 這種 方式過于繁瑣，并且不利于編程 實現(xiàn) 。所以 我們 選用了 這部分 的代碼見附錄二。 選擇算子 我們 使用了輪盤賭 的 方法 來 實現(xiàn) “優(yōu)勝劣汰，適者生存 ”的 選擇算子 。具體 方法 是，首先根據(jù)各染色體的適應(yīng)度換算出它被選中的概率，然后從 N 個 染色體 中按 這個 概率 依次 選出 N 個 （ N 為偶數(shù) ） ， 這樣適應(yīng)度高的染色體可能出現(xiàn)多次，適應(yīng)度 低 的就 很可能被 淘汰 。 這個 換算公式是： ? ?? ???? 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ū)?yīng)的機器， W 陣中的 元素為對應(yīng)的時間。 下面 是我們使用 的范例 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. 模型檢驗與魯棒性分析 為了 檢驗?zāi)Ｐ偷聂敯粜裕覀?更換輸入 矩陣 ，并 畫出 種群 平均 耗時的 曲線圖， 發(fā)現(xiàn)得到了類似的結(jié)果，這說明 我們的 模型具有 比較 好的 魯棒性。 6. 模型的優(yōu)缺點和改進方向 這個 模型采用了遺傳算法來解決 生產(chǎn)調(diào)度問題 ，通過仿真結(jié)果 我們可以發(fā)現(xiàn)， 這種方法耗時短 ，能較快的 獲得 近似 最優(yōu)方案，而且是黑箱操作， 簡潔 有效 。 更重要 的 是 ，采用同時處理群體中多個個體的方法，降低了陷入局部最優(yōu)解的可能性，并易于并