夏俊紅， 鄭建國

(東華大學 旭日工商管理學院， 上海 200051)

柔性車間調度[1](Flexible Job-shop Scheduling Problem， FJSP)突破機器約束和加工過程路線固定的限制， 每道工序可在一臺或多臺機器上進行加工. 目前車間調度研究熱點仍把最小最大完工時間作為主要指標， 這樣會導致庫存積壓等情況， 但如果工件拖期完工會打亂生產節(jié)拍， 出現缺件等情況的發(fā)生， 任何提前或拖期(E/T)都會產生相應的懲罰成本. 因此柔性車間E/T調度相比于傳統(tǒng)作車間調度更具有實際意義.

過去研究中， 科學家們嘗試各種方法， 比如一些傳統(tǒng)的確定性算法， 分值界定算法， 但是隨著工件和機器數量的增加， 問題變得越來越復雜， 這些確定性算法無法滿足問題的需求. 因此， 很多學者開始引入不確定性算法， 比如遺傳算法， 粒子群算法等等. 劉愛軍等[2]利用改進的多種群遺傳算法解決柔性車間調度問題； 蔡霞等[3]提出基于浮點型編碼策略的差分多目標進行柔性車間調度優(yōu)化； 侯曉莉等[4]及馬立波等[5]將粒子群算法引進柔性車間問題并求解； 薛宏全等[6]利用改進的蟻群算法求解柔性車間問題； 欒飛等[7]基于PST層次結構的改進GA求解柔性車間調度問題； 徐華等[8]利用新型離散蝙蝠算法求解柔性流水車間調度問題； 傅衛(wèi)平等[9]利用改進的遺傳算法求解柔性車間調度. 隨著群智能發(fā)展， 出現一種模擬螢火蟲發(fā)光求偶覓食行為的螢火蟲算法[10](Glowworm Swarm Optimization， GSO). 目前，利用GSO算法解決調度問題尚在探索階段， 還未具體應用到柔性車間E/T調度問題中.

綜上所述， GSO算法還未應用于柔性車間E/T調度問題中， 針對問題特點， 提出改進的GSO算法， 算法設計了一種具有貪婪思想的編碼策略， 采用自適應選擇策略， 使步長自適應， 提高算法精度； 引入 POX 交叉、鄰域交換和反序排序方法提高算法局部和全局尋優(yōu)能力， 并利用貪婪思想， 提高算法的收斂速度.

1 柔性作業(yè)車間E/T調度問題模型

1.1 問題描述

柔性車間調度是傳統(tǒng)作業(yè)車間調度的擴展， 在原有問題基礎上， 增加機器資源可選擇這一環(huán)節(jié)， 在加大了調度靈活性的同時， 也加大了求解難度. 柔性車間調度問題可以簡單描述為在給定資源條件下， 合理安排工件加工順序、分配機器， 完成工件加工任務. 具體描述如下:

n個工件在m臺機器上進行加工， 每個工件有一道或多道工序， 每道工序可在不同機器進行加工， 但不同機器加工同一工序的時間不一樣. 調度任務的目標:首先確定加工每道工序的機器， 其次確定每個工件在每臺機器上的加工順序， 從而優(yōu)化某些生產指標， 比如最普遍的性能指標為最小最大完工時間. 完工時間是指某個工件開始進入第一道工序到最后一道工序的完成時間， 所有工件的完成時間中最長的那個即位最大完工時間且使最大完工時間最小化.

1.2 模型假設

假設1. 同一時刻， 一臺機器只能加工一個工件， 即一個工件只能選擇一臺機器， 不可同時選擇多臺機器.

假設2. 同一時刻， 一個工件只能在一臺機器上進行加工， 且不被間斷.

假設3. 同一工件， 工序之間有先后順序約束； 不同工件的工序之間沒有先后順序約束.

假設4. 每個工件的工序有特定加工順序.

假設5. 每個工件的準備時間為0.

假設6. 不同工件具備相同的優(yōu)先級， 即每個時刻，每個都有可能被加工.

假設7. 加工過程中， 裝載、卸載時間忽略不計.

1.3 變量及參數說明

N: 表示工件總個數；

M: 表示機器總個數；

J={1， 2，…，j}: 表示需要加工的工件的集合；

K={1， 2，…，k}: 表示機器的集合；

Xijk: 表示工件j的工序i是否在機器k上進行加工， 取值為 0 或 1；

tijk: 表示工件j的工序i在機器k上的需要加工的時間；

