詳談改進(jìn)的遺傳算法求解柔性作業(yè)車(chē)間調度問(wèn)題論文
0 引言
作業(yè)車(chē)間調度問(wèn)題(Job-shop scheduling problem，JSP)是研究生產(chǎn)線(xiàn)調度問(wèn)題最常用的模型之一，也是實(shí)現先進(jìn)制造和提高生產(chǎn)效率的基礎和關(guān)鍵. 柔性作業(yè)車(chē)間調度問(wèn)題( Flexible jobshopscheduling problem，FJSP)是傳統作業(yè)車(chē)間調度問(wèn)題的擴展，在傳統的作業(yè)車(chē)間調度問(wèn)題中，每個(gè)工件的加工工序是確定的，每一道工序的加工機器和加工時(shí)間也是確定的，而在柔性作業(yè)車(chē)間調度問(wèn)題中，每個(gè)工件的每一道工序可以在多個(gè)可選擇的加工機器上進(jìn)行加工，并且不同的加工機器所需要的加工時(shí)間是不同的，增加了調度的靈活性，比較符合生產(chǎn)的實(shí)際情況.
柔性作業(yè)車(chē)間調度問(wèn)題已經(jīng)被證明是更復雜的NP-Hard 問(wèn)題，因而難以取得最優(yōu)解. 目前，求解FJSP 的常用方法有禁忌搜索( TS)，模擬退火(SA)和遺傳算法(GA)等. 其中遺傳算法以其操作簡(jiǎn)單、魯棒性強、搜索全局最優(yōu)解速度快等特點(diǎn)，在生產(chǎn)調度領(lǐng)域得到了廣泛的應用.
遺傳算法是由美國J. Holland 教授于1975 年提出的，是一種模擬自然進(jìn)化過(guò)程的一種優(yōu)化算法. 由于傳統的遺傳算法存在著(zhù)較大的缺陷，國內外學(xué)者已從不同角度對其進(jìn)行了改進(jìn)，本文對傳統遺傳算法的初始種群進(jìn)行了改進(jìn)，以提高初始解的質(zhì)量.
1 柔性作業(yè)車(chē)間調度模型設有n 個(gè)待加工工件J(J1，J2，…，Jn)，在m臺設備上加工M(M1，M2，…，Mm)，每個(gè)工件Ji有Pi(Pi1，Pi2，…，Pin) 道工序，每道工序可在一臺或多臺設備上加工，同一道工序在不同設備上加工的時(shí)間可能不等，工序Pik的可選機器集為Mik(Mik 罬)，每臺設備的加工時(shí)間從0 開(kāi)始，加工完所有工件的完成時(shí)間為ETMi . 本文以最小化最大完工時(shí)間為性能指標，其目標函數為:f(x) = min(max(ETMi))，1 ≤ i ≤ m模型需滿(mǎn)足如下約束條件:(1)同一工件的工序加工順序確定;(2)每道工序必須在它的上一道工序加工完成后才能開(kāi)始加工;(3)每道工序只能選擇一臺設備進(jìn)行操作;(4)每臺設備在同一時(shí)間只能加工一個(gè)工件的一道工序;(5)每道工序在設備上操作時(shí)都不允許被中斷;(6) 不同工件工序之間沒(méi)有先后約束條件.一個(gè)包含3 個(gè)工件、5 臺機器的FJSP 的問(wèn)題.
2 算法的設計
(1) 基因編碼
常用的遺傳算法編碼方案有二進(jìn)制編碼、格雷碼編碼、矩陣編碼、自然數編碼等，本文采用自然數編碼，每條染色體表示一個(gè)可行解，同時(shí)采用雙層編碼，第一層編碼為基于工件的工序編碼，編碼長(cháng)度為所有工件工序之和，基因值代表工件號，基因值出現的次數代表該工件的工序總數，第二層編碼為對應于第一層工件工序的機器編碼，所以編碼長(cháng)度也為所有工件工序之和.染色體表示的工序順序為(O31，O11，O12，O21，O22，O32，O13，O33)，染色體表示的機器序列為(M2，M4，M2，M1，M4，M5，M3，M4).
(2)產(chǎn)生初始種群
初始種群的優(yōu)良對生物進(jìn)化會(huì )產(chǎn)生很大的影響，本文對初始種群的機器選擇進(jìn)行了改進(jìn)，首先隨機生成初始種群的工序編碼，工序編碼生成后就要對應生成機器編碼，每個(gè)工件工序在對應可選機器集中選擇機器時(shí)，是以不同的概率的來(lái)選擇不同的機器，機器加工時(shí)間短的以大概率被選擇，相比之下，機器加工時(shí)間長(cháng)的以小概率被選擇，這樣既保證了機器選擇的隨機性，也優(yōu)化了初始種群.
(3)適應度函數的確定
本文以最小化最大完工時(shí)間為目標函數，故選擇全部工件完工時(shí)間作為評價(jià)種群優(yōu)劣的標準，設n 個(gè)待加工工件在m(M1，M2，…，Mm) 臺設備上加工，所有加工工件工序在設備上的最后完工時(shí)間為ETMi(i = 1，2，…，m)，T = max(ETMi)，則適應度函數fi = 1 /T，T 越小，則適應度越大，即個(gè)體越優(yōu).
(4)選擇
選擇操作的目的是為了保留優(yōu)良個(gè)體，使他們可以遺傳到下一代. 本文采用精英保留策略和輪盤(pán)賭法相結合的方法，對父代個(gè)體和子代個(gè)體進(jìn)行選擇時(shí)直接將最優(yōu)個(gè)體和次優(yōu)個(gè)體遺傳到下一代，然后對剩余的個(gè)體采用輪盤(pán)賭法進(jìn)行選擇，選擇出p - 2 個(gè)個(gè)體到下一代進(jìn)行遺傳操作. 若種群規模為p，個(gè)體i 的適應度為fi，則個(gè)體i 被選擇的概率pi為pi = fi /Σpk = 1fk即適應度越高的個(gè)體被選擇的概率就越大.
(5)交叉
交叉操作是產(chǎn)生新個(gè)體的主要方法，提高全局搜索能力. 本文采用單點(diǎn)交叉方式，即隨機產(chǎn)生一個(gè)交叉點(diǎn)，交換交叉點(diǎn)后的基因. 從種群中隨機選擇兩個(gè)個(gè)體，交換兩個(gè)個(gè)體工序編碼的交叉點(diǎn)后面的基因，將交叉后工件多余的工序替換為其他工件缺失的工序;機器部分則按交叉前工件工序所選擇的機器進(jìn)行相應調整以保證其子代染色體的合法性.
(6)變異
變異操作的目的是改變算法的局部搜索能力，有助于維持進(jìn)化群體的多樣性，防止過(guò)早陷入局部最優(yōu). 本文采用互換方式，即隨機產(chǎn)生兩個(gè)變異點(diǎn)，交換兩點(diǎn)的基因值. 從種群中隨機選擇一個(gè)個(gè)體，對該個(gè)體的工序編碼部分隨機產(chǎn)生兩個(gè)變異點(diǎn)，交換兩點(diǎn)的基因值，同時(shí)將交換的基因位所對應的機器號也進(jìn)行交換.
3 仿真實(shí)例分析
6 × 6(6 個(gè)工件，6 臺機器) FJSP的加工工序，機器選擇和加工時(shí)間矩陣表. 分別用標準遺傳算法和本文提出的改進(jìn)遺傳算法對工件最小化最大完工時(shí)間進(jìn)行優(yōu)化計算，并分析優(yōu)化計算結果.
遺傳算法采用以下參數:種群規模為100，進(jìn)化代數為100，交叉概率Pc = 0. 8，變異概率Pm =0. 1. 算法運行10 次，標準遺傳算法的最大完工時(shí)間為20，收斂代數為75 代左右;改進(jìn)遺傳算法的最大完工時(shí)間為16，收斂代數為35 代左右. 改進(jìn)遺傳算法既縮短了工件完工時(shí)間，也加快了收斂代數. 從而驗證了改進(jìn)遺傳算法的可行性
4 結論
傳統遺傳算法在進(jìn)行種群初始化時(shí)采用的大多是隨機選擇方式，而本文提出了一種新的種群初始化方法，提高了種群初始解的質(zhì)量. 最后對改進(jìn)遺傳算法進(jìn)行了仿真實(shí)驗，并將結果與標準遺傳算法進(jìn)行比較，結果表明了本算法的優(yōu)越性和可行性.
【詳談改進(jìn)的遺傳算法求解柔性作業(yè)車(chē)間調度問(wèn)題論文】相關(guān)文章：
巖土工程勘察問(wèn)題與改進(jìn)措施論文02-24
電力企業(yè)營(yíng)銷(xiāo)統計問(wèn)題與改進(jìn)的論文02-21
水利工程管理問(wèn)題及改進(jìn)措施論文03-02
大模板施工中常見(jiàn)的問(wèn)題及改進(jìn)措施論文03-04
中學(xué)體育教育中存在的問(wèn)題及改進(jìn)建議的論文01-15
高校體育教學(xué)存在的問(wèn)題及改進(jìn)策略論文03-05
初中體育教育問(wèn)題及改進(jìn)措施論文02-27
作業(yè)成本法的運用及應注意的問(wèn)題的論文12-07
- 相關(guān)推薦