【導(dǎo)讀】作業(yè)車間調(diào)度問題簡(jiǎn)單來(lái)說(shuō)就是設(shè)備資源優(yōu)化配置問題。系統(tǒng)有著重要的影響。在當(dāng)今的競(jìng)爭(zhēng)環(huán)境下，如何利用計(jì)算機(jī)技術(shù)實(shí)現(xiàn)生產(chǎn)調(diào)度計(jì)劃優(yōu)。近年來(lái)遺傳算法得到了很大的發(fā)展，應(yīng)用遺傳算法來(lái)解決車間調(diào)度問題早。本文在已有算法基礎(chǔ)上詳細(xì)討論了染色體編碼方法并對(duì)其進(jìn)行了改進(jìn)。該算法是將sigmoid函數(shù)的變形函數(shù)應(yīng)用到自適應(yīng)遺傳算法中，并。時(shí)的“早熟”和穩(wěn)定性差的缺點(diǎn)，以及傳統(tǒng)的線性自適應(yīng)遺傳算法收斂速度慢的缺點(diǎn)。統(tǒng)，詳細(xì)介紹了各個(gè)模塊的功能與操作。最后根據(jù)改進(jìn)的編碼進(jìn)行遺傳算法的設(shè)計(jì)，本。導(dǎo)下進(jìn)行的研究工作及取得的成果。含我為獲得及其它教育機(jī)構(gòu)的學(xué)位或?qū)W歷而使用過(guò)的材料。明并表示了謝意。以贏利為目的前提下，學(xué)?？梢怨颊撐牡牟糠只蛉?jī)?nèi)容。除了文中特別加以標(biāo)注引用的內(nèi)容外，本論文不包含任何。其他個(gè)人或集體已經(jīng)發(fā)表或撰寫的成果作品。的個(gè)人和集體，均已在文中以明確方式標(biāo)明。本人完全意識(shí)到本聲明的法。律后果由本人承擔(dān)。

　　

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