張 利，孟祥凱，劉文生

（武漢輕工大學(xué) 機(jī)械工程學(xué)院，湖北 武漢 430023）

1 車間調(diào)度優(yōu)化問題的描述

車間調(diào)度優(yōu)化問題可描述為：有n個工件在m臺機(jī)器上加工，在已有的工序要求下，在工件的加工順序及時間給定的條件下，將n個工件在機(jī)器上排序，使得生產(chǎn)周期與加工時間最短、最優(yōu)［1］。

由于日本MAZAK柔性制造生產(chǎn)線在現(xiàn)代制造業(yè)中得到了較廣泛的應(yīng)用，因此本文將智能算法中的克隆免疫遺傳算法和粒子群算法運(yùn)用在生產(chǎn)調(diào)度中，以提高生產(chǎn)效率，且可得到比較直觀的仿真結(jié)果［2］。

2 免疫遺傳算法的優(yōu)化過程

免疫算法所求解的問題即抗原，首先提取抗原中的特征信息——疫苗；然后對疫苗處理將其轉(zhuǎn)變?yōu)榍蠼鈫栴}方案；再將這個方案轉(zhuǎn)變成免疫算子來具體操作，抗原所提取的疫苗有多個，可將其進(jìn)行組合后再注射。在提取疫苗的過程中，通過接種疫苗來提高適應(yīng)度，而免疫選擇則是為了防止種群退化。

2.1 免疫遺傳算法接種疫苗［3］

設(shè)種群c＝（m1，…，），則對c種群接種的疫苗就是按比例λ（0＜λ≤1）得到的qλ＝λq個個體的變異，qλ為總的種群數(shù)量，疫苗是特定的特征信息。

2.2 免疫遺傳算法免疫選擇

圖1 免疫遺傳算法基本流程

3 粒子群算法的優(yōu)化過程

粒子群算法（Particle Swarm Optimization，PSO）是由美國的Kennedy博士和Eberhar博士于1995年提出的一種基于群智能的進(jìn)化算法。在粒子群的優(yōu)化算法當(dāng)中，粒子在一個n維的空間上搜索時，每個粒子的位置是一個所要解答的問題的解，它持續(xù)地調(diào)整自己所處的位置來進(jìn)行解的優(yōu)化。本文中，第d維第i個粒子所處的位置用Xid來表示，用Pid表示粒子群中粒子搜索到的解，用Pgd表示所有的粒子所經(jīng)歷的最好位置［5］，用表示粒子群的速度。因此，第d維的第i個粒子在某一時刻的速度為：

其中：ω為權(quán)重；η1，η2為粒子當(dāng)中兩個解的參數(shù)值；rand（）為隨機(jī)生成的函數(shù)值。因此，由式（1）可以得到粒子群下一代的位置為：

重新構(gòu)造下一位置X′id的粒子速度V′id，其中粒子移動的算式為：

其中：α與β為隨機(jī)數(shù)，α，β∈［0，1］。交換序列（Xid→Pid）以概率α保留，基本的工序操作為α（Xid→Pid）；同樣地，交換序列（Xid→Pgd）以概率β保留，基本操作由β（Xid→Pgd）表示［6］。從式（2）、式（3）當(dāng)中可以看出，它們是PSO算法求解的主要算子，并且在式子當(dāng)中，α的值對局部最優(yōu)移動的影響很大，當(dāng)其增大時，粒子位置Pid也開始向最優(yōu)解移動；同樣，β的值對局部的影響也很大，當(dāng)其越大，對粒子位置Pgd的影響就越大。圖2為粒子群算法的調(diào)度過程。

4 實(shí)驗(yàn)仿真與結(jié)果分析

本文采用經(jīng)典的10/10/G/Cmax的Job shop調(diào)度問題，通過仿真得到求解結(jié)果，并確定是否是最優(yōu)的結(jié)果。

圖2 粒子群算法的調(diào)度過程

4.1 免疫遺傳算法仿真分析

