基于批量分流生產的供應鏈網(wǎng)絡調度研究

赫 超 唐 亮，2

1(沈陽航空航天大學機電工程學院 遼寧 沈陽 110000)2(大連海事大學交通運輸工程學院 遼寧 大連 116026)

0 引 言

現(xiàn)如今市場經(jīng)濟模式的快速轉變對企業(yè)的制造環(huán)境產生了翻天覆地的影響。從制造業(yè)漫長的發(fā)展歷史來看，總結制造業(yè)的發(fā)展階段，其中主要包括勞動密集型、設備密集型、信息密集型、知識密集型等幾個重要的發(fā)展階段。目前制造業(yè)正歷經(jīng)著從信息密集型過渡向知識密集型的更科學的發(fā)展階段。在21世紀的新型市場環(huán)境中，優(yōu)勢競爭企業(yè)應該具備的最核心能力是對市場的快速響應速度，因此，以協(xié)作分工和高度自適應性為特征的協(xié)同制造模式通過數(shù)字化、網(wǎng)絡化信息與其他優(yōu)勢企業(yè)在生產經(jīng)營業(yè)務活動中各個環(huán)節(jié)進行合作，以實現(xiàn)供應鏈中各個企業(yè)間的生產組合利用和資源共享。協(xié)同制造能根據(jù)用戶的不同需要迅速地與其他企業(yè)組成聯(lián)盟，進行產品的協(xié)同設計和制造，從而快速響應用戶的需求。這使得擁有協(xié)同生產能力的制造商們共同組成了關于產品生產的供應鏈。

目前在生產調度、智能調度優(yōu)化方面，國內外許多學者已經(jīng)從多個角度做出了大量有意義的工作并獲取了豐碩的研究成果[1-6]。近年來，研究者不再局限于僅對生產企業(yè)內部生產環(huán)節(jié)進行優(yōu)化，而是越來越多地從供應鏈的角度綜合考慮包括原料采購、生產、庫存以及物流配送等環(huán)節(jié)在內的集成優(yōu)化。這些研究[7-9]從不同的角度對集成調度模型進行了構建，即制造企業(yè)的不同分布結構、交貨時間約定、交貨方式、車輛運輸方式等，并考慮了總成本和客戶服務水平之間的權衡。總體而言，該領域大部分研究可以分為兩階段：供應鏈調度[10-14]和三階段供應鏈調度[15-22]。

歸納現(xiàn)有針對供應鏈調度問題的文獻，我們發(fā)現(xiàn)針對協(xié)同生產方式的局部特點所開展的研究較少。而結合實際生產過程，我們發(fā)現(xiàn)當供應鏈中某一制造企業(yè)完成產品中間工序的加工任務后，可能會將手中的半成品以成批量的形式委派到具有相應生產能力的多個下游企業(yè)處進行生產。這種協(xié)同制造方式與上游制造企業(yè)將全部數(shù)量的半成品委任給單個下游制造企業(yè)的傳統(tǒng)協(xié)同制造模式相比，更加符合以快速響應客戶需求為核心的市場經(jīng)濟模式，并使各個制造企業(yè)的優(yōu)勢生產資源得到更充分的利用。

基于上述內容，本文將針對基于批量分流生產的供應鏈網(wǎng)絡調度問題進行研究，建立了以總最短完工時間為優(yōu)化目標的數(shù)學模型。此外，對于求解算法的選擇上，由于本文研究問題的數(shù)學模型中0-1變量較多，其中不僅包括協(xié)同企業(yè)選擇變量，還包括生產路徑選擇變量。而Benders算法是一種專門求解問題中含有不同類型變量的分解算法，故本文選用Benders分解算法對問題模型中0-1變量和純整數(shù)變量進行分離后,通過反復求解對偶子問題和Benders主問題不斷修正上下界值最終得到問題的最優(yōu)解。此外，為提高算法求解效率，通過應用pareto最優(yōu)割代替Benders最優(yōu)割的方法對傳統(tǒng)Benders算法進行改進。

1 數(shù)學模型及求解算法

1.1 問題描述

