摘 要：借鑒遺傳算法及粒子群優(yōu)化算法的思想，提出了一種改進(jìn)的粒子群算法，并將其應(yīng)用于車間作業(yè)調(diào)度問題。根據(jù)車間作業(yè)調(diào)度的目標(biāo)函數(shù)建立起算法數(shù)學(xué)模型，采用改進(jìn)的粒子群算法對車間作業(yè)調(diào)度進(jìn)行優(yōu)化，得到目標(biāo)的全局最優(yōu)解。仿真示例說明改進(jìn)的粒子群算法優(yōu)化車間作業(yè)調(diào)度的最小化加工時(shí)間目標(biāo)比遺傳算法明顯更有效。

關(guān)鍵詞：車間作業(yè)調(diào)度；粒子群算法；改進(jìn)的粒子群算法；遺傳算法；交叉；變異

0 引言

Job Shop調(diào)度問題（Job- shop scheduling problem，簡稱JSSP）研究具有重要的理論意義和工程價(jià)值，是目前研究最廣泛的一類典型調(diào)度問題。粒子群優(yōu)化（Particle Swarm Optimizer，簡稱PSO）算法是一種基于迭代的群智能演化優(yōu)化工具，最早是由Kennedy J.和 Eberhart R.于1995年提出的，目前在函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練及模糊系統(tǒng)控制等領(lǐng)域得到較為廣泛的應(yīng)用[1]。與遺傳算法比較，PSO的優(yōu)勢在于沒有許多參數(shù)需要調(diào)整[2]，簡單容易實(shí)現(xiàn)。本文在PSOA的基礎(chǔ)上提出了一種改進(jìn)的粒子群算法（Improve Particle Swarm Optimizer Algorithm，簡稱IPSOA），并將其應(yīng)用到JSSP離散問題的優(yōu)化中。

1 車間作業(yè)調(diào)度問題（Job-Shop Scheduling Problem，簡稱JSSP）

1.1 JSSP的描述

JSSP是組合優(yōu)化問題中最困難的一類，調(diào)度目標(biāo)是找到使用這些共同資源的一種排序，使生產(chǎn)約束被滿足，同時(shí)使生產(chǎn)成本最低。JSSP是在m臺(tái)不同機(jī)器上加工有特定加工工序和加工時(shí)間的n個(gè)工件。調(diào)度的目標(biāo)就是確定各臺(tái)機(jī)器上工件的加工順序和每個(gè)工件在各臺(tái)機(jī)器上的起始加工時(shí)間，使加工完所有工件所需的時(shí)間最少。

1.2 JSSP的數(shù)學(xué)模型

典型的JSSP問題有多種描述形式，通常采用Adams[3]提出的數(shù)學(xué)模型。是工件的工序集合，M表示機(jī)器集合，A是工序的先后順序有序?qū)希珽m表示在機(jī)器m上加工的工序?qū)?，Pi表示第i道工序的加工時(shí)間，ti表示第i道工序的開始加工時(shí)間。JSSP可以表示為：

設(shè)工件j經(jīng)過m道工序操作完成，且須按照給定的工序序列Oij（i=1，2，m，j=1，2，…，n）加工，即j工件的第i道工序在機(jī)器Oij上加工；

Tij（i=1，2，…，m，j=1，2，…，n）表示工件j的第i道工序的固定加工時(shí)間；C（k，j）表示工件j在機(jī)器k上的加工結(jié)束時(shí)間；Pij=find（Oj=i）為在工序矩陣Oij中，工件j在機(jī)器i上的工序。

n×m車間作業(yè)調(diào)度問題的完工時(shí)間表示如下：

即makespan為：

JSSP中優(yōu)化的一個(gè)目標(biāo)是找到一個(gè)可行調(diào)度方案，使得makespan最小。

2 算法

2.1 遺傳算法（Genetic Algorithm，GA）實(shí)現(xiàn)的基本方法[4]

采用遺傳算法來設(shè)計(jì)問題的求解方法，針對Job -Shop實(shí)際生產(chǎn)情況，具體設(shè)計(jì)環(huán)節(jié)如下：

