王 婷，毋 濤

(西安工程大學 計算機科學學院，陜西 西安 710048)

0 引 言

隨著中國經濟社會的發(fā)展，產品定制服務的出現(xiàn)，消費者個性化需求也日益凸顯，有一部分制造型企業(yè)開始采用訂單生產模式[1](make-to-order，MTO)，比如西裝定制、船舶制造。

在MTO生產模式中,訂單內不同的工件的交貨期不同，而制造型企業(yè)通常都是配備固定的車間、機器和人員，訂單調度決策往往受車間生產能力的制約。在這種情況下，這種決策往往會與實際生產有所偏差，造成計劃外的生產成本(如加班、外包)和拖期罰金，導致企業(yè)信譽受損，客戶滿意度降低。

為提高訂單交付的準時率,企業(yè)需要在有限產能下對訂單生產作業(yè)進行合理的計劃安排和調度，依據訂單產品的要求交期及時交付產品，履行合約。研究基于流水線車間的訂單調度問題可以有效提高企業(yè)的生產效率和競爭力，對于處于MTO生產模式的企業(yè)制定出合理有效的訂單調度決策，及時交付作業(yè)具有重要的研究意義。

長期以來，混合流水車間調度問題[2](hybrid flow shop scheduling problem，HFSP)被證明是一個經典的NP難題。目前，求解HFSP的算法主要包括遍歷式算法、構造型算法和智能化優(yōu)化算法，其中遍歷式算法可以求解出該類問題的精確解，但計算速度較慢；構造型算法在求解該類問題時運算速度較快，但算法結構復雜且通常無法求解出全局最優(yōu)解[3]；優(yōu)化算法有嚴格的理論基礎，能在短時間內解決問題的最優(yōu)或理想解。智能優(yōu)化算法[4]主要有混合螢火蟲算法(hybrid firefly algorithms，HFA)[5]、最佳覓食算法(optimal foraging algorithm，OFA)[6]、離散狼群算法(discrete wolf pack algorithm，DWPA)[7]、離散布谷鳥算法(cuckoo search，CS)[8]、改進蛙跳算法(shuffled frog leaping algorithm，SFLA)[9]、果蠅優(yōu)化算法(fruit fly optimization algorithm，F(xiàn)OA)[10]、混合魚群算法(hybrid artificial fish swarm algorithm，HAFSA)[11]、人工蜂群算法(artificial bee colony algorithm，ABC)[12]等等，已經廣泛應用于解決各種生產調度問題。

麻雀搜索算法[13](sparrow search algorithm，SSA)是一種新型的群智能優(yōu)化算法，主要是受麻雀的覓食行為和反捕食行為的啟發(fā)。針對SSA的研究表明，該算法在不同的搜索空間中具有良好的性能。在SSA的基礎上，文中提出了基于生產環(huán)節(jié)生產線兩段式麻雀搜索算法(two-vector sparrow search algorithm，T-SSA)，并將T-SSA實際應用于流水車間訂單調度問題中，驗證了該算法的有效性。

1 問題描述與建模

1.1 問題描述

1.2 模型的假設條件

(1)在初始時間(設置為0)，可以處理任何訂單任務。

(2)同一生產線的同一時間只能加工1件產品。

(3)不同的訂單任務之間沒有先后約束。

(4)在生產過程中，訂單前一個生產環(huán)節(jié)被處理完成后，會立即進入下一個生產環(huán)節(jié)進行處理；如果下一個生產環(huán)節(jié)生產線正在工作，則訂單進行等待。

(5)每兩個處理環(huán)節(jié)之間有足夠的緩存空間，允許產品在處理環(huán)節(jié)之間停留和等待。

(6)訂單調度過程為非搶占式調度。

(7)訂單任務中各生產環(huán)節(jié)的交貨時間和利潤值均為已知量(交貨時間從初始時間0開始計算)。

根據上述解釋和假設，研究的問題是：確定訂單的加工順序和各生產環(huán)節(jié)的生產線分配，從而使加權訂單完成時間最小化。

1.3 參數(shù)和變量說明

i：表示待加工工件編號。

j：表示待加工的生產環(huán)節(jié)序號。

k：表示每個生產環(huán)節(jié)的生產線編號。

Mj：第j個生產環(huán)節(jié)并行生產線的集合。

NMj：第j個生產環(huán)節(jié)并行生產線的數(shù)量。

