時間窗口約束下基于改進(jìn)蟻群算法的協(xié)同制造調(diào)度研究

唐 亮，何 杰，靖 可，靳志宏

(1. 大連海事大學(xué)交通運(yùn)輸工程學(xué)院，遼寧 大連 116026；2. 東南大學(xué)交通學(xué)院，江蘇 南京 210096；3. 大連海事大學(xué)航運(yùn)經(jīng)濟(jì)與管理學(xué)院，遼寧 大連 116026)

1 引言

當(dāng)今，制造業(yè)尤其是航空、汽車、電子等高新技術(shù)行業(yè)在數(shù)字化制造和網(wǎng)絡(luò)化制造模式[1-2]的興起下，越來越注重高效率、協(xié)同化的生產(chǎn)。這種模式可以充分利用協(xié)同制造企業(yè)的優(yōu)勢資源進(jìn)行生產(chǎn)制造，也由此產(chǎn)生了協(xié)同制造商選擇問題，并面臨不同產(chǎn)品生產(chǎn)時的可行協(xié)同制造網(wǎng)絡(luò)設(shè)計(jì)問題。然而也正是由于協(xié)同制造模式下協(xié)同調(diào)度運(yùn)作具有比傳統(tǒng)模式更多樣性的特性，使得調(diào)度問題變得更加復(fù)雜。傳統(tǒng)調(diào)度問題一般是加工工藝路線固定，而協(xié)同制造模式下加工工藝路線具有不固定的特點(diǎn)，且多種不同的加工路線可以形成網(wǎng)絡(luò)，這使得調(diào)度的選擇性變多，調(diào)度的復(fù)雜性增加。對此，需要設(shè)計(jì)具有普適性的不同類型協(xié)同制造網(wǎng)絡(luò)，并從中找到合理和優(yōu)化的網(wǎng)絡(luò)路徑。

目前，對具有網(wǎng)絡(luò)化特征的協(xié)同制造調(diào)度問題的研究非常少，因此本文主要針對與本文研究問題相關(guān)的供應(yīng)鏈調(diào)度問題進(jìn)行綜述，主要研究包括：Thomas等[3]研究了多獨(dú)立生產(chǎn)廠商和單連接的資源約束規(guī)劃調(diào)度問題，他們將該問題分解為兩層：生產(chǎn)規(guī)劃和資源調(diào)度，并構(gòu)建了一個混合整數(shù)規(guī)劃模型，采用基于列生成分布式?jīng)Q策方法進(jìn)行求解。Selvarajah等[4]研究了最小化加權(quán)流水時間和批量運(yùn)輸成本的供應(yīng)鏈調(diào)度問題，通過分析一些多項(xiàng)式可解特殊問題，提出了啟發(fā)式算法求解一般問題。他們給出了下界以研究該啟發(fā)式算法的效果，數(shù)值仿真表明所提算法求得結(jié)果非常接近最優(yōu)解。Sawik[5]針對材料供應(yīng)、生產(chǎn)、裝配的集成調(diào)度問題構(gòu)建了混合整數(shù)規(guī)劃模型，其目標(biāo)是協(xié)同整個供應(yīng)鏈以實(shí)現(xiàn)庫存成本、生產(chǎn)線啟動成本以及運(yùn)輸成本的最小化。Liu等[6]對庫存、運(yùn)輸和調(diào)度決策進(jìn)行了綜合考慮，并對此提出了綜合模型，在此基礎(chǔ)上采用元啟發(fā)式算法進(jìn)行變領(lǐng)域搜索，仿真實(shí)驗(yàn)驗(yàn)證了該算法的有效性。Hajiaghaei-Keshteli等[7]提出了一個集成的生產(chǎn)和運(yùn)輸供應(yīng)鏈調(diào)度模型，目標(biāo)是尋找優(yōu)化的生產(chǎn)排程和運(yùn)輸路徑實(shí)現(xiàn)最小總成本下的客戶最優(yōu)服務(wù)，他們采用了啟發(fā)式方法對該問題進(jìn)行了求解。

