楊劍勇

摘 要： 傳統(tǒng)基于精確算法求解柔性作業(yè)車間調(diào)度問題時(shí)，僅能對(duì)小量柔性作業(yè)車間調(diào)度問題實(shí)施求解，具有一定的局限性。針對(duì)該問題，采用改進(jìn)捕魚算法求解柔性作業(yè)車間調(diào)度問題，在分析經(jīng)典捕魚算法存在弊端的基礎(chǔ)上，提出改進(jìn)捕魚算法，融入漁夫的自身感知性能以及捕魚經(jīng)驗(yàn)，分析魚濃度高的區(qū)域，并不斷趨向該區(qū)域區(qū)間，通過概率分布原理對(duì)漁夫撒網(wǎng)方案實(shí)施優(yōu)化。分析求解柔性作業(yè)車間調(diào)度問題的描述以及性能指標(biāo)，將性能指標(biāo)作為改進(jìn)捕魚算法的輸入，通過運(yùn)算獲取最佳的調(diào)度結(jié)果。實(shí)驗(yàn)結(jié)果說明，所提算法具有較高的調(diào)度效率和精度，并且確保作業(yè)車間能耗的最小化。

關(guān)鍵詞： 改進(jìn)捕魚算法； 求解； 柔性作業(yè)； 車間； 調(diào)度問題

中圖分類號(hào)： TN911.1?34； TP301.6 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2017）21?0128?04

Improved fishing algorithm for solution of flexible job?workshop scheduling problem

YANG Jianyong

（School of Computer Science and Engineering， Changshu Institute of Technology， Changshu 215500， China）

Abstract： The traditional precise algorithm for the solution of the flexible job?shop scheduling problem can only solve the small amounts of the flexible job?shop scheduling problem， and has a certain limitation. In order to eliminate the above problems， the improved fishing algorithm is used to solve the flexible job?shop scheduling problem. On the basis of analyzing the shortcomings of the classical fishing algorithm， the improved fishing algorithm is put forward， and the perceived performance and fishing experience of the fisherman itself are integrated into it to analyze the area with high concentration of fish， and tend to the area range constantly. The principle of probability distribution is used to optimize the net casting scheme of fisherman. The description of the flexible job?workshop scheduling problem solution and performance index are analyzed. The performance index is taken as the input of the improved fishing algorithm， and then operated to get the optimal dispatching result. The experimental results show that the proposed algorithm has high scheduling efficiency and precision， and can ensure the minimum energy consumption of the job workshop.

Keywords： improved fishing algorithm； solution； flexible job； workshop； scheduling problem

0 引 言

以前的車間調(diào)度過程中各道工序僅通過一臺(tái)明確的機(jī)器進(jìn)行加工，柔性作業(yè)車間調(diào)度問題能夠解決該種資源約束，使得不同工序在一臺(tái)或多臺(tái)機(jī)器中進(jìn)行加工，提高了可行解的檢索區(qū)域，使得作業(yè)車間調(diào)度效率提高[1]。因此，求解柔性作業(yè)車間的高質(zhì)量調(diào)度問題成為研究的重點(diǎn)。傳統(tǒng)方法主要采用精確算法求解柔性作業(yè)車間調(diào)度問題，但是該方法僅能對(duì)小量柔性作業(yè)車間調(diào)度問題實(shí)施求解，具有一定的局限性。針對(duì)該現(xiàn)象，本文采用改進(jìn)捕魚算法求解柔性作業(yè)車間調(diào)度問題，實(shí)現(xiàn)調(diào)度的高效率和高精度，提高作業(yè)車間產(chǎn)量和質(zhì)量。

1 改進(jìn)捕魚算法求解柔性作業(yè)車間調(diào)度

1.1 基本捕魚算法

基于漁夫捕魚行為以及習(xí)慣的啟發(fā)，采用依據(jù)模擬漁夫捕魚的智能優(yōu)化算法，設(shè)置漁夫捕魚作業(yè)區(qū)的范圍是[D=D1×D2×…×Dn，]其用于描述作業(yè)車間控制變量組的取值域，[K]個(gè)漁夫用于描述[K]個(gè)控制變量組，各漁夫位置的狀態(tài)量是[X=（x1，x2，…，xn）]，其用于描述一個(gè)控制變量組，[D]內(nèi)魚的密度函數(shù)是[f（X）]，用于描述求解靜態(tài)電壓穩(wěn)定裕度的目標(biāo)函數(shù)[λmax，]將獲取魚密度最高以及所處位置過程看成是獲取最高[λmax]和狀態(tài)變量最佳組合的過程。