MPij：工件i在第j個生產環(huán)節(jié)可用的生產線集合，MPij?Mj。

tijk：工件i的第j個生產環(huán)節(jié)在生產線k上的加工時間。

stijk：工件i的第j個生產環(huán)節(jié)在生產線k上的開始加工時間。

etijk：工件i的第j個生產環(huán)節(jié)在生產線k上的結束加工時間。

xijk：當工件i的第j個生產環(huán)節(jié)在生產線k上的加工時xijk=1；否則xijk=0。

rjk：第j個生產環(huán)節(jié)在生產線k上加工的第r個任務的工件編號。

Ti：工件i的各生產環(huán)節(jié)加工時間總和。

1.4 模型構建

根據問題描述，采用最小最大訂單完成時間為目標函數(shù)，可轉化為求解訂單內工件集的最小化完成時間，即一個工件完成時間的最小值，模型構建具體如下：

(1)

模型描述如下：

etijk≤sti(j+1)k*；i=1,2,…,n;j=1,2,…,s;

k∈MPij;k*∈MPi(j+1)

(2)

etijk=stijk+tijk；i=1,2,…,n;j=1,2,…,s;

k∈MPij

(3)

(4)

r=1,2,…,Njk-1

(5)

若rjk=i，則：

其中：

k∈MPij，k-∈MPi(j-1)，r=1,2,…,Njk

(6)

(7)

xijk∈{0,1},xijk-=1,?i,j,k,r

(8)

(9)

公式(1)是最小化工件完成時間的公式和目標函數(shù)；公式(2)表示在前一個生產環(huán)節(jié)完成后，才可以在下一個生產環(huán)節(jié)中進行加工；公式(3)表示每個工件的加工完成時間，其中每個生產環(huán)節(jié)的加工結束完成時間取決于該生產環(huán)節(jié)的開始時間和加工時長；公式(4)表示工件的每個生產環(huán)節(jié)只能選擇該生產環(huán)節(jié)的一臺生產線進行加工；公式(5)表示一條生產線同時只能加工一個工件；公式(6)表示當工件i是第j個生產環(huán)節(jié)在生產線k上處理的第r個任務時，生產環(huán)節(jié)開始時間取決于該工件前一個生產環(huán)節(jié)的結束時間與本生產線的前一任務結束時間；公式(7)表示每個工件的完成時間等于工件在最后一個生產環(huán)節(jié)中的完成時間；公式(8)為變量取值范圍；公式(9)表示每個工件每個生產環(huán)節(jié)加工時間的計算關系，即工件的總加工時間。

2 麻雀搜索算法(SSA)

麻雀搜索算法是一種基于麻雀覓食行為和反捕食行為的新型群體智能優(yōu)化算法，其仿生原理如下：

在麻雀覓食的過程中，將整個麻雀種群分為發(fā)現(xiàn)者和加入者兩種角色，疊加了偵查預警機制。發(fā)現(xiàn)者在種群中負責尋找食物并為整個麻雀種群提供覓食區(qū)域和方向，而加入者則是利用發(fā)現(xiàn)者來獲取食物。為了獲得食物，麻雀通?？梢圆捎冒l(fā)現(xiàn)者和加入者這兩種行為策略進行覓食。種群中的個體會監(jiān)視群體中其他個體的行為，并且該種群中的攻擊者會與高攝取量的同伴爭奪食物資源，以提高自己的捕食率。此外，當麻雀種群受到捕食者的攻擊時會做出反捕食行為。

SSA算法的具體流程見圖1。

圖1 麻雀搜索算法流程

Step1：初始化麻雀種群。

Step2：設置發(fā)現(xiàn)者規(guī)模，將種群分為發(fā)現(xiàn)者和跟隨者。

Step3：(發(fā)現(xiàn)者位置更新)當預警值小于安全值的時候，即覓食環(huán)境沒有捕食者時，發(fā)現(xiàn)者位置隨機更新；若預警值大于安全值，種群中的一些麻雀已經發(fā)現(xiàn)了捕食者，并向種群中其他麻雀發(fā)出了警報，此時所有麻雀都需要迅速飛到其他安全的地方進行覓食。更新方式如公式(10)：

(10)

上式表示種群中第t代中的第i個個體的第j維位置信息，α和Q是服從不同分布的隨機數(shù)。itermax、R2、ST分別表示最大迭代次數(shù)、預警值和安全值。