在協(xié)同制造模式下，企業(yè)通常以標準化和模塊化生產運作，具備一種或幾種優(yōu)勢生產能力。為了充分利用這些協(xié)同企業(yè)的某種優(yōu)勢資源，對產品關鍵部件的協(xié)同工序進行分解，不同的協(xié)同工序可以交由具備該工序生產能力的協(xié)同企業(yè)完成。同時，由于具備某種協(xié)同工序生產能力的協(xié)同企業(yè)可能有多個，因而構成協(xié)同供應鏈有向網(wǎng)絡，網(wǎng)絡中包含多條可行加工路徑。一旦出現(xiàn)多種不同類型訂單需求的情況，由于其工序的不同，協(xié)同企業(yè)會發(fā)生相應變化，導致部分協(xié)同企業(yè)處于不同協(xié)同供應鏈網(wǎng)絡的現(xiàn)象，因此有必要擴展至多個交互的協(xié)同供應鏈網(wǎng)絡進行研究。針對本文供應鏈網(wǎng)絡調度問題給出如下假設：

1) 每個協(xié)同企業(yè)可完成某一項協(xié)同工序或幾項協(xié)同工序的加工；

2) 各個訂單的每個協(xié)同工序只能由一個協(xié)同企業(yè)完成，且同一個協(xié)同企業(yè)不能并行處理不同訂單的生產任務；

3) 各個訂單按照先到達先加工規(guī)則，加工結束立即運輸；

4) 各個訂單產品的中間工序在加工過程不允許打斷,也不存在返回再加工的情況；

5) 整個生產系統(tǒng)運作開始時間為0時刻；

6) 訂單必須成批生產，不接受某幾個產品的單獨生產。

1.2 模型構建

假定多個協(xié)同制造企業(yè)組成的供應鏈現(xiàn)已接受多個訂單的生產，其中包含多個種類的產品。為了構建分批制造的供應鏈調度問題模型，首先分別對模型中參數(shù)與變量進行描述。

在相關參數(shù)中，K={1,2,…,k}為全部訂單集合，k為訂單總數(shù)；Ni={1,2,…,ni}為第i個訂單全部可行加工路徑集合，ni為第i個訂單可行加工路徑總數(shù)；M={1,2,…,m}為全部協(xié)同企業(yè)集合，m為協(xié)同企業(yè)總數(shù)；Tij(p,q)為運輸時間矩陣，表示i訂單第j條可行路徑的加工矩陣中第p行q列元素，若i訂單在第j條可行路徑上企業(yè)p與企業(yè)q之間存在先后相鄰加工關系則大于0，否則為0；b為每批產品所包含的產品數(shù)量；di為訂單i包含的產品數(shù)量；elij和slij分別代表訂單i在可行加工路徑j處首工序和尾工序制造企業(yè)序號；wip為訂單i在協(xié)同企業(yè)p處單位產品的加工時間。

在相關變量中，yij為0-1變量，i訂單選擇在第j條可行路徑上加工為1，否則為0；xij表示i訂單在第j條可行路徑上的加工批量；cijp表示i訂單在第j條路徑上協(xié)同企業(yè)p的完工時間；lii′jj′p為0-1變量，若訂單i、i′分別在第j、j′條可行路徑上加工且在這兩個加工路徑上的交叉企業(yè)p處，訂單i先于訂單i′完工則為1，否則為0；ei表示訂單i的完工時間。綜上所述，基于批量分流生產的供應鏈網(wǎng)絡調度問題模型構建如下：

(1)

(2)

b×xij≤di×yij?i∈K,j∈Ni

(3)

b×xij≥b-di×(1-yij) ?i∈K,j∈Ni

(4)

yij≤cijp?i∈K,j∈Ni,p=elij

(5)

cijp≤G×yij?i∈K,j∈Ni,p=elij

(6)

cijp≥b×xij×wip?i∈K,j∈Ni,p=slij

(7)

cijp+t(p,q)×yij≤cijq-b×xij×wiq

?Tij(p,q)>0

(8)

cijp≤ci′j′p-b×xi′j′×wi′p+G×(1-lii′jj′p)+

G×(2-yij-yi′j′)

?i、i′∈K,j∈Ni,j′∈Ni′,p∈Hij∩Hi′j′,i≥i′,i≠i′‖j≠j′

(9)

ci′j′p≤cijp-b×xij×wip+G×(2-yij-yi′j′+lii′jj′p) ?i、i′∈K,j∈Ni,j′∈Ni′,p∈Hij∩Hi′j′,

i≥i′,i≠i′‖j≠j′

(10)

ei≥cijp?i∈K,j∈Ni,p=elij

(11)

