基于T-SSA算法的流水車(chē)間訂單調(diào)度問(wèn)題研究

王 婷，毋 濤

(西安工程大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安 710048)

0 引 言

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

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

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

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

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

1 問(wèn)題描述與建模

1.1 問(wèn)題描述

1.2 模型的假設(shè)條件

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

(2)同一生產(chǎn)線的同一時(shí)間只能加工1件產(chǎn)品。

(3)不同的訂單任務(wù)之間沒(méi)有先后約束。

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

(5)每?jī)蓚€(gè)處理環(huán)節(jié)之間有足夠的緩存空間，允許產(chǎn)品在處理環(huán)節(jié)之間停留和等待。

(6)訂單調(diào)度過(guò)程為非搶占式調(diào)度。

(7)訂單任務(wù)中各生產(chǎn)環(huán)節(jié)的交貨時(shí)間和利潤(rùn)值均為已知量(交貨時(shí)間從初始時(shí)間0開(kāi)始計(jì)算)。

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

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

i：表示待加工工件編號(hào)。

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

k：表示每個(gè)生產(chǎn)環(huán)節(jié)的生產(chǎn)線編號(hào)。

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

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

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

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

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

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

xijk：當(dāng)工件i的第j個(gè)生產(chǎn)環(huán)節(jié)在生產(chǎn)線k上的加工時(shí)xijk=1；否則xijk=0。

rjk：第j個(gè)生產(chǎn)環(huán)節(jié)在生產(chǎn)線k上加工的第r個(gè)任務(wù)的工件編號(hào)。

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

1.4 模型構(gòu)建

根據(jù)問(wèn)題描述，采用最小最大訂單完成時(shí)間為目標(biāo)函數(shù)，可轉(zhuǎn)化為求解訂單內(nèi)工件集的最小化完成時(shí)間，即一個(gè)工件完成時(shí)間的最小值，模型構(gòu)建具體如下：

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

2 麻雀搜索算法(SSA)

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

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

SSA算法的具體流程見(jiàn)圖1。

圖1 麻雀搜索算法流程

Step1：初始化麻雀種群。

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

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

(10)

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

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

(11)

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

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

(12)

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

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

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

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

3.1 編碼方式

圖2 兩段式編碼示意圖

生產(chǎn)環(huán)節(jié)編碼的編碼長(zhǎng)度為總生產(chǎn)環(huán)節(jié)數(shù)，基因位上的數(shù)字表示工件號(hào)，相同工件號(hào)出現(xiàn)的次數(shù)對(duì)應(yīng)工件的第幾個(gè)生產(chǎn)環(huán)節(jié)。圖2中表示的工件加工順序?yàn)椋汗ぜ?→工件2→工件3→工件1→工件2→工件3→工件2→工件1→工件1，其中每個(gè)工件出現(xiàn)三次，即每個(gè)工件有3個(gè)生產(chǎn)環(huán)節(jié)，比如基因位1上的數(shù)字3，表示工件3的第一個(gè)生產(chǎn)環(huán)節(jié)，基因位3上的數(shù)字3，表示工件3的第二個(gè)生產(chǎn)環(huán)節(jié)，諸如此類。

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

[3,2,3,1,2,3,2,1,1,1,2,1,1,2,2,1,2,2]整個(gè)整數(shù)段表示一只麻雀?jìng)€(gè)體。

3.2 種群初始化

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

(13)

(14)

3.3 適應(yīng)度函數(shù)

以最小化最大訂單完成時(shí)間為目標(biāo)函數(shù)求解流水車(chē)間訂單調(diào)度問(wèn)題，主要思想是訂單內(nèi)的每個(gè)工件的完成時(shí)間最優(yōu)，可以將該問(wèn)題轉(zhuǎn)化為求解訂單內(nèi)工件集的最小化最大完成時(shí)間為適應(yīng)度函數(shù)，工件最大完成時(shí)間越小，表示個(gè)體的適應(yīng)度值越好，即fitness=min{Cmax(P)}。

3.4 智能行為設(shè)計(jì)

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

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

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

(2)發(fā)現(xiàn)者移動(dòng)機(jī)制。

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

(3)跟隨者跟隨機(jī)制。

(4)偵察預(yù)警機(jī)制(警戒者)。

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

3.5 T-SSA算法迭代過(guò)程

根據(jù)智能行為設(shè)計(jì)的4大機(jī)制，可將使用T-SSA算法求解流水車(chē)間訂單調(diào)度問(wèn)題的步驟概括如下：

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

Step2：根據(jù)初始化方案進(jìn)行種群初始化，確定麻雀?jìng)€(gè)體的位置編碼。

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

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

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

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

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

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

4 算法驗(yàn)證與分析

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

4.1 算法仿真驗(yàn)證

采用以下兩種方式驗(yàn)證算法的有效性：

(1)實(shí)例驗(yàn)證一。

圖3 TSSA算法測(cè)試甘特圖

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

(2)實(shí)例驗(yàn)證二。

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

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

表1 實(shí)例運(yùn)行結(jié)果統(tǒng)計(jì)(最小值、平均值單位：小時(shí))

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

圖4 訂單調(diào)度迭代圖

4.2 訂單調(diào)度實(shí)例應(yīng)用驗(yàn)證

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

表2 訂單信息

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

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

續(xù)表3

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

表4 實(shí)例運(yùn)行結(jié)果統(tǒng)計(jì)

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

5 結(jié)束語(yǔ)

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