【導讀】作業(yè)車間調(diào)度問題簡單來說就是設備資源優(yōu)化配置問題。系統(tǒng)有著重要的影響。在當今的競爭環(huán)境下，如何利用計算機技術實現(xiàn)生產(chǎn)調(diào)度計劃優(yōu)。近年來遺傳算法得到了很大的發(fā)展，應用遺傳算法來解決車間調(diào)度問題早。本文在已有算法基礎上詳細討論了染色體編碼方法并對其進行了改進。該算法是將sigmoid函數(shù)的變形函數(shù)應用到自適應遺傳算法中，并。時的“早熟”和穩(wěn)定性差的缺點，以及傳統(tǒng)的線性自適應遺傳算法收斂速度慢的缺點。統(tǒng)，詳細介紹了各個模塊的功能與操作。最后根據(jù)改進的編碼進行遺傳算法的設計，本

　　

【正文】 作序列 1 2 3 操作時間 J1 J2 J3 3 1 3 3 5 2 2 3 3 機器 J1 J2 J3 M1 M1 M2 M2 M3 M1 M3 M2 M3 對于上表 3個工件在 3個 機器上加工的例子，假設染色體為 {2 1 2 3 1 1 3 2 3}， Oijk 表示第 i個工件的第 j 個工序在第 k 個機器上加工（以下同），則對機器加工順序的工藝約束，該染色體對應的有序操作表為 [O211 O111 O223 O312 O122 O133 O321 O232 O333]，即首先安排第二個工件的第一個操作步驟，然后安排第一個工件的第一個操作步驟，第二項任務的第二個操作步驟， ? 以次類推。進而相應的調(diào)度如圖 （我們用 Gantte圖表示一個調(diào)度）。 圖 Gantte 圖 t 12 9 6 J3 J3 J3 J1 J1 J1 J2 J2 J2 t t 1 M1 10 7 3 4 M3 M2 遼寧科技大學本科生畢業(yè)設計 第 18 頁 （ jobbased representation） 將每個染色體用 n個代表工件的基因組成，是所有工件的一個排列。解碼過程是先加工第 1 號工件的所有操作，然后依次以最好允許加工時間加工后面所有操作。其基本思想是只對任務進行編碼，然后按照編碼在染色體中的順序來以相應的優(yōu)先級別安排任務。例如，對于上述 3*3 例子。對于有三項任務的調(diào)度問題，假設染色體為 [2 3 1]，則可以解釋為首先安排第二項任務的所有操作，其次是第三項任務，最后才輪到第一項任務。 的編碼 （ preferences listbeset representation） 每個染色體用分別對應于 m 臺不同機器的 m 個子串構(gòu)成，各子串是一個長度為 n的符號串。用于表示機器上加工工件的一個排列順序。 () 對染色體的解釋為：在第一臺機器上首先應該安排第二項工件的操作，其次是第一項工件的操作，第三項工件的操作；在第二臺機器上首先應該安排第三項工件的操作，然后是第一、二項任務的操作，以此類推。 前面兩種編碼方式比較復雜，下面我們用基于操作的編碼方式來解此車間調(diào)度問題： 把調(diào)度編碼為工 序的序列，每個基因代表一道工序，給所有同一工件的工序指定相同的符號，其解碼原則是將染色體上得基因按照從左到右得順序解釋為任務相應順序的操作。這是一種直接對調(diào)度方案進行編碼的方式。顯然，這種解碼過程可產(chǎn)生活動調(diào)度。 對于 n 個工件 m 機器問題，一個染色體包括個 n*m 個基因，每個個體出現(xiàn)在染色體中 m次，每個基因不表明具體的工序，而是指上下依賴關系的工序。只需改變工序的順序，即可得到不同的調(diào)度結(jié)果，即不同的生產(chǎn)周期。 如果染色體位為 [3 2 2 1 1 2 3 1 3 1]，其中 1 表示工件 j1， 2 表示工件 j2， 3 表示 工件 j3。因為每個工件有三道工序，所以每個工件在一個染色體中剛好出現(xiàn)三次。例如， 遼寧科技大學本科生畢業(yè)設計 第 19 頁 在以上給定的染色體中出現(xiàn)三個 2 表示工件 j2 的三道工序，第一個 2 對應工件 j2 的第一道工序在機器 1 上加工，第二個 2 對應工件 j2 的第二道工序在機器 2 上加工，第三個2 對應工件 j2 的第三道工序在機器 3 上加工?？梢钥闯龉ぜ?j2 的所有工序都用相同的符號 2 來命名，并且根據(jù)它出 現(xiàn)在染色體中的順序加以解釋，工件的工序和加工機器的對應關系如下 所示。 染色體 1 1 2 2 3 3 1 1 2 3 ↓ ↓ ↓ 機器 1 2 3 一個好的調(diào)度方法（換句話說就是染色體對應的適應度值高），可以有效提機器的利用率，降低機器空閑的時間長度，從而達到優(yōu)化的目的，遺傳算法就是來尋找這樣的更優(yōu)的調(diào)度策略。 初始種群的生成 在 N 個工件 M臺機器的排序問題中，對每個機器的加工存在加工工藝順約束，這個工藝約束表示為工件的加工順序矩陣： M11 M12 ? M1M M（ J,M） = M21 M22 ? M2M ： ： ： ： () Mn1 Mn2 ? MnM 其中第 J行表示第 J個工件的機器順序 .機器號為零表示工件加工結(jié)束。 相應的每個加工操作有時間矩陣： T11 T12 ? T1M T21 T22 ? T2M T(J,M)= ： ： ： ： () TN1 TN2 ? TNM 其中第 J 行表示第 J 個工件的機器加工時間 ,時間為零表示工件不在機器上加工 . 因為每個個體由 N 個工件號重復 M 次組成的 .所以產(chǎn)生一個 1,2.. .. ..N(每個重復有N*M 個操作 )的全排列即是一個初始個體 ,算法如下： STEP1：用行號 1 代替機器順序矩陣 M(j,m)的第 j 行的所有元素 ,零元素保持不變 , 遼寧科技大學本科生畢業(yè)設計 第 20 頁 若產(chǎn)生的矩陣為 GEN。 STEP2：產(chǎn)生一個整數(shù)隨機數(shù) 1=p=N。 STEP3：令 chrom（ i） =p，并且將矩陣 GEN 的 p 行 GEN（ p，：）左移一個元素，此行移出的最后一個元素 用 零代替。 STEP4：重復 STIP2， STEP3，直到 GEN 的所有元素為零。產(chǎn)生的 chrom 為一個個體。重復 STEP1， STEP2， STEP3， STEP4，直到種群滿。 這是用遺傳算法解決車間調(diào)度問題的一種初始化群體方法 ［ 13］ ，但是它并不適用于基于操作 的編碼方式。 初始種群的生成也可以用隨機方法產(chǎn)生，這是因為群體中的個體都是由工件的符號組成的，而且工件任意排列總能產(chǎn)生可行調(diào)度 .在下文的舉例驗證過程中我們運用了隨機的方法產(chǎn)生初始種群。 個體的適應度函數(shù) 在遺傳算法中 ,適應度是描述個體性能的主要指標。根據(jù)適應度的大小 ,對個體進行優(yōu)勝劣汰。適應度是驅(qū)動遺傳算法的動力。從生物學角度講 ,適應度相當于“生存競爭 ,適者生存”的生物生存能力 ,在遺傳過程中具有重要意義。 適應度函數(shù)就是目標函數(shù)，在用遺傳算法解決車間調(diào)度問題里，定義個體的適應度函數(shù)為在 M 臺機器 上排序加工完 N 個工件所需的時間，根據(jù)染色體編碼的思想提出的適應度算法如下： STEP1:定義 ti(n)為每個工件的可加工時間，初始化向量為零向量。 STEP2:chrom（ i） 對應相應工序的加工機器為 machiner（ i）。 ti(chrom(1))=ti(chrom(1),machine(1)) STEP3:for i=2 to n For k=1 to n ti(chrom(i))=ti(chrom(i1))+max(ti(chrom(ik),machine(ik)+k)) 其中若當 ik=0,則ti(chrom(ik),machine(ik))=0,還有要判斷 chorm(i)所對應的工件在以前是否加工過，若加工過，則 ti(chrom(i))=ti(chorm(i1))。 STEP4:求出適應度函數(shù) F=ti(chorm(n))。 算法參數(shù) 標準 GA 有 4 個關鍵參數(shù)，包括種群數(shù)目 （ population size,記作 M） 、交叉概率 遼寧科技大學本科生畢業(yè)設計 第 21 頁 （ crossover rate,記作 pc） 、變異概率 （ mutation rate,記作 pm） 和代溝 （ generation gap,記作 （ G） 。目前，如何確定 GA 的最優(yōu)參數(shù)仍舊是一個公開的問題，也是研究 GA 的重要課題之一。 M 種群數(shù)目是影響算法最終優(yōu)化性能和效率的因素之一。通常，種群太小 時，不能提供足夠的采樣點，以致算法性能很差，甚至得不到問題得可行解；種群太大時，盡管可增加優(yōu)化信息以阻止早熟收斂的發(fā)生，但無疑會增加計算量，從而使收斂時間太長。當然，在優(yōu)化過程中種群數(shù)目是允許變化的，也可以將較大規(guī)模的種群分解成若干子種群進行優(yōu)化。 pc 交叉概率用于控制交叉操作的頻率。交叉概率太大時，種群中串的更新很快 ，進而會使高適應值的個體很快被破壞掉；概率太小時，交叉操作很少進行，從而會使搜索停滯不前。 pm 變異概率是加大種群多樣性的重要因素。通常一個較低的變異概率足以防止整個群體中任一位置的基因一直保持不變。但是，變異概率太小則不會產(chǎn)生新個體，抑制早熟現(xiàn)象的能力較差，概率太大則會破壞掉很多較好的模式，使 GA 成為隨機搜索。 遺傳算子的設計 選擇操作是對自然界“適者生存 ” 的模擬。評價值 (目標函數(shù) )較小的個體有較高的概率生存 ,即在下一代群體中再次出現(xiàn)。一種常用的選擇方法是按比例選 擇 ,即若個體 i適應值 (目標函數(shù) )是 fi,則個體在群體中復制 (再生 )的子代個數(shù)在群體中的比例將為 : /iiff? 。 其中 ,∑fi 表示指所有個體適應值之和。 對群體中各個體的適應值做比較 ,將適應值小的個體復制 ,將適應值大的淘汰掉 ,這是因為在作業(yè)調(diào)度算法中的適應度函數(shù)為在 M 臺機器上加工完 N 個工件所需的時間 ,時間越短 ,更能達到優(yōu)化的目的。 第一種交叉算子 遼寧科技大學本科生畢業(yè)設計 第 22 頁 在用遺傳算法解決作業(yè)車間調(diào)度問題中 ,在對工序編碼的排序問題中 ,交叉算子不能簡單交換兩個個體的相應位置的基因段 ,因為這樣得到的后代個體可能不能滿足每個工件號重復 M次的要求。 例如 :染色體 1 1 2 2 3 3 1 1 2 3 染色體 2 2 1 3 1 2 3 1 3 2 交換點隨機選擇 4,則交換后得到的新串為 : 染色體 1ˊ 1 2 2 3 2 1 1 2 3 染色體 2ˊ 2 1 3 1 3 3 1 3 2 很清楚的可以看到交換后新串中的每個工件出現(xiàn)的次數(shù)已經(jīng)不能等于機器數(shù)。所以為了滿足我們的工序編碼的要求 ,本文采用另一種交叉 算子。算子描述如下 : 隨機將工件集合 {1,2,…N }分成兩個互補子集 ,相應的將個體的基因分成兩個部分，然后把父母個體中的 part2 部分用 h 代替形成兩個新串，用第二個父母個體的 part2 部分按照原來的相對順序逐個替換第一個父母個體的 part2 產(chǎn)生的新串中的 h ,同樣用第一個父母個體的 part2 按照原來的相對順序逐個替換第二個父母個體的 prat1 產(chǎn)生的新串中的 h,得到兩個后代個體。 例如 :對于一個 4 個工件 4 個機器問題 ,假如父母個體為 : Parent1:1 3 4 2 4 2 3 3 1 4 3 2 1 4 2 1 Parent2:3 2 4 1 1 2 3 4 4 2 3 1 2 4 1 3 假設隨機選擇工件 1， 2，則從 parent1 得到的新串為： New1:1 h h 2 h 2 h h 1 h h 2 1 h 2 1 Part1:1 2 2 1 2 1 2 1 Part2:3 4 4 3 3 4 3 4 同樣從 Parent2 得到的新串為 New2:h 2 h 1 1 2 h h h 2 h 1 2 h 1 h Part1: 2 1 1 2 2 1 2 1 Part2: 3 4 3 4 4 3 4 3 然后用 Parent2 個體的 part2： 3 4 3 4 4 3 4 3 按照原來的相對順序逐個替換第一個父母個體 Parent1 產(chǎn)生的新串 New1： 1 h h 2 h 2 h h 1 h h 2 1 h 2 1 中的 h，得到的后代個體為： Parent1＇ :1 3 4 2 3 2 4 4 1 3 4 2 1 3 2 1 同理用 Parent1 個體的 part2： 3 4 4 3 3 4 3 4 按照原來的相對順序逐個替換第二個父 遼寧科技