Step4：(跟隨者位置更新)若當前跟隨者處于十分饑餓的狀態(tài)，則需要飛往其他地方覓食，以獲得更多的能量，進行位置更新；否則，跟隨者是圍繞最好的發(fā)現(xiàn)者周圍進行覓食，期間也有可能發(fā)生食物爭奪，使自己成為生產者。更新方式如公式(11)：

(11)

其中，Xp是目前發(fā)現(xiàn)者的最優(yōu)位置，Xworst是當前全局最差的位置，n是種群大小。

Step5：(隨機選擇警戒者并更新位置)當任意麻雀意識到危險靠近時，它們會放棄當前的食物，即無論該麻雀是發(fā)現(xiàn)者還是跟隨者，都將放棄當前的食物而移動到一個新的位置，處于種群外圍的麻雀向安全區(qū)域靠攏，處于種群中心的麻雀則隨機行走靠近別的麻雀。更新規(guī)則如公式(12)：

(12)

其中，Xbest是當前的全局最優(yōu)位置，fg和fw分別是當前全局最佳和最差的適應度值，fi是當前麻雀的適應度值，ε、β、K是不同隨機常數(shù)。

Step6：判斷是否達到最大迭代次數(shù)，若達到，則輸出最優(yōu)適應度值，即所求問題的最優(yōu)解，否則轉到Step2。

3 基于T-SSA算法的模型求解

針對流水車間訂單調度問題采用基于生產環(huán)節(jié)和生產線的兩段式編碼方式來表示麻雀種群中麻雀的位置。應用其設計的初始化種群方式初始化種群，對麻雀的智能行為進行重新設計；則基于兩段式麻雀搜索算法的流水車間訂單調度問題的具體操作如下：

3.1 編碼方式

圖2 兩段式編碼示意圖

生產環(huán)節(jié)編碼的編碼長度為總生產環(huán)節(jié)數(shù)，基因位上的數(shù)字表示工件號，相同工件號出現(xiàn)的次數(shù)對應工件的第幾個生產環(huán)節(jié)。圖2中表示的工件加工順序為：工件3→工件2→工件3→工件1→工件2→工件3→工件2→工件1→工件1，其中每個工件出現(xiàn)三次，即每個工件有3個生產環(huán)節(jié)，比如基因位1上的數(shù)字3，表示工件3的第一個生產環(huán)節(jié)，基因位3上的數(shù)字3，表示工件3的第二個生產環(huán)節(jié)，諸如此類。

生產線編碼的編碼長度與生產環(huán)節(jié)編碼長度一致，也是總生產環(huán)節(jié)數(shù)，基因位上的數(shù)字代表前半段對應的生產環(huán)節(jié)可以選擇的生產線集合中的第幾條生產線。圖2中表示選擇的生產線順序依次為：生產線M1→生產線M2→生產線M3→生產線M1→生產線M4→生產線M6→生產線M5→生產線M4→生產線M6，基因位10位上的數(shù)字1表示工件3的第一個生產環(huán)節(jié)選擇生產線M1加工，基因位12上的數(shù)字1表示工件3的第二個生產環(huán)節(jié)上選擇生產線M3加工，以此類推。

[3,2,3,1,2,3,2,1,1,1,2,1,1,2,2,1,2,2]整個整數(shù)段表示一只麻雀個體。

3.2 種群初始化

在麻雀搜索算法中，多樣性好的初始解集能夠有效提高運算效率，擴大搜索范圍，避免局部收斂的情況發(fā)生?？紤]到兩段式編碼的特點，先采用隨機初始化方式產生足夠多的麻雀個體，確保種群的多樣性，然后使用輪盤賭選擇機制選取所需數(shù)量的初始個體，確保種群的質量。采用權重法計算個體被選取的概率，優(yōu)先選擇收益高、交期緊、訂單權重大的工件個體，工件選擇概率越大，個體越容易被選用。

(13)

(14)

3.3 適應度函數(shù)

以最小化最大訂單完成時間為目標函數(shù)求解流水車間訂單調度問題，主要思想是訂單內的每個工件的完成時間最優(yōu)，可以將該問題轉化為求解訂單內工件集的最小化最大完成時間為適應度函數(shù)，工件最大完成時間越小，表示個體的適應度值越好，即fitness=min{Cmax(P)}。

3.4 智能行為設計

文中以最小化最大訂單完工時間為目標函數(shù)來確定最優(yōu)訂單調度方案，即訂單中工件的生產環(huán)節(jié)排序和生產線選擇方案。結合HFSP的特性，對兩段式麻雀搜索算法中的具體定義如下：