（1）編碼方案

編碼方案采用整數(shù)編碼，5×5車間作業(yè)調(diào)度問題具體編碼如圖1所示。

評價(jià)函數(shù)）

適應(yīng)度函數(shù)是評價(jià)個(gè)體位串的適應(yīng)性，本文根據(jù)JSSP問題的調(diào)度目標(biāo)采用makespan作為算法的適應(yīng)度函數(shù)。

（3）遺傳算子

為了保證良好基因遺傳給下一代，選擇是從當(dāng)前群體中選擇適應(yīng)度值較優(yōu)的個(gè)體來生成交配池，最基本的選擇方法是適應(yīng)度值比例選擇。交叉操作是進(jìn)化算法中遺傳算法具備的原始性的獨(dú)有特征，通常采用的遺傳算子包括一點(diǎn)、兩點(diǎn)和多點(diǎn)等交叉形式。變異可以確保群體的多樣性。

（4）初始化

初始化根據(jù)工件和工序數(shù)隨機(jī)產(chǎn)生初始種群，以這些染色體為初始點(diǎn)進(jìn)行迭代。種群規(guī)?？梢噪S具體計(jì)算情況變化。

（5）終止循環(huán)的條件

采用最大代數(shù)的方法或算法的種群適應(yīng)度平均值等于最優(yōu)的運(yùn)算結(jié)果則停止。

2.2 改進(jìn)的粒子群算法

PSO算法是一種基于迭代的群智能演化優(yōu)化工具，在優(yōu)化過程中系統(tǒng)首先初始化為一組隨機(jī)解，然后通過迭代在解空間搜尋到最優(yōu)值。目前在函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練及模糊系統(tǒng)控制等領(lǐng)域應(yīng)用較為廣泛。本文提出了一種改進(jìn)的粒子群算法（Improve Particle Swarm Optimization，簡稱 IPSO），該算法是在PSO算法中采用GA算法的交叉和變異操作，并將其應(yīng)用于JSSP離散問題的優(yōu)化。因PSO算法只適合解決連續(xù)問題的優(yōu)化，所以用PSO算法來優(yōu)化JSSP的關(guān)鍵是設(shè)計(jì)一種適合離散優(yōu)化問題的有效機(jī)制。本文根據(jù)JSSP的特點(diǎn)提出了IPSO算法，具體設(shè)計(jì)如下：

（1）交叉和變異操作

交叉操作可分為：一段、二段、三段和四段交叉。一段交叉首先是在第一個(gè)父代中隨機(jī)選取兩個(gè)交叉點(diǎn)，然后把二交叉點(diǎn)間的工件序列復(fù)制到子代，最后在子代的其他位置依次用第二個(gè)父代的因子來代替。

Nearchou Ac在[5]中闡述了六種變異操作，對于不同規(guī)模的JSSP，最佳的變異操作方法是移動(dòng)變異操作，該操作的工作原理是先隨機(jī)選取一個(gè)移動(dòng)點(diǎn)和一個(gè)插入點(diǎn)，然后對工件系列進(jìn)行移動(dòng)。

（2）最小化加工時(shí)間的JSSP改進(jìn)粒子群算法的迭代模式

假設(shè)在一個(gè)由m個(gè)粒子組成的D維搜索空間中，其中表示第i個(gè)粒子在D維搜索空間中的位置。是第i個(gè)粒子的飛行速度，是迄今為止第i個(gè)粒子搜索到的最佳位置，是迄今為止整個(gè)粒子群搜索到的最佳位置[6]。IPSO的遞推方程如下：

在（2-1）、（2-2）、（2-3）和（2-4）中，k為迭代代數(shù)，為粒子i在第k次迭代時(shí)飛行速度矢量的第d維分量；是粒子i在第k次迭代時(shí)位置矢量的第d維分量；是粒子i個(gè)體最優(yōu)位置的第d維分量；為群體最優(yōu)位置的第d維分量，顯然，和都是符號(hào)或者自然數(shù)；是交叉算子符號(hào)，代表兩個(gè)粒子或者速度進(jìn)行交叉操作；，分別表示變異隨機(jī)選擇的速度和粒子，然后覆蓋原來相對應(yīng)的速度和粒子，rN表示總共需要變異的速度與粒子總數(shù)。