模型中目標函數(shù)式(1)表示所有訂單的完工時間總和的最小值；式(2)表示同一訂單在不同的路徑上加工數(shù)量的總和必須達到既定數(shù)量；式(3)和式(4)表示上游企業(yè)將半成品后續(xù)工序的工作托付給下游企業(yè)時，若選擇的下游企業(yè)不止一個，則分流的批量至少為1;式(5)和式(6)表示產品在所選擇的可行加工路徑中的各個協(xié)同企業(yè)的完工時間均大于0，在未被選擇的路徑上均等于0，其中G代表一個很大的正整數(shù)；式(7)限制了訂單首加工工序的最小完工時間，保證了整個生產系統(tǒng)運作開始時間為0時刻；式(8)結合了運輸時間限制了同一路徑中相鄰兩個企業(yè)的完工時間關系；式(9)和式(10)表示企業(yè)不能同時加工兩個訂單，這里要額外說明一點，為了減少變量lii′jj′p以及相關約束的數(shù)目，我們約束變量lii′jj′p在滿足i≤i′的前提下，必須額外滿足i≠i′或者j≠j′;式(11)表示產品最終的完工時間大于部分數(shù)量產品的完工時間。

2 改進Benders分解算法及其應用

2.1 Benders分解算法及其改進

Benders分解算法是J.F.Benders在1962年提出的，它是一種專門求解混合整數(shù)規(guī)劃的算法。其主要思想是通過固定一部分變量的值將原始復雜問題轉換成相對簡單的子問題，固定變量的取值不同相應產生的子問題也不同。每次求解子問題都會根據(jù)不同求解情況得到一個Benders最優(yōu)割或Benders可行割加入到新構建的Benders主問題中，通過一定次數(shù)的迭代不斷縮小最優(yōu)解的搜索范圍后得到最優(yōu)解。以如下形式的0-1混合整數(shù)規(guī)劃為例說明Benders算法流程：

mincTx+dTy

(12)

s.t.Ay+Bx≤b

y∈{0,1}x∈Z+

式中：c、d、b分別為m、n、l維列向量，A、B分別為l×n、l×m維系數(shù)矩陣，當變量y取值為y*時，式(12)可以轉變?yōu)橐韵滦问剑?/p>

min{dTy*+min{cTx|Bx≤b-Ay*,x∈Z+}}

(13)

式(13)中內層問題min{cTx|Bx≤b-Ay*,x∈Z+}被稱為原始子問題，其對偶問題Q為：

max(b-Ay*)Tλ

(14)

s.t.BTλ≥c

λ∈Z+

記S={λ|BTλ≥c,λ∈Z+}是由對偶子問題Q的可行域構成的多面體，它不隨y取值的不同而發(fā)生改變，up和ud分別為多面體S的極點集與極方向集。通過引用一個輔助變量θ構造Benders主問題，其最優(yōu)值與原始問題相同,具體形式如下：

minθ

(15)

s.t. (b-Ay)α≤θα∈up

(b-Ay)β≤0β∈ud

y∈{0,1}θ∈Z+

α和β分別多面體S的極點和極方向，每個極點或極方向在Benders主問題中都代表一條約束，由極點產生的約束叫做Benders最優(yōu)割平面，由極方向產生的約束叫做Benders可行割平面。當多面體S全部極點與極方向被添加進up和ud中，求解問題Benders主問題得到的目標函數(shù)值與原始問題的最優(yōu)值相等。但在實際求解過程中想要得到全部極點和極方向是很難做到的，尤其當問題規(guī)模較大時，多面體S中極點和極方向的總數(shù)量也隨著約束數(shù)大幅增長，而且在這些約束中只有一部分是積極約束，故沒有必要求出全部極點與極方向。

以下給出一種基于Benders表示的約束生成算法：在求解前需要設置初始上UB、下界LB和程序終止閾值ε，并且給定一組列變量y的初始可行解y*，初始up和ud為空集。在求解過程中，首先求解y值初始固定后的對偶子問題Q，并且根據(jù)對偶子問題Q的求解情況判斷添加Benders最優(yōu)割或可行割，若此時對偶子問題存在最優(yōu)解，則將λ添加進up中，并且根據(jù)對偶定理，其目標函數(shù)與原問題目標函數(shù)值相等，故可以將該值作為臨時上界；若對偶子問題存在無界解，則將λ添加進up中。在更新up與ud中元素后下一步求解Benders主問題式(15)，將求解得到的θ最優(yōu)值作為臨時下界，并用最優(yōu)解y**替換給定的初始值y*產參與下一次流程運算。經(jīng)過反復的迭代，上下界逐漸逼近，當兩者逼近到一定程度滿足終止條件時，問題求解結束并得到原始問題最優(yōu)值與最優(yōu)解。