Chen Zhilong等[8]調(diào)查了現(xiàn)有的綜合調(diào)度模型，并給出一個統(tǒng)一的模型表述方案。同時將現(xiàn)有的模型分為幾個不同的種類，并對各個模型的最優(yōu)性能、計(jì)算柔性、求解算法做了概述。孫靖等[9]為解決信息不完全共享環(huán)境下大規(guī)模定制供應(yīng)鏈的動態(tài)調(diào)度問題，提出了基于蟻群算法的多企業(yè)交互調(diào)度模型。Yimer等[10]針對按訂單生產(chǎn)制造供應(yīng)鏈，構(gòu)建了一個從原材料采購、部件制造、產(chǎn)品裝配以及配送過程的兩階段混合整數(shù)規(guī)劃模型。劉小華等[11]以大規(guī)模定制模式下的供應(yīng)鏈調(diào)度優(yōu)化問題為研究背景，將該問題進(jìn)行數(shù)學(xué)規(guī)劃建模，并通過定義將模型映射為有向圖。構(gòu)造一種混合算法并進(jìn)行供應(yīng)鏈優(yōu)化調(diào)度問題求解，結(jié)果表明該混合算法具有較好的整體性能。姚建明等[12]分析了拉動式供應(yīng)鏈調(diào)度動態(tài)性的產(chǎn)生根源，他們分析了供應(yīng)鏈動態(tài)調(diào)度過程中的兩個主要瓶頸，并在優(yōu)化供應(yīng)鏈動態(tài)調(diào)度過程中引入蟻群覓食的尋優(yōu)機(jī)理，提出供應(yīng)鏈動態(tài)調(diào)度的螞蟻尋優(yōu)算法。裴軍等[13]研究了多供應(yīng)商和單制造商組成的二層供應(yīng)鏈調(diào)度問題，他們考慮了各廠商的工件加工方式，并以最小化制造跨度時間和運(yùn)輸總費(fèi)用為目標(biāo)進(jìn)行優(yōu)化。姚建明等[14]在對MC模式下供應(yīng)鏈調(diào)度的基本運(yùn)作特征描述及界定基礎(chǔ)上，分析了調(diào)度過程中主導(dǎo)矛盾的緩解思路；通過將該思路引入動態(tài)調(diào)度的運(yùn)作過程，分析了MC模式下的供應(yīng)鏈動態(tài)調(diào)度機(jī)理，并提出了供應(yīng)鏈動態(tài)調(diào)度的螞蟻尋優(yōu)算法。程八一等[15]研究了作業(yè)體積有差異且生產(chǎn)設(shè)備為容積限定的批處理設(shè)備的差異分批調(diào)度問題，以服務(wù)跨度即制造-配送的總時長為優(yōu)化目標(biāo)，建立整數(shù)規(guī)劃模型。

通過上述研究綜述，我們知道現(xiàn)有研究主要針對固定工序模式下的傳統(tǒng)調(diào)度問題進(jìn)行，很少有針對本文所提協(xié)同模式下具有非固定工序特點(diǎn)的調(diào)度問題方面的成果。而事實(shí)上，這種類似模塊化生產(chǎn)的非固定工序調(diào)度問題在當(dāng)前數(shù)字化制造以及協(xié)同制造模式下，將變得更加普遍，其問題的研究和解決也變得尤為迫切。因此，本文在上述研究的基礎(chǔ)上，針對協(xié)同制造模式下的多產(chǎn)品多訂單協(xié)同制造調(diào)度問題進(jìn)行了研究。我們綜合考慮了制造商同類產(chǎn)品訂單的合并加工問題以及不同協(xié)同制造商之間的運(yùn)輸問題，并在此基礎(chǔ)上設(shè)計(jì)了四種典型的協(xié)同制造網(wǎng)絡(luò)，在交貨時間窗口的約束下對協(xié)同調(diào)度問題進(jìn)行優(yōu)化。

2 協(xié)同制造模式下的網(wǎng)絡(luò)調(diào)度模型

2.1 問題描述

在協(xié)同制造模式下，為了充分利用企業(yè)的優(yōu)勢資源，不同的加工制造工序可以有多個協(xié)同制造商供選擇，構(gòu)成了產(chǎn)品的協(xié)同制造網(wǎng)絡(luò)。在這種協(xié)同制造商供需網(wǎng)絡(luò)中，若干個協(xié)同制造商作為網(wǎng)絡(luò)節(jié)點(diǎn)，不同的產(chǎn)品加工可以設(shè)計(jì)不同的可行加工網(wǎng)絡(luò)，每個協(xié)同制造商具備加工一個或連續(xù)多個工序的能力。制造商相互之間根據(jù)產(chǎn)品需要，可自由構(gòu)建供需關(guān)系，每種產(chǎn)品指定網(wǎng)絡(luò)中的一些制造商按照一定的次序組成協(xié)同制造加工鏈。

基于上文描述，本文構(gòu)建模型的實(shí)質(zhì)是：任意一個協(xié)同制造商是有向圖中的一個節(jié)點(diǎn)，產(chǎn)品的加工序列構(gòu)成連接節(jié)點(diǎn)的邊(該產(chǎn)品的加工工序是非固定的)，進(jìn)而由邊構(gòu)成加工路徑，多條加工路徑可以共同構(gòu)成有向協(xié)同加工網(wǎng)絡(luò)圖。

本文調(diào)度問題給出如下假設(shè)：

a)每個協(xié)同制造商只負(fù)責(zé)某一同類工序的加 工，不同產(chǎn)品經(jīng)過該協(xié)同制造商所經(jīng)歷的加工處理方式是一致的，因此假設(shè)同一制造商分別加工等量的不同產(chǎn)品的加工費(fèi)用相同；

b)各個訂單的每個子任務(wù)只交由某一個協(xié)同制造商完成，且一個企業(yè)制造商不能并行處理不同訂單的相同子任務(wù)；

c)產(chǎn)品是單向生產(chǎn)，不存協(xié)同制造網(wǎng)絡(luò)中某工序節(jié)點(diǎn)折回加工的情況；