bijk: 表示工件j的工序i在機器k上的開始加工時間；

tj: 工件j的完工時間；

dj: 工件j的交貨期；

rj: 工件j的提前懲罰系數；

wj: 工件j的拖期懲罰系數.

1.4 模型建立

(1) 目標函數

(2) 約束條件

工序約束: 同一工件的工序之間有先后約束.

機器約束: 同一臺機器在同一時刻只能加工一道工序.

連續(xù)性約束: 工序在加工過程中不能中斷.

工件約束: 同一時刻， 每個工件只能在一臺機器上進行加工.

2 改進GSO算法

2.1 基本螢火蟲算法

螢火蟲算法作為一種模仿自然界中螢火蟲的發(fā)光特性的隨機優(yōu)化算法， 在算法中舍棄了螢火蟲其他的生物意義， 只利用其發(fā)光特性在其搜索領域尋找伙伴，并向領域內位置較優(yōu)的螢火蟲伙伴移動， 從而實現位置的更新.

在該算法中， 螢火蟲彼此吸引的原因主要取決于兩個因素: 自身的亮度跟吸引度. 其中螢火蟲的發(fā)光亮度取決于螢火蟲當前所在的位置， 位置越好螢火蟲的亮度越高， 即目標值越佳. 吸引度跟亮度有關， 亮度越高吸引力越大. 如果發(fā)光亮度相同， 則螢火蟲會隨機移動. 亮度與吸引度與螢火蟲之間的距離成反比， 都隨著距離的增加而減小.

(1) 熒光素的更新

螢火蟲的熒光素大小的決定了螢火蟲在搜索空間的位置， 此外熒光素的大小還與上一代迭代的螢火蟲的熒光素揮發(fā)有關系， 如式(6)所示:

(2) 移動的概率計算

(3) 個體位置更新

經過上一步驟后， 從滿足了集合Ni(t)的兩個條件個體中選取了同伴個體j， 位置更新按照式(8)如下:

其中，s表示的移動步長代表i到j的笛卡爾距離.

(4) 決策半徑更新

位置更新以后， 根據移動后的位置周圍鄰居個數，來更新個體的決策半徑， 具體如式(9)所示:

其中，rs表示個體的最大決策半徑，nt調整螢火蟲鄰域集合大小的參數，是調整螢火蟲動態(tài)感知范圍大小的參數，·求集合元素的個數.

2.2 編碼解碼策略

為使螢火蟲算法適用于柔性車間調度問題， 設計一種貪婪式編碼策略. 設有n個工件， 所有工件的工序總數為m，那編碼由2m個整數組成的數組A， A[0]～A[m]表示工序加工順序， A[m+1]～A[2m]表示機器選擇順序.數組A的后半部分是利用貪婪思想進行機器選擇， 以保證解碼產生的調動為主動調度， 每道工序調用可加工的機器. 表1為柔性車間調度問題示例.

表1 處理時間

編碼過程如下所示:

前半部分表示工序， 根據表1示例， 隨機生成長度為 6， 由整數 1， 2， 3 組成的數組， 得到個體的前半部， 如圖1所示.

圖1 工序加工順序

根據所得個體前半部分的整數順序， 解碼得到工件加工順序為O31-O11-O12-O21-O32-O22-O23-O33.

后半部分表示機器選擇順序， 本文利用貪婪思想進行機器選擇， 以保證解碼產生的調動為主動調度， 每道工序調用可加工的機器. 因此根據前半部分已得的工件加工順序選擇機器. 根據表1， 工序O31可由兩臺機器進行加工， 則編碼為隨機取1或2的整數. 如此得到得體的后半部分， 如圖2所示.

圖2 機器選擇順序

根據所得個體后半部分的整數順序解碼得到各工序加工機器， O31由第一臺機器進行加工， O11由第三臺機器進行加工等.

將工序加工順序編碼與機器選擇部分編碼合并，得到整個個體， 個體的前半部分表示工序編碼， 個體的后半部分表示機器編碼， 整個個體合并如圖3所示.

圖3 整個個體

2.3 自適應選擇策略

生物的免疫系統(tǒng)是機體執(zhí)行免疫應答和免疫功能的重要系統(tǒng)， 它能夠識別和清除外來的抗原體和內在的腫瘤細胞和癌細胞等作用. 因免疫算法較為復雜， 為避免復雜性， 本文選取幾個重要的免疫操作， 摒棄復雜的交叉變異. 本文通過加入免疫算法中的抗體、親和度， 來自適應調整步長參數.