(1)最優(yōu)最差麻雀選擇機制。

記錄第i只麻雀個體的適應度函數(shù)為Fiti，根據適應度值對麻雀個體進行排序，那么取全局最差適應度值為worseF=max(Fiti),i=1,2,…,n，worseF對應的全局最差位置為worseX；最優(yōu)麻雀個體對應的適應度值為bestF1=min(Fiti),i=1,2,…,nbestF1對應的全局最優(yōu)位置為bestX1。

(2)發(fā)現(xiàn)者移動機制。

根據設置麻雀發(fā)現(xiàn)者個體的比例PR，從種群中隨機取出發(fā)現(xiàn)者的個體數(shù)量。將隨機預警值R2與發(fā)現(xiàn)者警戒閾值ST進行比較，若R2

(3)跟隨者跟隨機制。

(4)偵察預警機制(警戒者)。

對意識到危險的個體稱為警戒者，并不代表出現(xiàn)了真正的捕食者。隨機指定個體j，取該個體的適應度值為Fitj，若Fitj>bestX1，表示此時的麻雀正處于種群的邊緣，極其容易受到捕食者的攻擊，位置跳躍性比較大，警戒者位置更新；若Fitj=bestX1，表明處于種群中間的麻雀意識到了危險，需要靠近其他的麻雀以此盡量減少它們被捕食的風險。

3.5 T-SSA算法迭代過程

根據智能行為設計的4大機制，可將使用T-SSA算法求解流水車間訂單調度問題的步驟概括如下：

Step1：初始化算法相關參數(shù)。設置種群的規(guī)模大小為pop，最大迭代次數(shù)為itermax，發(fā)現(xiàn)者比例為PR，偵查者比例為SD，預警值為R2，發(fā)現(xiàn)者警戒閾值為ST。

Step2：根據初始化方案進行種群初始化，確定麻雀個體的位置編碼。

Step3：依據設定的PR，將種群分為發(fā)現(xiàn)者和跟隨者。計算個體的適應度值Fiti，進行排序，并取出種群最優(yōu)位置bestX1和最差位置worseF對應的適應度值bestF1、worseF。

Step4：將預警值R2與警戒閾值進行比較，更新所有發(fā)現(xiàn)者位置，淘汰掉邊緣個體，迭代并計算發(fā)現(xiàn)者的適應度值。取出發(fā)現(xiàn)者的最優(yōu)位置bestX2對應的適應度值bestF2。

Step5：依據跟隨者的編號，判斷跟隨者的狀態(tài)，淘汰邊緣個體，跟隨者進行隨機位置更換，或者搶奪最優(yōu)發(fā)現(xiàn)者bestX2成為發(fā)現(xiàn)者。迭代，計算所有跟隨者的適應度值。

Step6：判斷隨機警戒者所處位置是否在種群中心，若處在中心，向最差位置worseF個體移動位置，淘汰邊界個體，更新警戒者的適應度值。

Step7：求解最新全局個體適應度值，替換最優(yōu)位置bestX1及其響應的適應度值bestF1。

Step8：判斷是否達到最大迭代次數(shù)，若達到，則輸出最優(yōu)適應度值，即所求問題的最優(yōu)解，否則轉到Step4。

4 算法驗證與分析

實驗仿真環(huán)境為操作系統(tǒng)Windows8、處理器Intel(R) Core(TM)i5-4210U CPU @ 1.70 GHz 2.40 GHz、內存12G，采用Matlab R2018a。

4.1 算法仿真驗證

采用以下兩種方式驗證算法的有效性：

(1)實例驗證一。

圖3 TSSA算法測試甘特圖

由圖可知，兩段式麻雀搜索算法甘特圖調度結果顯示46小時可完成6個工件的生產，與文獻[13]中優(yōu)化的SA-PSO-GA調度效果相同，均優(yōu)于傳統(tǒng)的PSO-GA算法。將T-SSA算法的迭代曲線與原文獻比較，PSO-GA算法和SA-PSO-GA更易陷入局部最優(yōu)，輸出的解并非實際最優(yōu)解。從運行時間上來看，由于T-SSA達到最優(yōu)的迭代次數(shù)較少，運算時間為14-17S，在效率上明顯高于原文中提到的算法。

(2)實例驗證二。