收縮檢索，通過[m]次移動(dòng)搜索后[2]，漁夫[i]將即刻位置當(dāng)成中心塑造方體，獲取撒網(wǎng)點(diǎn)集：

[Ωim=Xim=（ti1，ti2，…，tin）tij∈ximj-l-j，ximj，ximj+l+j， j=1，2，…，n] （1）endprint

若[f（Xim）=maxXi∈Ωimf（Xi）

[Ωim+1=Xim+1=（ti1，ti2，…，tin）tij∈ximj-l-j，ximj，ximj+l+j， j=1，2，…，n] （2）

式中：[l-j=αl-j，l+j=αl+j，0<α<1，][α]表示方體邊長的收縮系數(shù)。

若在收縮搜索過程時(shí)獲取最高魚密度位置，將漁夫位置當(dāng)成中心，塑造新方體實(shí)施搜索，同時(shí)運(yùn)行收縮搜索。設(shè)置搜索閾值確保搜索過程順利進(jìn)行。

1.2 改進(jìn)捕魚算法

上述分析的基本捕魚算法過程中的漁夫缺乏對(duì)自身以及環(huán)境的感知能力，僅憑對(duì)方體的運(yùn)算變換撒網(wǎng)位置，捕魚效率以及精度較低，因此采用改進(jìn)捕魚算法對(duì)基本捕魚算法進(jìn)行改進(jìn)[4]，融入漁夫的自身感知性能以及捕魚經(jīng)驗(yàn)，分析魚濃度高的區(qū)域，并不斷趨向該區(qū)域區(qū)間，通過概率分布原理改進(jìn)漁夫撒網(wǎng)方案，提高捕魚效率和精度。

設(shè)置[t]時(shí)刻的全局最佳位置以及最優(yōu)點(diǎn)是[G（t）=][（g1（t），g2（t），…，gn（t））]以及[Bi（t）=bi1（t），bi2（t），…，bin（t）]，該種情況下第[i]個(gè)漁夫的位置是[Xi（t）=xi1（t），xi2（t），…，xin（t），]若存在[Xi≠G（t），]則該漁夫采用[N]個(gè)探測點(diǎn)的方案為：

[Pij（t+1）=Xi（t）+rjIβjQj（t+1）Qj（t+1）] （3）

[rj=（1-βj）G（t）-X（t）G（t）-X（t）] （4）

式中：[j=1，2，…，N；][i]表示撒網(wǎng)半徑；[Qj（t+1）]表示隨機(jī)數(shù)。

基于概率分布原理可得，若[Xi=G（t），]則該漁夫采用[N]個(gè)探測點(diǎn)的方案是：

[Pij（t+2）=Xi（t+1）+rjIQj（t+2）Qj（t+2）] （5）

設(shè)置[Pibest（t+1）=bestPij（t+1）：1≤j≤N，]如果[Pibest（t+1）]比[Xi（t）]好，則第[i]個(gè)漁夫?qū)⒆儞Q到位置[Pibest（t+1）]，同時(shí)存在[Xi（t+1）=Pibest（t+1）]。如果[Pibest（t+1）]比[Xi（t）]差，則當(dāng)[Xi（t）=G（t）]時(shí)第[i]個(gè)漁夫的運(yùn)行捕魚位置固定，否則其位置調(diào)整規(guī)范是：

[Xij（t+1）=Xij（t）+rbij（t）-xij（t）+r2?exp-gj（t）-xij（t）gj（t）-xij（t）gj（t）-xij（t）] （6）

2 求解柔性作業(yè)車間調(diào)度問題

2.1 柔性作業(yè)車間調(diào)度問題描述