d)訂單產(chǎn)品在制造商之間的運(yùn)輸只考慮時間問題，不考慮成本問題；

e)同一訂單產(chǎn)品在不同制造商處單位庫存費(fèi)用相同，庫存費(fèi)用與存儲量和存儲時長成正比；

f)同類產(chǎn)品的不同訂單在同一制造商處可合并加工；

g)訂單產(chǎn)品在第一道工序?yàn)樵牧?，原材料成本以及其庫存成本在本文不予考慮；

h)各個訂單產(chǎn)品按照先到達(dá)先加工，加工結(jié)束立即運(yùn)輸處理(若訂單到達(dá)某一制造商時該制造商正在加工其它訂單，則進(jìn)入等待隊(duì)列)；

i)選取供應(yīng)鏈運(yùn)作開始的時間為0時刻；

j)訂單產(chǎn)品交貨時間分為最早交貨時間和最晚交貨時間，不接受提前交貨。

2.2 多產(chǎn)品網(wǎng)絡(luò)協(xié)同調(diào)度數(shù)學(xué)模型

為構(gòu)建協(xié)同制造模式下多產(chǎn)品多訂單的協(xié)同制造調(diào)度模型，首先對本文中用到的相關(guān)符號、參數(shù)、變量等進(jìn)行定義，具體如下：

M—協(xié)同制造商總個數(shù)

K—訂單總數(shù)

m—協(xié)同制造商索引，m=1,2,…,M

k—訂單索引，k=1,2,…,K

p—產(chǎn)品索引，p=1,2,…,P

i—制造商加工次數(shù)索引

j—產(chǎn)品工序數(shù)索引

l—加工路徑索引

Qk—第k個訂單的訂單數(shù)量

nm—第i個協(xié)同制造商加工總次數(shù)

nk l—第k個訂單在可行加工路徑l下的工序總數(shù)

nk—第k個訂單可行加工路徑總數(shù)

uk l—0,1變量，訂單k在可行加工路徑l上加工為1，否則為0

(1)協(xié)同制造商模型要素分析

協(xié)同制造商模型的設(shè)計(jì)主要考慮加工成本和加工時間兩個主要因素。

1)協(xié)同制造商加工成本

(1)

2)協(xié)同制造商加工時間

制造商加工產(chǎn)品的數(shù)量越多所需要的加工時間就越長，加工時間Tm與加工產(chǎn)品數(shù)量Q之間可用函數(shù)關(guān)系近似表達(dá)如下：

Tm(Q)=αtmQ

(2)

式(2)中αtm是制造商m加工單件產(chǎn)品所需時間。需要說明的是，不同的制造商加工同一產(chǎn)品所需要的時間會有所差異。

(2)產(chǎn)品模型要素分析

1)產(chǎn)品庫存費(fèi)用

根據(jù)基本假設(shè)，產(chǎn)品的庫存費(fèi)用與存儲量和存儲時長成正比，所以產(chǎn)品的庫存費(fèi)用Ws與庫存量Q以及存儲時長t近似關(guān)系如下述函數(shù)所示：

(3)

式(3)中，αtp為訂單k(所屬產(chǎn)品p)單位時間單件產(chǎn)品庫存成本。

2)基本加工時間Tb和額外交貨時間Ta

本文提出基本加工時間、額外交貨時間的概念?；炯庸r間可以作為一個交貨時間參考值中的一個因素，它反應(yīng)的是協(xié)同制造網(wǎng)絡(luò)對某一產(chǎn)品加工效率的特點(diǎn)，Tb表達(dá)式如下：

(4)

一般我們會選擇的交貨時間會比基本加工時間晚，所以在這里為每類產(chǎn)品定義一個額外交貨時間屬性，它反應(yīng)的是人為因素對該種產(chǎn)品訂單交貨時間的影響，這里給出額外交貨時間函數(shù)：

(5)

3)產(chǎn)品協(xié)同制造工序有向網(wǎng)絡(luò)

本文假設(shè)有多類產(chǎn)品p，同種產(chǎn)品可以有多條加工工藝路線從而形成協(xié)同制造網(wǎng)絡(luò)。不失一般性，本文針對四類產(chǎn)品網(wǎng)絡(luò)進(jìn)行設(shè)計(jì)和分析，四類產(chǎn)品協(xié)同制造網(wǎng)絡(luò)分為平衡型、瓶頸型、跳躍型、混合型。這些產(chǎn)品可行協(xié)同制造網(wǎng)絡(luò)存在如下特點(diǎn)和約束：①不允許有折回現(xiàn)象；②可以有多個起始點(diǎn)和終點(diǎn)；③可以存在加工工序的跳躍。

a.平衡型協(xié)同制造網(wǎng)絡(luò)。這種協(xié)同制造網(wǎng)絡(luò)是生產(chǎn)比較平衡的一種情況，每個網(wǎng)絡(luò)節(jié)點(diǎn)(協(xié)同制造商)都有多個均勻的下游節(jié)點(diǎn)可供選擇，一般此類網(wǎng)絡(luò)的物流比較平均，網(wǎng)絡(luò)壓力會比較小。

