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

(1. 大連海事大學(xué)交通運輸工程學(xué)院，遼寧 大連 116026；2. 東南大學(xué)交通學(xué)院，江蘇 南京 210096；3. 大連海事大學(xué)航運經(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è)計問題。然而也正是由于協(xié)同制造模式下協(xié)同調(diào)度運作具有比傳統(tǒng)模式更多樣性的特性，使得調(diào)度問題變得更加復(fù)雜。傳統(tǒng)調(diào)度問題一般是加工工藝路線固定，而協(xié)同制造模式下加工工藝路線具有不固定的特點，且多種不同的加工路線可以形成網(wǎng)絡(luò)，這使得調(diào)度的選擇性變多，調(diào)度的復(fù)雜性增加。對此，需要設(shè)計具有普適性的不同類型協(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]研究了多獨立生產(chǎn)廠商和單連接的資源約束規(guī)劃調(diào)度問題，他們將該問題分解為兩層：生產(chǎn)規(guī)劃和資源調(diào)度，并構(gòu)建了一個混合整數(shù)規(guī)劃模型，采用基于列生成分布式?jīng)Q策方法進(jìn)行求解。Selvarajah等[4]研究了最小化加權(quán)流水時間和批量運輸成本的供應(yīng)鏈調(diào)度問題，通過分析一些多項式可解特殊問題，提出了啟發(fā)式算法求解一般問題。他們給出了下界以研究該啟發(fā)式算法的效果，數(shù)值仿真表明所提算法求得結(jié)果非常接近最優(yōu)解。Sawik[5]針對材料供應(yīng)、生產(chǎn)、裝配的集成調(diào)度問題構(gòu)建了混合整數(shù)規(guī)劃模型，其目標(biāo)是協(xié)同整個供應(yīng)鏈以實現(xiàn)庫存成本、生產(chǎn)線啟動成本以及運輸成本的最小化。Liu等[6]對庫存、運輸和調(diào)度決策進(jìn)行了綜合考慮，并對此提出了綜合模型，在此基礎(chǔ)上采用元啟發(fā)式算法進(jìn)行變領(lǐng)域搜索，仿真實驗驗證了該算法的有效性。Hajiaghaei-Keshteli等[7]提出了一個集成的生產(chǎn)和運輸供應(yīng)鏈調(diào)度模型，目標(biāo)是尋找優(yōu)化的生產(chǎn)排程和運輸路徑實現(xiàn)最小總成本下的客戶最優(yōu)服務(wù)，他們采用了啟發(fā)式方法對該問題進(jìn)行了求解。

Chen Zhilong等[8]調(diào)查了現(xiàn)有的綜合調(diào)度模型，并給出一個統(tǒng)一的模型表述方案。同時將現(xiàn)有的模型分為幾個不同的種類，并對各個模型的最優(yōu)性能、計算柔性、求解算法做了概述。孫靖等[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)度問題，他們考慮了各廠商的工件加工方式，并以最小化制造跨度時間和運輸總費用為目標(biāo)進(jìn)行優(yōu)化。姚建明等[14]在對MC模式下供應(yīng)鏈調(diào)度的基本運作特征描述及界定基礎(chǔ)上，分析了調(diào)度過程中主導(dǎo)矛盾的緩解思路；通過將該思路引入動態(tài)調(diào)度的運作過程，分析了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ào)度問題方面的成果。而事實上，這種類似模塊化生產(chǎn)的非固定工序調(diào)度問題在當(dāng)前數(shù)字化制造以及協(xié)同制造模式下，將變得更加普遍，其問題的研究和解決也變得尤為迫切。因此，本文在上述研究的基礎(chǔ)上，針對協(xié)同制造模式下的多產(chǎn)品多訂單協(xié)同制造調(diào)度問題進(jìn)行了研究。我們綜合考慮了制造商同類產(chǎn)品訂單的合并加工問題以及不同協(xié)同制造商之間的運輸問題，并在此基礎(chǔ)上設(shè)計了四種典型的協(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é)點，不同的產(chǎn)品加工可以設(shè)計不同的可行加工網(wǎng)絡(luò)，每個協(xié)同制造商具備加工一個或連續(xù)多個工序的能力。制造商相互之間根據(jù)產(chǎn)品需要，可自由構(gòu)建供需關(guān)系，每種產(chǎn)品指定網(wǎng)絡(luò)中的一些制造商按照一定的次序組成協(xié)同制造加工鏈。