設置9種不同規(guī)模的調度算例，隨機生成訂單數(shù)量、訂單權重、訂單收益，訂單中的工件數(shù)量合計分別為20、50、100,生產環(huán)節(jié)數(shù)為2、4、8，生產線條數(shù)分別合計為5、10、20，工件交期根據EDD規(guī)則[15]與經驗設置。數(shù)據結果與4.2中的數(shù)據格式類似。對生成的訂單數(shù)據進行處理，得到算例規(guī)模n×s(m)，n表示工件數(shù)，s表示生產環(huán)節(jié)數(shù)，m表示生產線總數(shù)。

使用相同的算法參數(shù)和編碼方式對人工蜂群算法(ABC)[12]、兩段式麻雀搜索算法(T-SSA)進行9次實例驗證比較。仿真結果如表1所示，在不同規(guī)模的算例中，T-SSA求解的最小值、平均值基本優(yōu)于ABC算法，體現(xiàn)出了明顯的搜索能力。

表1 實例運行結果統(tǒng)計(最小值、平均值單位：小時)

其中某一次的迭代曲線如圖4所示，實驗結果基本類似，ABC的最優(yōu)解T-SSA均可在相近迭代次數(shù)到達，且最優(yōu)解的消耗時長接近。結合表1和圖5可以看出，T-SSA的最優(yōu)解質量更好，表明該算法的搜索能力更強，更進一步證明了該算法的有效性和優(yōu)越性。

圖4 訂單調度迭代圖

4.2 訂單調度實例應用驗證

結合上海某西裝定制企業(yè)的流水車間生產過程為實例作為研究對象，驗證訂單調度模型和兩段式麻雀算法的有效性。該生產企業(yè)的西裝定制生產過程可描述為有限并行生產線混合流水車間，所有西裝定制產品從加工到結束，主要分為五個環(huán)節(jié)：裁剪有2條生產線(M1，M2)；縫制有3條生產線(M3，M4，M5)、手縫有3條生產線(M6，M7，M8)、整燙有2條生產線(M9，M10)，檢驗有2條生產線(M11，M12)。此處忽略不同工件的規(guī)格、生產工藝在每個加工環(huán)節(jié)的局部差異。本次選取該企業(yè)一次實際生產任務為實驗對象，共有8個客戶訂單，合計20個待加工工件，訂單權重、交貨期、工件收益已知。假設所有訂單在0時刻接受，且所有生產線環(huán)境運作正常，物料庫存充足。模擬訂單信息數(shù)據如表2所示，表3為訂單對應的西裝企業(yè)生產工時數(shù)據。

表2 訂單信息

表3 上海某西裝定制企業(yè)生產工時(單位：小時)

使用T-SSA算法進行實例調度，設置種群數(shù)量分別為30、60、100，最大迭代次數(shù)為500，發(fā)現(xiàn)者警戒閾值為0.8，發(fā)現(xiàn)者比例為20%，重復多次計算以上訂單實例。

續(xù)表3

各種群規(guī)模隨機取20次運算結果統(tǒng)計如表4所示，最優(yōu)迭代次數(shù)均在150代以內，運算時間較短。實際結果表明，種群增大可以有效減少迭代次數(shù)，得到目標值。

表4 實例運行結果統(tǒng)計

目前該企業(yè)還是通過傳統(tǒng)的Excel和人為經驗制作訂單生產排程，人工負荷調整工作量巨大，采用這種方式進行以上實例調度編排企業(yè)應用總共耗時450分鐘，使用T-SSA算法運行實例，最差結果也是少于450分鐘的，驗證了兩段式麻雀搜索算法結果流水車間訂單調度問題的實用性和有效性。

5 結束語

針對流水車間訂單調度問題，建立單目標數(shù)學模型，采用兩段式雙層編碼的麻雀搜索算法進行問題求解，對發(fā)現(xiàn)者、跟隨者、警戒者三種角色采用不同的機制更新策略。算法很好地挖掘了全局最優(yōu)潛在區(qū)域的能力，從而有效地避免了局部最優(yōu)問題。將T-SSA算法與文獻[10,12]中的算法進行模擬比較，驗證了算法的有效性和優(yōu)越性。采用企業(yè)訂單調度實例測試T-SSA，更近一步驗證了T-SSA的有效性和實用性。不足之處是，T-SSA在求解大規(guī)模應用時，耗時稍微長一些，可對算法進行進一步的研究，將其擴展使用在更復雜的調度問題中，例如多目標調度問題。