b.瓶頸型協(xié)同制造網(wǎng)絡(luò)。瓶頸型協(xié)同制造網(wǎng)絡(luò)表明由于某些制造工序的特殊性，網(wǎng)絡(luò)中可行加工路徑必須經(jīng)過某些節(jié)點(diǎn)，這將導(dǎo)致這些特定節(jié)點(diǎn)的物流比較集中。因此，當(dāng)總物流量較大時，協(xié)同制造網(wǎng)絡(luò)的總生產(chǎn)能力會受到這些節(jié)點(diǎn)的制約。

c.跳躍型協(xié)同制造網(wǎng)絡(luò)。對于跳躍型協(xié)同制造網(wǎng)絡(luò)的設(shè)計(jì)，主要是考慮到不同的制造企業(yè)對同一產(chǎn)品的加工方法和能力不同，同樣的產(chǎn)品有的企業(yè)可以直接完成連續(xù)多個加工任務(wù)，由此一旦加工路線經(jīng)過此類網(wǎng)絡(luò)節(jié)點(diǎn)，可以較快到達(dá)網(wǎng)絡(luò)終點(diǎn)。

d.混合型協(xié)同制造網(wǎng)絡(luò)?；旌闲蛥f(xié)同制造網(wǎng)絡(luò)是以上三種網(wǎng)絡(luò)的整合，一般在復(fù)雜產(chǎn)品的大中型加工網(wǎng)絡(luò)中比較常見。

在上述對四種類型的制造網(wǎng)絡(luò)設(shè)計(jì)的基礎(chǔ)上，我們假設(shè)產(chǎn)品p在加工過程中可供選擇的協(xié)同制造商集合為Up(Up≠φ)，集合中元素個數(shù)|Up|。根據(jù)產(chǎn)品在這些協(xié)同制造商中的流動關(guān)系，可得到一個階數(shù)為|Up|的臨接二元關(guān)系矩陣Ap，Ap(ij)表示產(chǎn)品從集合中第i個制造商到集合中第j個制造商的供需關(guān)系，i到j(luò)存在供需關(guān)系則Ap(ij)=1，否則Ap(ij)=0。

(3)訂單模型要素分析

1)訂單最早交貨時間

(6)

2)最晚交貨時間

根據(jù)每個訂單緊急程度不同，設(shè)置一個緊急倍數(shù)ηk，作為最晚交貨時間的計(jì)算參數(shù)，表達(dá)如下：

(7)

式(7)中，ηk≥1。

3)延期交貨懲罰費(fèi)用

根據(jù)每個訂單重要程度不同，設(shè)置一個延期交貨懲罰費(fèi)用倍數(shù)λk，作為延期交貨處罰費(fèi)用的計(jì)算參數(shù)，延期交貨處罰費(fèi)用與訂單量和延期時長成正比，從某種程度可以將其看作是在高成本下的庫存費(fèi)用，表達(dá)式如下：

(8)

λk的設(shè)置需要根據(jù)訂單緊急程度進(jìn)行設(shè)置，一般越緊急的訂單其懲罰倍數(shù)設(shè)置應(yīng)越高。

(4)綜合評價目標(biāo)函數(shù)

本文中協(xié)同制造網(wǎng)絡(luò)調(diào)度綜合評價目標(biāo)函數(shù)由訂單加工費(fèi)用、訂單等待庫存費(fèi)用、訂單提前完工庫存費(fèi)用以及延期懲罰費(fèi)用構(gòu)成，表述如下：

(9)

目標(biāo)函數(shù)(9)中，相關(guān)函數(shù)描述如下

(10)

(11)

(12)

(13)

模型相關(guān)約束條件：

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

1)目標(biāo)函數(shù)說明

值得提出的是，鑒于本文交貨策略具有時間窗口限制，我們除了不希望延遲交貨還不希望提前交貨，因此本文將在后文蟻群算法仿真給出的最優(yōu)加工時間表(最早開始加工時間)初始排序后，將按時間后移的策略對訂單的開始時間進(jìn)行優(yōu)化(具體策略在后文描述)，實(shí)現(xiàn)最晚開工時間下庫存成本的最優(yōu)。

2)約束條件說明

約束(14)表示k訂單在j工序處的等待開始時刻不大于其開始加工時間；約束(15)表示訂單k在j工序的開始加工時間小于在該工序的完工時間；約束(16)表示訂單k在j工序的完工時間不大于其在該工序開始運(yùn)輸時間；(17)表示訂單k在j工序開始運(yùn)輸時間不大于其運(yùn)輸結(jié)束時間；(18)表示訂單k在j工序運(yùn)輸結(jié)束時間不大于訂單k在下一工序(j+1)開始加工時間；(19)表示在j工序處，訂單k的完工時間不大于下一訂單(k+1)的開始加工時間；(20)表示訂單k只能在一條加工路徑l上加工。