上述過程為傳統(tǒng)Benders算法計算流程，此流程中不需要求得多面體S中全部極點和極方向。但傳統(tǒng)Benders算法在每次迭代過程中無法保證每次得到的Benders最優(yōu)割的質量，從而影響上下界的收斂速度。故本文利用pareto最優(yōu)割替換Benders最優(yōu)割提高算法求解效率，并重新安排算法流程。pareto最優(yōu)割也是在求解對偶子問題的過程中得到的，具體方式如下：

傳統(tǒng)Benders算法中，當對偶問題Q有唯一解時，其解對應一個極點被添加到Benders主問題中，在改進Benders算法中此部分有所不同，具體流程如下：

首先我們假設在對偶子問題中y取值為y1。按照算法流程接下來計算對應的對偶子問題：

max(b-Ay1)Tλ

(16)

s.t.BTλ≥c

λ∈Z+

當問題式(16)存在最優(yōu)解時,記最優(yōu)解集為G(y1)。下面通過引入一個新的y值y2構造新的問題：

max(b-Ay2)Tλ

(17)

s.t.BTλ≥c

λ∈Z+,λ∈G(y1)

問題式(17)必定存在最優(yōu)解，此時求解得到的λ值成為約束添加到Benders主問題中稱為pareto最優(yōu)割。

2.2 基于改進算法求解供應鏈調度模型

前文闡述了研究問題的數(shù)學模型以及其中各部分約束含義，下面結合研究問題闡述計算流程。

在利用改進Benders算法求解之前我們要將原問題模型轉化成形如式(12)較為規(guī)范又有明確劃分的矩陣形式。首先我們要得到系數(shù)矩陣A、B和常數(shù)列向量。本文將約束式(2)-式(10)中各項系數(shù)轉換為統(tǒng)一形式的系數(shù)矩陣MA，其中不同變量對應著相應的列，不同約束對應著相應的行。若某條約束中不包含個別變量，則在MA中對應行列的系數(shù)值為0。比如在式(3)中并不包含變量yij、lii′jj′p、cijp、ei,那么在MA中代表式(3)所有展開的行中，以上變量對應的列中系數(shù)均為0。對于式(2)來說，我們可以將其轉換為雙向關系約束，即將“等于”轉換為“大于等于”和“小于等于”。常數(shù)列向量則是各個約束中的常數(shù)移到不等式右邊得到的，通過上述的方法很容易得到，這樣我們就可以得到一個系數(shù)矩陣MA和常數(shù)列向量。

下一步我們將矩陣根據(jù)變量的不同類型將其劃分成兩個部分，即MA=(A，B)。A為0-1變量列代表的MA中部分矩陣，B為純整數(shù)變量列代表的MA中部分矩陣。在本文建立的數(shù)學模型中，0-1變量包括yij、lii′jj′p，純整數(shù)變量包括xij、ei、cijp?？梢愿鶕?jù)實際問題的規(guī)模將這兩種變量對應的列分離成矩陣A和矩陣B。目標函數(shù)中系數(shù)行向量也以此方法得到，就本文模型而言，目標函數(shù)中系數(shù)行向量中除變量ei所對應的列的系數(shù)為1，其余列系數(shù)均為0。最終我們得到形如問題式(12)的0-1混合整數(shù)規(guī)劃：

(18)

s.t.AY+BX≤r3

Y∈{0,1}X∈Z+

式中:Y=(y,l),X=(x,e,c),且均為列變量。

綜上所述，改進Benders算法具體流程如下：

Step1設置初始UB、LB和程序終止閾值ε，并賦予兩組0-1列變量(y*、l*)和(y**、l**)初始值，up和ud均為空集。轉Step2。

Step2求解利用(y*，l*)產生的問題的對偶問題Q。若問題Q存在最優(yōu)解，將(y*，l*)值賦予(y**，l**)。并相應得到一個pareto最優(yōu)割平面，同時更新up。此時子問題最優(yōu)值若小于當前UB則其值代替UB，并通過引入列變量(optimy，optiml)記錄當前最優(yōu)解(y*，l*)；若子問題存在無界解，則相應得到一個Benders可行割平面，并更新ud。轉Step3；

Step3根據(jù)當前UB、LB與ε值判斷程序是否終止。若滿足終止條件，則UB為原始問題最優(yōu)值。轉Step5；否則轉Step4。

Step4求解更新up和ud后的Benders主問題，根據(jù)θ最優(yōu)值修正當前LB，并將最優(yōu)解賦給(y*,l*)。轉Step2；

Step5(optimy,optiml)為原始問題中列變量(y,l)最優(yōu)值，分別代入原始問題約束式(2)-式(10)中，此時求解原始問題最優(yōu)解，問題求解結束。