（3）IPSO算法的步驟

步驟l：初始化迭代代數(shù)k=0，迭代終止代數(shù)Maxgen，產(chǎn)生規(guī)模為psize的初始種群，計(jì)算種群中各粒子的適應(yīng)值，從種群中選出第一代中的最優(yōu)粒子PgBest；

步驟2：用公式（2-1）得到2×psize個(gè)粒子，計(jì)算其適應(yīng)值，從中選出適應(yīng)值較小的psize個(gè)粒子作為速度，再隨機(jī)選擇rN個(gè)速度用公式（2-2）進(jìn)行變異，然后覆蓋原來對應(yīng)的速度。同理，利用公式（2-3）和（2-4）產(chǎn)生下一代粒子。判斷，若新種群中各粒子適應(yīng)值低于個(gè)體歷史最低適應(yīng)值，用新的最低粒子代替歷史適應(yīng)值最低粒子個(gè)體PiBest，同樣判斷新種群中的粒子適應(yīng)值若低于全局最優(yōu)值，用現(xiàn)在的全局最優(yōu)粒子代替粒子PgBest；若k=Maxgen，轉(zhuǎn)至步驟3，否則令k=k+1，轉(zhuǎn)至步驟2。

3 IPSO和GA優(yōu)化JSSP的仿真結(jié)果

對10×10的車間作業(yè)調(diào)度問題采用遺傳算法和改進(jìn)的粒子群算法進(jìn)行調(diào)度，10個(gè)工件的加工工藝路線和加工時(shí)間如表1所示。

圖2是10×10 JSSP最優(yōu)調(diào)度結(jié)果的甘特（Gantt）圖。

經(jīng)過多次反復(fù)調(diào)試，在取進(jìn)化代數(shù)為3 000、群體規(guī)模為30的情況下，采用IPSO算法和GA算法優(yōu)化10×10 和20×5的JSSP典型例子，搜索最優(yōu)解過程的收斂曲線比較圖如圖3所示。

圖3中a線和c線分別表示GA算法優(yōu)化JSSP典型例子時(shí)平均值和最優(yōu)值的收斂速度，b線和d線分別表示IPSO算法優(yōu)化JSSP典型例子時(shí)平均值和最優(yōu)值的收斂速度。收斂曲線圖的橫坐標(biāo)表示進(jìn)化代數(shù)，縱坐標(biāo)表示適應(yīng)度。

4 結(jié)語

IPSO算法是基于PSO算法的思想，它們迭代方程不同，但信息來源相似，有用的信息都是主要來自個(gè)體歷史最優(yōu)粒子和全局最優(yōu)粒子。IPSO算法相比PSO算法迭代方程添加了類似于GA的交叉和變異操作，即增加了粒子種群的多樣性。在IPSO算法與GA算法中種群都是隨機(jī)產(chǎn)生的，種群中的粒子是通過適應(yīng)值進(jìn)行評估的。GA更新種群是隨機(jī)選擇的染色體進(jìn)行交叉和變異操作，基本PSO算法的粒子更新是基于權(quán)重的合并，IPSO算法采用了類似于GA中的交叉和變異操作，通過PiBest和PgBest信息共享來進(jìn)行種群更新的。IPSO算法與GA相比，更易于搜索到全局最優(yōu)值。仿真算例說明IPSO算法用于優(yōu)化JSSP的最小Makespan目標(biāo)相比GA更為有效。

參考文獻(xiàn)

[1]潘全科，孫志峻，朱儉英.基于遺傳算法在車間作業(yè)高度優(yōu)化[J].信息與控制，2003，31（3）：216-218.

[2]Nearchou AC.The effect of various operators on the genetic search for large scheduling problems[J].International journal of production economics，2004，（88）：191-203.

[3]陳群賢.近似粒子群算法在Flow-shop調(diào)度中的應(yīng)用.上海電機(jī)學(xué)院學(xué)報(bào)，2006，9（2）：16-18.