3 蒙特卡洛改進(jìn)蟻群算法設(shè)計(jì)思路

對于多產(chǎn)品協(xié)同制造網(wǎng)絡(luò)圖，將不同類產(chǎn)品訂單的可選協(xié)同制造商視為網(wǎng)絡(luò)節(jié)點(diǎn)，節(jié)點(diǎn)之間的有向弧表示節(jié)點(diǎn)之間的信息素濃度，各弧的初始信息素濃度相等。

3.1 螞蟻設(shè)計(jì)

本文將n個訂單用n只螞蟻表示，所有螞蟻的某一順序集合則表示為一種可行的訂單生產(chǎn)排序。由于本文產(chǎn)品網(wǎng)絡(luò)圖可以有多個起始點(diǎn)，螞蟻從一個虛擬初始節(jié)點(diǎn)走到終點(diǎn)，走完則生命結(jié)束。螞蟻的路徑概率選擇相互獨(dú)立，依據(jù)在各節(jié)點(diǎn)留下的信息素進(jìn)行選擇。各節(jié)點(diǎn)同一時間只能處理一只螞蟻，但螞蟻可以在節(jié)點(diǎn)前等待上一只螞蟻離開后再進(jìn)入該節(jié)點(diǎn)。一次迭代所有螞蟻全部生命結(jié)束為一個螞蟻順序集合完成一次搜索，并倒推相關(guān)數(shù)據(jù)：由信息素濃度按概率確定路徑→確定加工順序→確定事件起止時間→確定加工成本、庫存成本和延期成本。

我們在蟻群路徑選擇時的概率采用如下公式：

(22)

3.2 上升期望定值獎勵與移動窗口約束機(jī)制

本文提出上升期望定值獎勵機(jī)制，即給滿足獎勵條件的螞蟻一個固定值信息素濃度獎勵。具體思想如下：選擇兩個不同螞蟻加工順序集合進(jìn)行模擬，得到評價指標(biāo)值分別P1、P2，假設(shè)P1

max←min+(1-u)(max-min)

(23)

式(23)中，u為期望窗口收縮率(0

3.3 蒙特卡洛思想在蟻群算法上的應(yīng)用

蒙特卡洛與蟻群算法結(jié)合的基本思想描述如下：在模擬過程中充分利用所有螞蟻加工順序集合已走路徑獲得的收益，給收益高的螞蟻加工順序集合更多的機(jī)會，同時也考慮探索那些收益暫時不高的螞蟻加工順序集合，這種對于利用和探索進(jìn)行權(quán)衡的關(guān)系體現(xiàn)在蒙特卡洛選擇函數(shù)的定義上，本文定義第i個螞蟻加工順序集合的UCB1(Upper Confidence Bound)值Zi，計(jì)算公式如下：

(24)

3.4 獎勵與信息素?fù)]發(fā)問題優(yōu)化

由于前期窗口移動變化次數(shù)少，獎勵期望比較低，螞蟻獲得獎勵比較容易。因此，螞蟻的質(zhì)量相對于后期并不一定理想，而信息素獎勵程度一樣，這樣容易導(dǎo)致前期給不是太好的螞蟻一個肯定的評價(給予獎勵)而使整個尋優(yōu)過程向某一個局部較優(yōu)發(fā)展。

當(dāng)模擬次數(shù)增加時，窗口移動次數(shù)增多，窗口期望可信度也隨之增高，此時我們需要將獎勵程度與窗口的可信度結(jié)合起來，讓獎勵程度隨著窗口期望可信度提高而提高。因此，我們將固定額度的獎勵乘以一個平衡系數(shù)，當(dāng)模擬次數(shù)少的時候這個系數(shù)趨近于零，當(dāng)模擬次數(shù)無窮大的時候，這個系數(shù)趨近于1，平衡系數(shù)如下：

(25)

式(25)中，C為定值，N為模擬次數(shù)。

經(jīng)過上述改進(jìn)，通過減少獎勵信息素濃度來控制前期低期望窗口對搜索結(jié)果的影響，然而會出現(xiàn)一個問題：獎勵信息素濃度達(dá)到一個穩(wěn)定值之前，整個網(wǎng)絡(luò)上的信息素由于處于揮發(fā)狀態(tài)，當(dāng)需要的模擬次數(shù)很多時，會出現(xiàn)獎勵信息素濃度還未達(dá)到穩(wěn)定值時，整個網(wǎng)絡(luò)的信息素都揮發(fā)掉了。因此，網(wǎng)絡(luò)上的信息素?fù)]發(fā)系數(shù)也要乘以平衡系數(shù)k(N)，這樣在前期獎勵信息素濃度并不高的情況下，網(wǎng)絡(luò)上的信息素?fù)]發(fā)速度也非常慢。當(dāng)達(dá)到模擬量時前期獎勵信息素濃度提高，網(wǎng)絡(luò)上的信息素?fù)]發(fā)速度也加快，這時網(wǎng)絡(luò)能快速收斂，從而找到理想解。

3.5 訂單開始時間優(yōu)化

