改進捕魚算法求解柔性作業(yè)車間調度問題

楊劍勇

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

關鍵詞： 改進捕魚算法； 求解； 柔性作業(yè)； 車間； 調度問題

中圖分類號： TN911.1?34； TP301.6 文獻標識碼： A 文章編號： 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 引 言

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

1 改進捕魚算法求解柔性作業(yè)車間調度

1.1 基本捕魚算法

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

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

[Ω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ù)。

若在收縮搜索過程時獲取最高魚密度位置，將漁夫位置當成中心，塑造新方體實施搜索，同時運行收縮搜索。設置搜索閾值確保搜索過程順利進行。

1.2 改進捕魚算法

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

設置[t]時刻的全局最佳位置以及最優(yōu)點是[G（t）=][（g1（t），g2（t），…，gn（t））]以及[Bi（t）=bi1（t），bi2（t），…，bin（t）]，該種情況下第[i]個漁夫的位置是[Xi（t）=xi1（t），xi2（t），…，xin（t），]若存在[Xi≠G（t），]則該漁夫采用[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）]表示隨機數(shù)。

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

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

設置[Pibest（t+1）=bestPij（t+1）：1≤j≤N，]如果[Pibest（t+1）]比[Xi（t）]好，則第[i]個漁夫將變換到位置[Pibest（t+1）]，同時存在[Xi（t+1）=Pibest（t+1）]。如果[Pibest（t+1）]比[Xi（t）]差，則當[Xi（t）=G（t）]時第[i]個漁夫的運行捕魚位置固定，否則其位置調整規(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è)車間調度問題

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

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

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

表1中描述的部分柔性作業(yè)車間調度問題的加工機器以及加工時間表共存在2個工件以及4臺機器，其中“—”用于描述該工序無法采用相關的機器加工。

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗分析

3.1 調度效果測試

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

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

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

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

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

3.2 能耗測試

實驗檢測本文算法對某模具車間實施調度的能耗情況，該模具作業(yè)車間包括14個工件，12臺機器，78道工序，實驗將最小化完工時間以及最小化加工能耗當成分析不同調度方法的指標，其中12臺機器的能耗情況見表5。

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

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

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

4 結 論

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

參考文獻

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

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

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

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

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

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

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

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

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