基于上文描述，本文構(gòu)建模型的實質(zhì)是：任意一個協(xié)同制造商是有向圖中的一個節(jié)點，產(chǎn)品的加工序列構(gòu)成連接節(jié)點的邊(該產(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)品的加工費用相同；

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

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

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

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

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

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

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

i)選取供應(yīng)鏈運作開始的時間為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è)計主要考慮加工成本和加工時間兩個主要因素。

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)品庫存費用

根據(jù)基本假設(shè)，產(chǎn)品的庫存費用與存儲量和存儲時長成正比，所以產(chǎn)品的庫存費用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)品加工效率的特點，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è)計和分析，四類產(chǎn)品協(xié)同制造網(wǎng)絡(luò)分為平衡型、瓶頸型、跳躍型、混合型。這些產(chǎn)品可行協(xié)同制造網(wǎng)絡(luò)存在如下特點和約束：①不允許有折回現(xiàn)象；②可以有多個起始點和終點；③可以存在加工工序的跳躍。

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

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

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

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

在上述對四種類型的制造網(wǎng)絡(luò)設(shè)計的基礎(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，作為最晚交貨時間的計算參數(shù)，表達(dá)如下：

(7)

式(7)中，ηk≥1。

3)延期交貨懲罰費用

根據(jù)每個訂單重要程度不同，設(shè)置一個延期交貨懲罰費用倍數(shù)λk，作為延期交貨處罰費用的計算參數(shù)，延期交貨處罰費用與訂單量和延期時長成正比，從某種程度可以將其看作是在高成本下的庫存費用，表達(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ù)由訂單加工費用、訂單等待庫存費用、訂單提前完工庫存費用以及延期懲罰費用構(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)化(具體策略在后文描述)，實現(xiàn)最晚開工時間下庫存成本的最優(yōu)。

2)約束條件說明

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

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

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

3.1 螞蟻設(shè)計

本文將n個訂單用n只螞蟻表示，所有螞蟻的某一順序集合則表示為一種可行的訂單生產(chǎn)排序。由于本文產(chǎn)品網(wǎng)絡(luò)圖可以有多個起始點，螞蟻從一個虛擬初始節(jié)點走到終點，走完則生命結(jié)束。螞蟻的路徑概率選擇相互獨立，依據(jù)在各節(jié)點留下的信息素進(jìn)行選擇。各節(jié)點同一時間只能處理一只螞蟻，但螞蟻可以在節(jié)點前等待上一只螞蟻離開后再進(jìn)入該節(jié)點。一次迭代所有螞蟻全部生命結(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，計算公式如下：

(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)時交貨，且交貨期通常會比實際加工時間寬余，早安排生產(chǎn)必然帶來庫存成本的增加，因此安排合理的訂單生產(chǎn)時間對企業(yè)適應(yīng)協(xié)同制造背景下低成本生產(chǎn)的發(fā)展趨勢具有很大意義。訂單開始時間的優(yōu)化策略如下：

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

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

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

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

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

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

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

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

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

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

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

(1)仿真結(jié)果

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

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

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

從8訂單的仿真結(jié)果可知，所有訂單在時間點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)。這與實際情況相符，并可以為調(diào)度網(wǎng)絡(luò)的最大承受能力設(shè)計提供參考依據(jù)。圖2中，訂單k1、k2、k3、k4、k6、k7均在交貨時間窗口的最晚交貨時間點交貨，訂單k5在156時間點完工，存在1個時間點的提前交貨庫存；訂單k8在209時間點交貨，由于其滿足交貨時間窗口[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é)果看，仿真具有較高的運算效率和良好的收斂性。

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

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

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

5 結(jié)語

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

參考文獻(xiàn)：

[1] 范玉順. 網(wǎng)絡(luò)化制造的內(nèi)涵與關(guān)鍵技術(shù)問題[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ī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)工程理論與實踐, 2014, 34(5): 1167-1175.