鑒于儲存成本限制，如果交貨時間充裕，當(dāng)訂單到達(dá)時，我們并不會立即投入生產(chǎn)。其原因是客戶一般要求準(zhǔn)時交貨，且交貨期通常會比實(shí)際加工時間寬余，早安排生產(chǎn)必然帶來庫存成本的增加，因此安排合理的訂單生產(chǎn)時間對企業(yè)適應(yīng)協(xié)同制造背景下低成本生產(chǎn)的發(fā)展趨勢具有很大意義。訂單開始時間的優(yōu)化策略如下：

步驟1：用蟻群算法仿真模擬尋得初始訂單的最優(yōu)加工時間表(最早開始加工時間)；

步驟3：將每個訂單進(jìn)行回溯分析，把各工序的事件開始時間按ΔT向后調(diào)整。

4 仿真設(shè)計(jì)及分析

4.1 仿真參數(shù)設(shè)計(jì)

(1)制造商參數(shù)設(shè)計(jì)

表1 協(xié)同制造商之間距離

(2)產(chǎn)品網(wǎng)絡(luò)及參數(shù)設(shè)計(jì)

(3)訂單參數(shù)設(shè)計(jì)

由于計(jì)算量隨訂單數(shù)量增長曾爆炸式增長，本算例設(shè)計(jì)6個訂單和8個訂單，以對其計(jì)算效率和穩(wěn)定性進(jìn)行比較分析。6個訂單的相關(guān)數(shù)據(jù)如下： ，，，，，。

“<>”中第一項(xiàng)為訂單k，第二項(xiàng)為訂單所屬的產(chǎn)品類型p，第三項(xiàng)為訂單量Q，第四項(xiàng)為時間緊急倍數(shù)ηk，第四項(xiàng)為延期懲罰費(fèi)用倍數(shù)λk。8個訂單的數(shù)據(jù)在前6個訂單的基礎(chǔ)上增加2個：，。

4.2 仿真結(jié)果及算法性能

(1)仿真結(jié)果

依據(jù)事件發(fā)生時點(diǎn)對各訂單在不同協(xié)同制造商處的開始等待時間、開始加工時間、開始運(yùn)輸時間以及運(yùn)輸完成時間繪制排程甘特圖，6訂單和8訂單的排程結(jié)果分別如圖1和圖2所示。從6訂單的結(jié)果看，所有的訂單已經(jīng)進(jìn)行了滿足約束條件下的后移，比如第一個事件的時間發(fā)生點(diǎn)42為第2個訂單在協(xié)同制造商m1處開始加工時間。所有訂單在時間點(diǎn)166完成并交貨，總評價指標(biāo)值493.5。其中，訂單k1、k2、k3、k4、k6均在交貨時間窗口的最晚交貨時間點(diǎn)交貨，而訂單k5則由于訂單k1的約束無法后移，其在159時刻完成加工而不是在最晚交貨時間點(diǎn)交貨，但其交貨時間仍在交貨窗口[157, 211]。

圖1 6訂單排程結(jié)果

圖2 8訂單排程結(jié)果

從8訂單的仿真結(jié)果可知，所有訂單在時間點(diǎn)219完成，總評價指標(biāo)值715.4。在8個訂單的情況下，同樣未出現(xiàn)延遲交貨的情況，說明此時制造網(wǎng)絡(luò)交貨壓力比較小，也表明產(chǎn)品可供選擇的網(wǎng)絡(luò)協(xié)同商比較多，可行生產(chǎn)網(wǎng)絡(luò)具有彈性時，整個生產(chǎn)調(diào)度系統(tǒng)比較容易排產(chǎn)。這與實(shí)際情況相符，并可以為調(diào)度網(wǎng)絡(luò)的最大承受能力設(shè)計(jì)提供參考依據(jù)。圖2中，訂單k1、k2、k3、k4、k6、k7均在交貨時間窗口的最晚交貨時間點(diǎn)交貨，訂單k5在156時間點(diǎn)完工，存在1個時間點(diǎn)的提前交貨庫存；訂單k8在209時間點(diǎn)交貨，由于其滿足交貨時間窗口[155, 215]，因此不存在提前完工庫存成本。訂單3在協(xié)同制造商m10處，存在2個等待加工時間，產(chǎn)生12個單位庫存成本。

(2)算法性能分析

為了分析算法的性能，我們分析了仿真模擬過程收斂性，并取每次獎勵時移動窗口中的min, max值進(jìn)行分析，得到6訂單和8訂單的算法收斂性仿真結(jié)果如圖3和圖4所示。

圖3 6訂單算法收斂性仿真

圖4 8訂單算法收斂性仿真

從收斂性能上可以看到，無論是6訂單還是8訂單，窗口上限隨著獎勵次數(shù)的增多而降低，前期速度較快后期開始減慢，最終趨向一個穩(wěn)定值。從結(jié)果看，仿真具有較高的運(yùn)算效率和良好的收斂性。