柔性作業(yè)車間調(diào)度問題描述：若作業(yè)車間存在[n]個(gè)待加工的工件，工件集是[J={J1，J2，…，Jn}]。工件[Ji（i=1，2，…，n）]包括[ni]個(gè)工序，并且其加工順序是確定的，工件[Ji]中的第[j]個(gè)工序是[Oij，]存在[m]臺(tái)可進(jìn)行加工的機(jī)器，機(jī)器集是[M=M1，M2，…，Mm]；工序[Oij]能夠在任意候選機(jī)器中加工，候選機(jī)器集是[Mij，]且有[Mij?M，]工序在各態(tài)機(jī)器中的加工時(shí)間事先已經(jīng)設(shè)置好，并且這些時(shí)間存在一定的差異。作業(yè)車間調(diào)度的目的是對(duì)各工序選擇加工的機(jī)器以及機(jī)器中的加工順序?qū)嵤┱{(diào)控[5]，得到確保目標(biāo)函數(shù)最高的調(diào)度策略。加工時(shí)應(yīng)確保某時(shí)刻一臺(tái)機(jī)器僅可加工一個(gè)工序，某時(shí)刻一個(gè)工序僅能在一臺(tái)機(jī)器中進(jìn)行，不同工件工序不相交，加工過程中的工序無法中斷，全部工件具有一致的優(yōu)先級(jí)。

基于候選機(jī)器集將柔性作業(yè)車間調(diào)度問題劃分成局部柔性作業(yè)車間調(diào)度問題和全部柔性作業(yè)車間調(diào)度問題，其中前者要求至少存在一個(gè)工序的可選擇加工機(jī)器集為局部機(jī)器[6]，則有[Mij?M；]而后者要求作業(yè)車間調(diào)度過程中各工序都能夠采用隨機(jī)的一臺(tái)機(jī)器實(shí)施加工，則有[Mij=M，]量子柔性作業(yè)車間調(diào)度問題的實(shí)例分別如表1和表2所示。實(shí)際生產(chǎn)時(shí)對(duì)機(jī)器選擇過程中受到相關(guān)條件的制約，局部柔性作業(yè)車間調(diào)度問題的應(yīng)用價(jià)值更高，但是其具有較高的檢索范圍和運(yùn)算量。

表1中描述的部分柔性作業(yè)車間調(diào)度問題的加工機(jī)器以及加工時(shí)間表共存在2個(gè)工件以及4臺(tái)機(jī)器，其中“—”用于描述該工序無法采用相關(guān)的機(jī)器加工。

2.2 柔性作業(yè)車間調(diào)度問題性能指標(biāo)和求解

求解2.1節(jié)分析的部分柔性作業(yè)車間調(diào)度問題以及全部柔性作業(yè)車間調(diào)度問題過程中存在較多的性能評(píng)估指標(biāo)，先設(shè)置柔性作業(yè)車間中工件數(shù)和機(jī)器數(shù)是[n]和[m，][ni]是[Ji]的工序數(shù)，工件[Ji]的完成時(shí)間是[Ci，]工序[Oij]在[Mk]中的加工時(shí)間是[pijk，][xijk=1]或0用于描述工序[xijk=1]在和不在機(jī)器[Mk]中加工。

求解柔性作業(yè)車間調(diào)度問題采用的性能指標(biāo)如下：

（1） 最高完工時(shí)間最低。完工時(shí)間是各工件的全部工序都加工完成耗費(fèi)的時(shí)間，最后被加工工序的完成時(shí)間是最高完工時(shí)間，其描述了產(chǎn)品的生產(chǎn)時(shí)間的最小值。最高完工時(shí)間最低是評(píng)估柔性作業(yè)車間調(diào)度方案優(yōu)劣的基本指標(biāo)[7]，其目標(biāo)函數(shù)為：

[f1=minmax1≤i≤n（Ci）] （7）

（2） 總機(jī)器負(fù)載最低。總機(jī)器負(fù)載是全部機(jī)器加工時(shí)間的匯總，工序在不同候選機(jī)器中的加工時(shí)間存在一定的差異，因此不同柔性作業(yè)車間調(diào)度策略中總機(jī)器負(fù)載與不同工序選擇加工機(jī)器相關(guān)[8]，若最高完工時(shí)間一致，則選擇總機(jī)器負(fù)載最低的調(diào)度指標(biāo)，其目標(biāo)函數(shù)是：

[f2=mink=1mi=1nj=1njpijkxijk] （8）

（3） 最高機(jī)器負(fù)載最小。機(jī)器負(fù)載是機(jī)器在總體加工時(shí)的全部加工時(shí)間，部分柔性作業(yè)車間調(diào)度以及全部柔性作業(yè)車間調(diào)度過程中，不同機(jī)器負(fù)載同工序以及加工機(jī)器相關(guān)，為了增強(qiáng)調(diào)度策略質(zhì)量，應(yīng)確保不同機(jī)器負(fù)載的均衡性，則目標(biāo)函數(shù)為：

[f3=minmax1≤k≤mi=1nj=1njpijkxijk] （9）

（4） 提前/拖期最低。實(shí)際柔性作業(yè)車間調(diào)度過程中，生產(chǎn)任務(wù)提前以及滯后完成需要耗費(fèi)相應(yīng)的成本，在求解柔性作業(yè)車間調(diào)度問題過程中重復(fù)分析交貨期問題[9]?；谧罡咄旯r(shí)間以及交貨期的差值描述工件交貨期的提前/拖期時(shí)間，工件[Ji]的交貨期和完工時(shí)間為[di]和[Ci，]工件的最高提前時(shí)間是[Ei=maxdi-Ci，0]，最高拖延時(shí)間是[Ti=maxCi-di，0]，則目標(biāo)函數(shù)為：

[f4=minmax1≤i≤n（Ei）] （10）

[f5=minmax1≤i≤n（Ti）] （11）

基于這些指標(biāo)，將這些指標(biāo)作為改進(jìn)捕魚算法[t]時(shí)刻的全局最佳位置以及最優(yōu)點(diǎn)，通過改進(jìn)捕魚算法獲取[N]個(gè)探測點(diǎn)的方案，也就是最佳的捕魚方案，完成柔性作業(yè)車間調(diào)度問題的優(yōu)化求解。

3 實(shí)驗(yàn)分析

3.1 調(diào)度效果測試

實(shí)驗(yàn)為了檢測本文提出的基于改進(jìn)捕魚算法求解柔性作業(yè)車間調(diào)度的性能，算法通過軟件VS2015、操作系統(tǒng)Windows 10，通過C++編程實(shí)現(xiàn)，實(shí)驗(yàn)采用文獻(xiàn)[7]中的數(shù)據(jù)實(shí)施分析，將8×8柔性作業(yè)車間調(diào)度問題作為算例求解生產(chǎn)周期。8×8實(shí)例中的機(jī)器和工件數(shù)都是8，各工件存在3～4個(gè)工序，是包括27個(gè)工序的部分柔性車間作業(yè)調(diào)度問題。設(shè)置人工魚群的規(guī)模為10，初始視野是工件數(shù)和工序數(shù)的乘積，擁擠度閾值是初始視野的[14]，最高迭代次數(shù)是5，分別采用本文算法和基本捕魚算法實(shí)施10次運(yùn)算，獲取的甘特圖如圖1，圖2所示。

分析圖1，圖2可得，本文算法的尋優(yōu)性能以及精確度高于基本捕魚算法，主要是由于本文算法融入漁夫的自身感知性能以及捕魚經(jīng)驗(yàn)，分析魚濃度高的區(qū)域，并不斷趨向該區(qū)域區(qū)間，通過概率分布原理對(duì)漁夫撒網(wǎng)方式實(shí)施優(yōu)化，極大增強(qiáng)了算法的尋優(yōu)精確度。

分析圖1能夠看出，本文算法獲取的最高完工時(shí)間最低的周期是14，實(shí)驗(yàn)對(duì)比分析不同方法調(diào)度下的作業(yè)車間生產(chǎn)周期，結(jié)果如表3所示，能夠看出本文算法取得的結(jié)果最優(yōu)，縮短了生產(chǎn)周期。

實(shí)驗(yàn)采用不同算法對(duì)柔性作業(yè)車間調(diào)度Kacem基準(zhǔn)函數(shù)實(shí)施求解。該函數(shù)由10×10實(shí)例構(gòu)成，其中10×10實(shí)例中的機(jī)器和工件數(shù)都是10，各工件存在3個(gè)工序，是包括30個(gè)工序的全部柔性車間作業(yè)調(diào)度問題。采用本文算法實(shí)施10次運(yùn)算，獲取各基準(zhǔn)函數(shù)的最佳解甘特圖如圖3所示。實(shí)驗(yàn)統(tǒng)計(jì)不同算法對(duì)Kacem基準(zhǔn)函數(shù)的檢測結(jié)果，見表4。其中的目標(biāo)函數(shù)是2.2節(jié)分析的柔性作業(yè)車間的調(diào)度相關(guān)性能指標(biāo)。

分析圖3和表4可得，對(duì)于不同目標(biāo)函數(shù)，本文算法的檢測結(jié)果都優(yōu)于其他算法，對(duì)10×10算例的平均解比基本捕魚算法佳，實(shí)現(xiàn)了柔性作業(yè)車間的合理調(diào)度。

3.2 能耗測試

實(shí)驗(yàn)檢測本文算法對(duì)某模具車間實(shí)施調(diào)度的能耗情況，該模具作業(yè)車間包括14個(gè)工件，12臺(tái)機(jī)器，78道工序，實(shí)驗(yàn)將最小化完工時(shí)間以及最小化加工能耗當(dāng)成分析不同調(diào)度方法的指標(biāo)，其中12臺(tái)機(jī)器的能耗情況見表5。

模具車間中拋光工序采用人工進(jìn)行，則表5中的拋光機(jī)器[M′12]的能耗是0。

基于表5中描述的不同機(jī)器的能耗參數(shù)，采用本文算法和基本捕魚算法獲取目標(biāo)包含最小化最大完工時(shí)間[f1]、最小化加工能耗[f3，]結(jié)果如表6所示。

分析表6中的[f1]以及[f3]值，能夠看出本文算法獲取的[f1]以及[f3]值低于基本捕魚算法，說明本文算法在優(yōu)化求解柔性作業(yè)車間調(diào)度過程最小化最大完工時(shí)間以及最小化加工能耗兩個(gè)目標(biāo)過程具有較強(qiáng)的性能，能夠更好地確保作業(yè)車間能耗的最小化。

4 結(jié) 論

本文采用改進(jìn)捕魚算法求解柔性作業(yè)車間調(diào)度問題，將性能指標(biāo)作為改進(jìn)捕魚算法的輸入，獲取最優(yōu)的柔性作業(yè)車間調(diào)度結(jié)果，提高作業(yè)車間調(diào)度效率和精度。

參考文獻(xiàn)

[1] 吳秀麗，張志強(qiáng)，杜彥華，等.改進(jìn)細(xì)菌覓食算法求解柔性作業(yè)車間調(diào)度問題[J].計(jì)算機(jī)集成制造系統(tǒng)，2015，21（5）：1262?1270.

[2] 彭建剛，劉明周，張銘鑫，等.多目標(biāo)柔性作業(yè)車間調(diào)度算法研究綜述[J].中國機(jī)械工程，2014，25（23）：3244?3254.

[3] 程子安，童鷹，申麗娟，等.雙種群混合遺傳算法求解柔性作業(yè)車間調(diào)度問題[J].計(jì)算機(jī)工程與設(shè)計(jì)，2016，37（6）：1636?1642.

[4] 伍大清，鄭建國，邵明，等.求解柔性作業(yè)車間調(diào)度的動(dòng)態(tài)群智能優(yōu)化算法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2014，44（13）：48?57.

[5] 何春林.基于蟻群擁擠度躍階調(diào)整的交互信息調(diào)度算法[J].科技通報(bào)，2015，31（8）：69?71.

[6] 項(xiàng)響琴，張滬寅.漁夫捕魚優(yōu)化算法的認(rèn)知無線電頻譜分配[J].計(jì)算機(jī)工程與應(yīng)用，2014，50（6）：72?76.

[7] 李景洋，王勇，李春雷.自調(diào)整的捕魚策略優(yōu)化算法[J].計(jì)算機(jī)工程與科學(xué)，2014，36（5）：923?929.

[8] 周愷，紀(jì)志成.關(guān)于柔性作業(yè)車間調(diào)度問題的仿真研究[J].計(jì)算機(jī)仿真，2016，33（3）：282?287.

[8] 田娜，紀(jì)志成.改進(jìn)量子粒子群求解多目標(biāo)柔性作業(yè)車間調(diào)度[J].系統(tǒng)仿真學(xué)報(bào)，2015，27（12）：2948?2957.endprint