克隆免疫遺傳算法繼承了遺傳算法的高度并行迭代模式［7］，采用原始克隆免疫算法的基本參數(shù)數(shù)據(jù)如下：初始抗體數(shù)為60，替換抗體為350，克隆選擇概率0.8，克隆細(xì)胞數(shù)80，迭代次數(shù)70。

在MATLAB 2013a下得到的免疫遺傳算法的調(diào)度仿真加工曲線為圖3～圖5所示。

圖3 免疫遺傳算法最優(yōu)完成時間變化曲線

圖4 免疫遺傳算法親和度曲線

圖5 免疫遺傳算法加工時間曲線

圖3為免疫遺傳算法最優(yōu)完成時間變化曲線，可以看到，在迭代過程中隨著迭代次數(shù)增加響應(yīng)時間持續(xù)下降，最后恒定。圖4為免疫遺傳算法親和度曲線，親和度的變化不是恒定的，而是上下波動的。圖5為免疫遺傳算法加工時間曲線，它呈現(xiàn)與迭代次數(shù)有關(guān)的上下波動，其中迭代次數(shù)在20～40之間是最好的。

對10個工件、10臺機(jī)器進(jìn)行作業(yè)調(diào)度，每個工件分別在10臺機(jī)器上各加工一次，由免疫遺傳算法得到的調(diào)度甘特圖見圖6。

圖6 免疫遺傳算法調(diào)度甘特圖

4.2 粒子群算法仿真分析

通過對10個工件、10臺機(jī)器進(jìn)行作業(yè)調(diào)度，每個工件分別在10臺機(jī)器上各加工一次，每個工件的加工路線與每道工序?qū)?yīng)的加工時間T與機(jī)器Js矩陣如下：

由粒子群算法得到的調(diào)度甘特圖如圖7所示。對比圖6與圖7可以看出，兩圖的調(diào)度順序完全不同，其中粒子群算法最優(yōu)完成時間為1 128s，而免疫算法的調(diào)度最優(yōu)完成時間為1 306s，遠(yuǎn)遠(yuǎn)地大于粒子群調(diào)度算法的最優(yōu)調(diào)度時間。由此可以看出在柔性生產(chǎn)調(diào)度中粒子群算法優(yōu)于免疫遺傳算法。

圖7 粒子群算法調(diào)度甘特圖

5 結(jié)束語

本文以日本MAZAK柔性生產(chǎn)線為基礎(chǔ)，通過對兩種算法的仿真比較分析，可以得到較為優(yōu)秀的調(diào)度值。從兩種算法的對比中可以看到，粒子群算法要優(yōu)于免疫遺傳算法調(diào)度，得到解的時間也相對較短。在今后的作業(yè)調(diào)度中，智能化調(diào)度將會得到更加廣泛的應(yīng)用。

［1］于穎，李永生，樸孝春.粒子群算法在工程優(yōu)化設(shè)計(jì)中的應(yīng)用［J］.機(jī)械工程學(xué)報(bào)，2008，44（12）：226－231.

［2］宋曉宇，曹陽，孟秋宏.求解Job Shop調(diào)度問題的粒子群算法研究［J］.系統(tǒng)工程與電子技術(shù)，2008，30（12）：2398－2401.

［3］王凌.車間調(diào)度及其遺傳算法［M］.北京：清華大學(xué)出版社，2003.

［4］Rui Zhang，Shiji Song，Cheng Wu.A two－stage hybrid particle swarm optimization algorithm for the stochastic job shop scheduling problem ［J］. Knowledge－Based Systems，2012，27：393－406.

［5］李小華，熊禾根.基于粒子群算法的車間作業(yè)調(diào)度問題［J］.信息技術(shù)，2009（7）：19－21.

［6］何利，劉永賢，謝華龍.基于粒子群算法的車間調(diào)度與優(yōu)化［J］.東北大學(xué)學(xué)報(bào)（自然科學(xué)版），2008，29（4）：555－568.

［7］Sha D Y，Lin Hsing－Hung.A multi objective PSO for job－shop scheduling problems［J］.Expert Systems with Applications，2009（6）：1065－1070.