從上述仿真結(jié)果來看，將期望窗口和蒙特卡洛思想與蟻群算法相結(jié)合，能夠得到一個比較滿意的結(jié)果。但是由于隨機(jī)模擬的算法求解具有一定的隨機(jī)性，每一次得到的解并不一定完全相同。為了檢驗(yàn)算法穩(wěn)定性，本文對上述6訂單和8訂單分別仿真40次得到的數(shù)據(jù)進(jìn)行分析后發(fā)現(xiàn)：對于6訂單仿真結(jié)果，平均花費(fèi)時間44.3s，平均獎勵總次數(shù)244，平均模擬總次數(shù)2699825次，40次有37次得到評價指標(biāo)值493.5，3次497.4，均方差0.702；對于8訂單仿真結(jié)果，平均花費(fèi)時間63s，平均獎勵總次數(shù)267，平均模擬總次數(shù)298541次，40次仿真中最大和最小評價指標(biāo)值分別為733.9和715.4，均方差6.936。

對比分析8個訂單和6個訂單的實(shí)驗(yàn)數(shù)據(jù)，我們發(fā)現(xiàn)求解8個訂單所需要的時間并沒有很明顯的增長，只是求解的穩(wěn)定性有一定程度的降低。綜上所述，在訂單數(shù)較少的情況下，算法無論在求解速度還是在求解的穩(wěn)定性方面，都有良好的表現(xiàn)。當(dāng)訂單數(shù)較多時，算法會在一定程度內(nèi)，以犧牲解的穩(wěn)定性為代價來換取高效的求解。

(3)與其它算法的比較分析

針對本文模型，我們將傳統(tǒng)蟻群算法(ACO)和其它文獻(xiàn)相關(guān)算法(遺傳算法GA[16]以及IM-ACO[17]) 與本文所提算法進(jìn)行比較，結(jié)果列于表2中。需要提出，我們主要針對6訂單在不同產(chǎn)品組合下的運(yùn)行效果進(jìn)行比較，每一種組合進(jìn)行40次仿真實(shí)驗(yàn)。表2中，列出了各種算法在40次實(shí)驗(yàn)中的最優(yōu)值以及平均CPU時間。

表2 不同算法下仿真結(jié)果比較

從上表結(jié)果可以看出，本文所提蒙特卡洛算法無論在求解的質(zhì)量以及效率上與其它算法相比都有很好的優(yōu)勢。尤其與傳統(tǒng)蟻群算法ACO相比，效率和質(zhì)量要更高很多。由此可知，一旦協(xié)同制造網(wǎng)絡(luò)結(jié)構(gòu)變得更加復(fù)雜，本文算法在求解上將具有明顯的優(yōu)勢。

4.3 仿真結(jié)果討論和分析

通過上述仿真結(jié)果和算法性能描述，我們進(jìn)行如下討論和分析總結(jié)：

1)本文構(gòu)建模型具有合理性和創(chuàng)新性。由于考慮了制造企業(yè)連續(xù)加工方式的生產(chǎn)特點(diǎn)，其制造成本比分開加工方式的成本要低；其次，對最早交貨時間和最晚寬放交貨時間進(jìn)行了合理設(shè)計(jì)，而非隨機(jī)給定，這與制造企業(yè)與客戶進(jìn)行交貨時間約定時一般會根據(jù)產(chǎn)品生產(chǎn)特點(diǎn)分析而確定交貨時間的實(shí)際相符，因而使模型更具有實(shí)用性；另外還考慮了不同類型產(chǎn)品的特點(diǎn)，并在多始點(diǎn)和多終點(diǎn)等一般性條件下對其協(xié)同制造網(wǎng)絡(luò)進(jìn)行設(shè)計(jì)，使調(diào)度仿真模型更具普適性；同時，通過交貨時間的窗口約束，要求企業(yè)向客戶準(zhǔn)時交貨，以共同減少制造企業(yè)和客戶各自庫存成本，這與現(xiàn)實(shí)企業(yè)運(yùn)營時的實(shí)際需求相符。從仿真結(jié)果看，在訂單量不是很大，協(xié)同制造網(wǎng)絡(luò)壓力較小時，訂單都可以實(shí)現(xiàn)不延期，而由于生產(chǎn)約束條件(19)，仍出現(xiàn)了提前完工而導(dǎo)致額外庫存成本的情況。

2)算法具有良好的效率和穩(wěn)定性。在算法效率方面，在本文設(shè)計(jì)模型下，6訂單和8訂單計(jì)算時間均比較快。通過不同訂單產(chǎn)品組合的設(shè)計(jì)，我們將本文算法與其它算法進(jìn)行了比較分析，通過每種組合40次實(shí)驗(yàn)的結(jié)果可知，本文設(shè)計(jì)的算法在效率上具有良好的優(yōu)勢。由此可知，本文所運(yùn)用的蒙特卡洛思想以及移動窗口獎勵策略提高了螞蟻選擇的合理性，大大增加了問題求解的運(yùn)算速度。同時，在算法的穩(wěn)定性方面，由于蒙特卡洛算法與蟻群算法的結(jié)合，以及平衡系數(shù)的采用都使得求解過程避免了向局部最優(yōu)發(fā)展，尤其6個訂單40次仿真實(shí)驗(yàn)結(jié)果有37次收斂于同一值，均方差0.702，表明算法具有很好的穩(wěn)定性。