算法具體流程如圖1所示。

圖1 算法流程圖

3 仿真算例與分析

3.1 參數(shù)設計

(1) 協(xié)同制造網(wǎng)絡設計 一般來說，不同類型產品加工網(wǎng)絡差距較大。結合實際生產情況，本文設計3種不同類型的加工網(wǎng)絡。每類加工網(wǎng)絡中每一個節(jié)點都代表不同的協(xié)同制造企業(yè)，每個企業(yè)都可以根據(jù)自身生產資源參與不同訂單產品的加工。圖2為平衡型加工網(wǎng)絡。這種網(wǎng)絡是生產比較平衡的一種情況，每個網(wǎng)絡節(jié)點都有多個均勻的上下游節(jié)點可供選擇，一般此類網(wǎng)絡的物流比較平均(規(guī)則網(wǎng)絡)，網(wǎng)絡壓力較小。圖3為瓶頸型加工網(wǎng)絡。瓶頸型加工網(wǎng)絡表明由于某些制造工序的特殊性，網(wǎng)絡中可行加工路徑必須經(jīng)過某些節(jié)點，因此生產網(wǎng)絡的總生產能力會受到這些節(jié)點的制約。圖4為跳躍型加工網(wǎng)絡。對于跳躍型加工網(wǎng)絡，主要是考慮到不同的企業(yè)的加工能力不同，針對相同的產品有的企業(yè)可以完成連續(xù)多個工序的加工任務，由此一旦加工路線經(jīng)過此類網(wǎng)絡節(jié)點，可以較快到達網(wǎng)絡終點。

圖2 平衡型加工網(wǎng)絡

圖3 瓶頸型加工網(wǎng)絡

圖4 跳躍型加工網(wǎng)絡

(2) 相關加工參數(shù)設計 在本文的仿真算例中假設接受生產三種不同類型的產品，平衡型、瓶頸型、跳躍型三種協(xié)同制造網(wǎng)絡各代表一種產品，可行路徑數(shù)目為8、8、4。這三種產品的需求數(shù)量分別為30、40、30，每10個產品為1批，共11家協(xié)同制造企業(yè)參與提供生產資源。每家企業(yè)生產不同訂單單件產品所需時間與企業(yè)間運輸時間分別如表1、表2所示。

表1 不同企業(yè)對不同訂單加工時間 h

表2 企業(yè)間運輸時間 h

鑒于篇幅，本文將全部訂單的每條可行加工路徑中各個協(xié)同企業(yè)間的運輸時間總結在一起。為了避免混淆，下面本文通過例子詳細說明，比如本文將生產路徑m2→m5→m3→m7→m11作為訂單1的第1條生產路徑，則在矩陣T11(p,q)中只有2行5列、5行3列、3行7列為非0值，其值等于表2中相應位置值(表頭除外)。

3.2 仿真結果描述

表3 具體調度方案

以上具體求解結果中，訂單1-訂單3的最終完工時間分別360、400、235 h，總最小完工時間為995 h。從路徑y(tǒng)15、y18中在企業(yè)6和后續(xù)企業(yè)的加工時段可以看出，企業(yè)6在連續(xù)生產20件訂單1產品后，分別向企業(yè)3、8分配了10件產品的生產任務，這將減少產品在協(xié)同制造網(wǎng)絡中的流通時間。為了驗證分流協(xié)同加工方式可以有效縮短產品在生產中流通時間，我們取消分流生產方式后求解該仿真算例，得到最小總加工時間為1 840 h。在算法性能上，我們也使用傳統(tǒng)Benders算法對算例進行求解，并與基于pareto最優(yōu)割改進的Benders算法進行比較。通過仿真，傳統(tǒng)Benders算法耗時22 337 s，迭代次數(shù)為5 728次；改進Benders算法耗時14 152 s，迭代次數(shù)3 819次。仿真結果表明改進算法具有明顯的優(yōu)勢，從而驗證了改進算法的有效性。

4 結 語

本文以多種產品協(xié)同制造網(wǎng)絡對供應鏈調度問題進行了研究。為了使研究更具普適性，設計三種不同類型的協(xié)同制造網(wǎng)絡。同時，本文考慮產品可以成批量分流加工，以總最小完工期為目標建立了0-1混合整數(shù)規(guī)劃模型。最后針對本文問題特點采用Benders分解算法進行精確求解。為了提高求解效率,本文利用pareto最優(yōu)割替換Benders最優(yōu)割改進傳統(tǒng)Benders算法。仿真結果表明,利用改進Benders算法可有效提高問題求解效率。