在初始GSO算法中， 步長固定， 容易導致算法陷入局部最優(yōu)解. 因此步長因根據每次迭代的結果， 不斷調整其大小， 以便快速和準確的找到全局最優(yōu)值， 比如在算法的迭代前期， 步長的變化需要大一些， 這樣可以加快迭代速度， 在迭代后期， 步長需要很小， 目的是為了能準確的找到局部最優(yōu)值. 因此將GSO算法和生物免疫搜索系統(tǒng)進行一個協(xié)同進化， 最終為每個個體找到最優(yōu)步長.

首先為每個個體在一個合適的范圍內隨機分配抗體和步長， 根據算法的迭代情況計算每個抗體的親和度， 并根據下式計算親和度:

在每次迭代過程中， 一定百分比的抗體被一些新的抗體代替， 根據下式更新抗體.

其中，M=2*NP，Q=|0.2*NP|，k=1， 2，…， 2*NP.

根據一個隨機的概率在抗體中選取步長參數， 并根據下式更新步長參數.

2.4 位置更新策略

位置更新過程中， 對三部分個體進行更新， 第一部分是個體自身i， 根據標準螢火蟲算法進行更新. 第二部分在個體i的鄰域范圍內， 并且滿足適應度值優(yōu)于個體i的適應度值的個體， 采取POX交叉. 第三部分， 其余個體采用鄰域交換或反序排序方法， 對個體進行位置更新.

(1) 第一部分

為使螢火蟲算法適用于柔性車間調度問題， 針對問題特點， 對螢火蟲的位置更新策略進行重新設置. 在標準螢火蟲的位置更新的基礎上重新排序， 首先針對個體的前半部分的工序進行重新排序， 后半部分在前半部分的基礎上重新分配機器. 根據標準GSO算法位置更新公式得到非整數序列， 因此需對此序列進行優(yōu)化， 使之符合柔性車間調度的實際狀況. 首先選擇比自己亮的個體， 因為步長參數的固定會使算法陷入局部最優(yōu)， 因此上一小節(jié)利用自適應選擇策略對步長參數進行自適應. 標準螢火蟲算法位置更新結果如圖4所示.

圖4 標準GSO位置更新結果

針對個體i的新位置的前半部分設置新的變化策略， 對于位置未發(fā)生變化的部分不進行變動， 對于位置發(fā)生改變的部分按大小進行排序即 0.87＜2.06＜3.06， 對新個體i的第1， 3， 6位置根據剛剛排序的大小所對應的位置， 將位置上的數字進行一一交換， 交換方式如圖5所示.

圖5 標準GSO位置更新后的改動過程

將個體的前半部分更新整理后， 對個體的后半部分利用貪婪編碼策略進行重新編碼， 最終得到個體如圖6所示.

圖6 標準GSO位置更新后的改動的結果

(2) 第二部分

隨機選擇兩個工件， 比如工件2和3， 對它們的工序進行整體POX交叉操作， 交叉過程如圖7所示.

圖7 個體前半部分POX交叉操作

POX交叉后并沒有工件整體的工序加工順序發(fā)生變化， 因此只需根據工序變化的位置進行POX交叉，交叉后得到機器選擇順序仍符合貪婪編碼策略. 機器編碼交叉過程如圖8所示.

圖8 個體后半部分POX交叉操作

為加快算法收斂速度， 提高算法性能， 引入貪婪思想， 若POX交換后的個體小于原的適應度值， 則選擇交換后的個體， 否則選擇原個體.

(3) 第三部分

為提高種群的多樣性， 提高算法全局搜索能力， 進行鄰域插入， 或反序排序. 其具體操作如下所示.

1) 鄰域插入. 隨機選擇兩個位置 1， 2， 將位置 2 基因插入位置1 基因的后面， 位置1與位置2間基因均向后移動. 其具體操作如圖9所示.

圖9 個體前半部分鄰域插入

2) 反序排序. 隨機選擇兩個位置 1， 2， 將位置 1 和位置2之間的基因進行反序排序. 其具體操作如圖10所示.

圖10 個體前半部分反序排序

將個體的前半部分更新整理后， 對個體的后半部分利用貪婪編碼策略進行重新編碼. 為加快算法收斂速度， 提高算法性能， 引入貪婪思想， 交換后的個體小于原個體的適應度值， 則選擇交換后的個體， 否則選擇原個體.