5 結(jié)語

本文基于協(xié)同制造背景建立了多產(chǎn)品多訂單的協(xié)同制造調(diào)度數(shù)學(xué)模型，模型考慮了協(xié)同制造商的同類產(chǎn)品訂單合并加工問題以及工序之間的運(yùn)輸時間問題。同時，本文設(shè)計(jì)了具有普適性特點(diǎn)的四類協(xié)同制造網(wǎng)絡(luò)，并設(shè)計(jì)了合理的交貨時間窗口。針對蟻群算法求解協(xié)同制造調(diào)度問題時，處理訂單加工順序的局限性，提出了用蟻群算法和蒙特卡洛思想相結(jié)合的方法，并提出了采用移動窗口提升期望獎勵規(guī)則。最后本文進(jìn)行了仿真實(shí)驗(yàn)，結(jié)果表明本文提出的模型具有科學(xué)合理性，可以獲得良好的調(diào)度結(jié)果；同時，本文所提算法具有較好的求解速度和求解性能，對于實(shí)際中求解多種類產(chǎn)品多訂單的調(diào)度方案具有較高的參考價值。

參考文獻(xiàn)：

[1] 范玉順. 網(wǎng)絡(luò)化制造的內(nèi)涵與關(guān)鍵技術(shù)問題[J]. 計(jì)算機(jī)集成制造系統(tǒng)-CIMS, 2003, 9(7): 576-582.

[2] 王宛山, 鞏亞東, 郁培麗. 網(wǎng)絡(luò)化制造[M]. 沈陽: 東北大學(xué)出版社, 2003.

[3] Thomas A, Venkateswaran J, Singh G, et al. A resource constrained scheduling problem with multiple independent producers and a single linking constraint: A coal supply chain example [J]. European Journal of Operational Research, 2014, 236: 946-956.

[4] Selvarajah E, Zhang Rui. Supply chain scheduling at the manufacturer to minimize inventory holding and delivery costs [J]. International Journal of Production Economics, 2014, 147: 117-124.

[5] Sawik T. Coordinated supply chain scheduling [J]. International Journal of Production Economics, 2009, 120(2): 437-451.

[6] Liu S C, Chen A Z. Variable neighborhood search for the inventory routing and scheduling problem in a supply chain [J]. Expert Systems with Applications, 2012, 39(4): 4149-4159.

[7] Hajiaghaei-Keshteli M, Aminnayeri M, Ghomi S M T F. Integrated scheduling of production and rail transportation [J]. Computers & Industrial Engineering, 2014, 74: 240-256.

[8] Chen Zhilong. Integrated production and outbound distribution scheduling: review and extensions [J]. Operations Research, 2010, 58(1): 130-148.

[9] 孫靖, 林杰. 信息不完全共享下MC供應(yīng)鏈動態(tài)調(diào)度模型研究[J]. 系統(tǒng)仿真學(xué)報, 2007, 19(9): 1943-1948.

[10] Yimer A, Demirli K. A genetic approach to two-phase optimization of dynamic supply chain scheduling [J]. Computers & Industrial Engineering, 2010, 58(3): 411-422.

[11] 劉小華, 林杰. 基于遺傳粒子群混合算法的供應(yīng)鏈調(diào)度優(yōu)化[J]. 控制與決策, 2011, 26(4): 501-506.

[12] 姚建明, 張秀敏, 劉麗文. 基于改進(jìn)螞蟻算法的拉動式供應(yīng)鏈動態(tài)調(diào)度分析[J]. 中國管理科學(xué), 2006, 14(3): 20-26.

[13] 裴軍, 劉心報, 范雯娟, 等. 基于生產(chǎn)與運(yùn)輸集成的供應(yīng)鏈調(diào)度優(yōu)化問題[J]. 中國管理科學(xué), 2012, 20(S1): 586-593.

[14] 姚建明, 劉麗文, 蒲云, 等. MC模式下供應(yīng)鏈動態(tài)調(diào)度的蟻群尋優(yōu)分析[J]. 管理科學(xué)學(xué)報, 2007, 10(3): 7-14.

[15] 程八一, 李明, 陳波, 等. 差異分批模式下的供應(yīng)鏈調(diào)度算法[J]. 系統(tǒng)工程學(xué)報, 2014, 29(4): 515-526.

[16] Lee Y, Jeong C, Moon C. Advanced planning and scheduling with outsourcing in manufacturing supply chain [J]. Computers & Industrial Engineering, 2002, 43(1), 351-374.

[17] 唐亮, 靖可, 何杰. 網(wǎng)絡(luò)化制造模式下基于改進(jìn)蟻群算法的供應(yīng)鏈調(diào)度優(yōu)化研究[J]. 系統(tǒng)工程理論與實(shí)踐, 2014, 34(5): 1167-1175.