2.5 改進的GSO算法的流程圖

圖11 改進的 GSO 算法的流程圖

3 實驗仿真

3.1 基準算例仿真

實驗環(huán)境為Core i5 M480@2.67 Hz的CPU， 內存為4 GB RAM； 環(huán)境為Win10操作系統(tǒng)和Matlab 2016a.

為驗證本文算法有效性， 采用Kacem測試算例Brandimarte問題測試算例， 其中Kacem測試算例包括8×8， 10×10， 15×10 三個柔性車間調度問題， 將本文算法與Chiang[11]提出的定位與控制遺傳算法(ALCGA)， Xia等[12]提出的混合模擬退火與粒子群算法(PSO+SA)， 吳秀麗等[13]提出的改進細菌覓食算法(IBFOA)， 與馬佳等[14]改進的人工免疫算法 (AIA)，進行對比. 各算法最優(yōu)統(tǒng)計結果如表2所示.

表2 Kacem實例最優(yōu)解統(tǒng)計結果

從表2可知， 本文算法的求解結果小于或等于最新的其他四個算法的求解結果， 證明了本文算法在同類算法中的優(yōu)越性能. 圖12為問題求解10×10的最優(yōu)甘特圖.

圖12 10×10求解結果

對于10個測試Brandimarte算例將本文的離散螢火蟲算法與吳秀麗等[13]提出的改進細菌覓食算法(IBFOA)、田旻[15]提出的分層混合遺傳算法(HHGA)、Xing等[16]提出的改進的蟻群算法(KB-ACO)進行對比分析. 各算法最優(yōu)統(tǒng)計結果如表3所示.

表3 Brandimarte問題統(tǒng)計結果

從表3可以看出，在求解上述10個問題中， 本文算法得到的結果80%優(yōu)于或等于KB-ACO得到的結果，70%優(yōu)于或等于IBFOA得到的結果， 80%優(yōu)于或等于HHGA的結果. 實驗結果表明， 和上述已有算法相比， 本文算法在求解FJSP問題具有一定的優(yōu)越性.

3.2 實例仿真

以某公司的柔性制造單元調度為例進行仿真， 制造單元有3臺加工設備，加工8種零件， 每種零件包括3道工序， 零件類型、交貨期、加工時間表如表4所示，根據企業(yè)預算和合同條款懲罰， 取提前懲罰系數為0.3，拖期懲罰系數為0.7. 經過計算得到每個工件的完工時間、以及每個工件的懲罰成本， 如表5所示， 函數值變化曲線如圖13所示， 最佳調度甘特圖如圖14所示.

表4 工件加工信息

表5 工件完工時間、懲罰成本

圖13 函數值變化曲線

圖14 最優(yōu)調度甘特圖

為進一步驗證本文提出的調度算法在求解柔性車間E/T調度上的優(yōu)越性， 與傳統(tǒng)的離散算法GA， 與改進的NSGA-II算法進行對比分析， 算法的種群數目最最大迭代次數與本文算法相同， 得到的函數變化曲線與本文算法求得的變化曲線進行對比， 如圖15所示.

由圖15可看出， 本文算法迭代75次可找到最優(yōu)值， 算法NSGA-II迭代110次找到最優(yōu)值， 算法GA迭代490次達到最優(yōu)值， 因此本文算法較其他兩種算法收斂速度更快， 且本文算求解結果更優(yōu). 因此本文提出的改進的GSO算法在求解柔性車間E/T調度方面具有一定的有效性.

4 結束語

針對機器資源和加工路線可選擇情況下的柔性車間調度， 以最小最大完工時間和時間懲罰成本為目標建立柔性車間模型. 根據問題特點， 提出一種改進的GSO算法， 算法設計了一種具有貪婪思想的編碼策略，一個螢火蟲個體表示工序加工順序和工序加工位置；采用自適應選擇策略， 使步長自適應， 提高算法精度；引入POX交叉、鄰域交換和反序排序方法提高算法局部和全局尋優(yōu)能力， 并利用貪婪思想， 提高算法的收斂速度. 通過實例仿真和算法比較驗證算法性能， 實驗結果表明改進的GSO求解柔性車間調度問題的有效性. 本文不足之處， 模型考慮因素較少， 之后將進一步優(yōu)化算法性能， 嘗試將本文算法用于機器故障情況下柔性車間調度問題.

圖15 函數曲線對比圖