付立坤++喬佩利

摘 要：主要研究生產(chǎn)計劃下的多級供應(yīng)鏈伙伴之間的協(xié)調(diào)優(yōu)化問題.在多階段多項目約束生產(chǎn)批量問題模型的基礎(chǔ)上，考慮關(guān)聯(lián)約束及相關(guān)需求約束，對整個供應(yīng)鏈的生產(chǎn)計劃問題利用拉格朗日松弛算法將其分解為多個子問題，并應(yīng)用自適應(yīng)分布式算法更新內(nèi)部價格來協(xié)調(diào)各成員之間的決策，實現(xiàn)了多級供應(yīng)鏈批量生產(chǎn)問題的協(xié)調(diào)優(yōu)化，以及較好的保證各成員隱私，實驗分析證明了該策略在協(xié)調(diào)多級供應(yīng)鏈生產(chǎn)計劃問題具有優(yōu)越性，

關(guān)鍵詞：供應(yīng)鏈協(xié)調(diào)：樹搜索；自適應(yīng)分布式

DOI：1O.15938/j.jhust.2015.02.015

中圖分類號：TP399

文獻標(biāo)志碼：A

文章編號：1007-2683（2015）02-0080-05

0 引 言

供應(yīng)鏈管理（SCM）是在充分利用資源條件下，通過協(xié)調(diào)供應(yīng)鏈中各成員間相互關(guān)系，以實現(xiàn)供應(yīng)鏈整體的協(xié)調(diào)優(yōu)化，供應(yīng)鏈運作計劃在SCM主要在滿足客戶服務(wù)約束的前提下，負責(zé)協(xié)調(diào)供應(yīng)鏈上資源的調(diào)配，物料的供需關(guān)系，以及優(yōu)化供應(yīng)鏈總成本.在以往關(guān)于供應(yīng)鏈協(xié)調(diào)問題的研究中，較為常用的方法是層次式模式，假定由一個決策者掌握了全部的信息，并集中對協(xié)調(diào)問題進行決策，供應(yīng)鏈中的信息具有私有性、實時性、非對稱性等特性，雖然層次式模式通常情況下，可高效獲得全局最優(yōu)策略，但如果供應(yīng)鏈有多個決策者，則無法使用層次式模式.文提出一種在不干涉自主決策實體的決策權(quán)和私有信息等條件下，又能夠有效的協(xié)調(diào)和優(yōu)化整個供應(yīng)鏈運作的模式，并用拉格朗日松弛技術(shù)和遺傳算法對多級多成員批量生產(chǎn)供應(yīng)鏈問題進行協(xié)調(diào)優(yōu)化，但其效率并不是最優(yōu)的.文根據(jù)協(xié)調(diào)理論分析了供應(yīng)鏈在物流、資源共享和時序間的依懶關(guān)系，并用拉格朗日松弛算法對模型進行協(xié)調(diào)優(yōu)化.文運用拉格朗日松弛技術(shù)和啟發(fā)式算法協(xié)調(diào)優(yōu)化的多廠生產(chǎn)計劃內(nèi)部價格問題，有相對較好的優(yōu)化性能，文基于協(xié)調(diào)企業(yè)和代理商之間供需關(guān)系，采用基于自適應(yīng)分布式搜索算法來縮短整個供應(yīng)鏈協(xié)調(diào)過程巾的所耗費的時間，每次提出的協(xié)調(diào)策略都是最優(yōu)的.

在供應(yīng)鏈中合作伙伴尋求競爭優(yōu)勢，如在短時問內(nèi)不斷滿足成員多樣化需求的能力，本研究著重從宏觀角度看，是一個典型的規(guī)劃和調(diào)度問題.在本研究中，將拉格朗日松弛算法和自適應(yīng)分布式算法結(jié)合起來，以協(xié)調(diào)各成員子問題間的決策，

本研究中，先利用拉格朗日松弛算法簡化多廠供應(yīng)鏈問題，并用自適應(yīng)分布式搜索算法對其進行協(xié)調(diào)優(yōu)化.首先，將多級供應(yīng)鏈生產(chǎn)計劃問題模型用拉格朗日松弛算法分解為多個相對獨立成員的子問題，降低問題本身的復(fù)雜度，其次，提出該模型可行解的構(gòu)造方法，將問題模型用樹形結(jié)構(gòu)表示，并用自適應(yīng)分布式搜索算法子問題進行協(xié)調(diào)優(yōu)化，最后，對供應(yīng)鏈整體進行協(xié)調(diào)優(yōu)化.

1 多級供應(yīng)鏈問題

1. 1 優(yōu)化模型

如多級供應(yīng)鏈生產(chǎn)計劃問題是指在某一計劃時問內(nèi)，最終產(chǎn)品需求以及對應(yīng)其產(chǎn)品結(jié)構(gòu)的物料清單，并為最終產(chǎn)品加工或裝配部件的成員企業(yè)制定生產(chǎn)計劃，以達到最小化總成本的目的，其本質(zhì)是為多級多產(chǎn)品受約束的批量問題（multi-level，multi-i-tem Capacitaled Lot-Sizing Problern，MLCLSP）.在本模型的計算過程中，假定產(chǎn)品所需提前周期為0.MLCLSP的主要約束包括：1）成員企業(yè)提供資源的數(shù)量約束和物料之問的順序約束；2）最大庫存能力約束；3）企業(yè)n的加工能力約束.符號定義如下： Prn為工廠n乍產(chǎn)的產(chǎn)品集合；Ok為生產(chǎn)產(chǎn)品k所需要的原料集合；D（n，k）為企業(yè)中所有下游工廠以工廠n的產(chǎn)品k為原料的集合；U（n，1）為企業(yè)中所有L游工廠為工廠n提供原料f的集合；為周期為t寸，下游工廠m向上游丁廠，n請求的產(chǎn)品k的產(chǎn)品數(shù)量；為周期為t時，上游工廠n向下游工廠m提供的產(chǎn)品k的產(chǎn)品數(shù)量；T為整個生命周期；hnk為工廠n對于產(chǎn)品k的單位庫存a費用；Snk為工廠n對于產(chǎn)品k的setup費用；Cn，k為工廠，n對于產(chǎn)品k的單位生產(chǎn)費用；dn，k為外部市場生產(chǎn)周期t時，對工廠n的產(chǎn)品k的需求量；trn，k為工廠n生產(chǎn)產(chǎn)品k的setup時問；tbn，k為工廠n生產(chǎn)單位產(chǎn)品k耗時；capn，1為工廠n在生產(chǎn)周期t的加工能力；/i：'ak為工廠n對于產(chǎn)品k的最大庫存能力；k.1β為產(chǎn)品k和產(chǎn)品2之間的物料清單關(guān)系；M為大的正數(shù)；Xn.k.為工廠n中產(chǎn)品k在生產(chǎn)周期t時的生乍產(chǎn)量為工廠n中產(chǎn)品k在生產(chǎn)周期t結(jié)束時對應(yīng)的庫存數(shù)量；為為0-1變量，如果生產(chǎn)取值為1，則表示工廠n在生產(chǎn)周期f時，是生產(chǎn)產(chǎn)品k，反之亦然.

在模型中，式（1）為最小化供應(yīng)鏈總成本；式（2）為庫存平衡約束；式（3）為產(chǎn)品的物料消單關(guān)系和T廠，z相對于其全部的上游工廠的原料需求；式（4）為工廠n的產(chǎn)品生產(chǎn)加工能力；式（5）為工廠在產(chǎn)品生產(chǎn)時，所需固定值的生產(chǎn)準(zhǔn)備費用；式（6）為企業(yè)的產(chǎn)品庫存最大值；式（7）表示物料在上下游工廠的平衡約束條件，保證上下游工廠的供需平衡.

1.2 模型的拉格朗日分解

拉格朗日松弛算法通過拉格朗日乘子，將模型中復(fù)雜約束作為懲罰項整合到目標(biāo)函數(shù)中，以降低問題的復(fù)雜度，拉格朗日松弛式（8），將拉朗格朗日乘子整合到目標(biāo)函數(shù)中，可將原問題分解為一組成員獨立的子問題，能較好的保證成員信息的隱私.拉格朗日算子A表示對不符合產(chǎn)品上下游供應(yīng)平衡約束的懲罰.本文稱其為產(chǎn)品的內(nèi)部價格，其中示工廠的原料成本.在確定產(chǎn)品的內(nèi)部價格后，式（9）中所有變量為工廠的本地變量，無需其它工廠信息.拉格朗日分解后模型MLCLSP為：

2 自適應(yīng)分布式搜索算法

2.1 建立樹形結(jié)構(gòu)

次梯度算法常用于求解拉格朗日松弛算法分解后的子問題.在本模型中，分解后的子問題為線性目標(biāo)函數(shù)，如果采用次梯度對其求解，將產(chǎn)生振蕩，難于收斂.拉格朗日松弛技術(shù)對于成員企業(yè)之間的信息必須保證全部共享，對于本模型來說，并不適用.因此本文建立的協(xié)調(diào)結(jié)構(gòu)和協(xié)調(diào)過程內(nèi)嵌了一個基于自適應(yīng)分布式可行化方法，該方法不需要集成模型和成員的全部信息，在可行化過程中，自適應(yīng)算法淘汰可能會失敗的拉格朗日乘子，保證能求得問題的可行解.雖然增加了淘汰步驟，但在汁算過程中，子問題是并行計算，所耗費時間很短.為此，本文在拉格朗日松弛算法的基礎(chǔ)上，運用自適應(yīng)分布式搜索算法，進行可行化求解.

圖l為多級供應(yīng)鏈生產(chǎn)計劃問題的用樹形表示的結(jié)構(gòu)圖.樹的根節(jié)點是協(xié)調(diào)中心，根節(jié)點制定產(chǎn)品的內(nèi)部價格，以及協(xié)調(diào)各個工廠.A、B、C為3個工廠，作為根節(jié)點的子節(jié)點，3個工廠根據(jù)自己的本地信息，在獲得內(nèi)部價格后，可得到各自工廠的生產(chǎn)計劃，并將確定各自向上游工廠提出的原料需求量，和向下游工廠提供的產(chǎn)品供給量，以及所得優(yōu)化結(jié)果傳給根節(jié)點.10種產(chǎn)品作為工廠節(jié)點的子節(jié)點，生產(chǎn)計劃結(jié)果和其它信息通過枝進行傳遞，協(xié)調(diào)中心根據(jù)接收到的消息，更新內(nèi)部價格，然后將其傳送給各個工廠.一直執(zhí)行該步驟，直到得出最優(yōu)決策，才停止運行.

2.2優(yōu)化算法

自適應(yīng)分布式搜索算法是一種全局性的搜索算法.許多研究者采用失敗學(xué)的方法處理樹在遍歷過程中違反約束導(dǎo)致失敗的情況，并分析樹在整個搜索中的其余部分，它具有對函數(shù)的形態(tài)無要求、搜索效率高、較好的全局搜索能力等優(yōu)勢，并且可以處理混合參數(shù)的約束優(yōu)化問題.自適應(yīng)方法涉及系統(tǒng)的動態(tài)響應(yīng)和調(diào)整特定實例的求解過程，能充分利用問題的約束條件.自適應(yīng)算法的實現(xiàn)通常為：1）更新數(shù)據(jù).每次遍歷一個新的節(jié)點，可能會引起相關(guān)節(jié)點的數(shù)據(jù)變化，及時更新數(shù)據(jù)，自適應(yīng)判斷是否更新當(dāng)前節(jié)點的數(shù)據(jù)，即對全局決策無影響，不更新除父節(jié)點和本身節(jié)點以外的節(jié)點.2）選擇節(jié)點，最優(yōu)決策通過系統(tǒng)地遍歷樹的所有節(jié)點，根據(jù)節(jié)點的屬性值判斷獲得最優(yōu)策略的可能性，可動態(tài)搜索概率最高的節(jié)點.每次通過比較該次得到的策略與上次最優(yōu)策略，保存對比后較優(yōu)策略對應(yīng)的數(shù)據(jù)和路徑.當(dāng)搜索到最優(yōu)決策之后，便停止搜索.本步驟的所有操作在多節(jié)點上都是并行進行處理.3）網(wǎng)溯節(jié)點.根據(jù)約束條件或者搜索到葉子后，采用回溯方法，常用的回溯方法是SyncLDS（ synchronous limited dis-crepancy search）

對應(yīng)本模型的具體步驟如下：

步驟1：初始化參數(shù).如制定初始的產(chǎn)品內(nèi)部價格、各個節(jié)點值、節(jié)點之間的關(guān)系變量、初始化掩格朗日乘子、最大迭代次數(shù)等，

步驟2：各獨立成員接收由協(xié)調(diào)中心所推送的拉格朗日乘子，在協(xié)調(diào)中心局部求解過程中，采用模糊次梯度算法進行更新.在協(xié)調(diào)過程中，協(xié)調(diào)中心采用自適應(yīng)方法對優(yōu)化結(jié)果進行判斷.為第一種，其他為.其中J為最優(yōu)解的估計值.這里選擇步長α5滿足：

步驟3：每個獨立成員在拉格朗日乘子的基礎(chǔ)上，并行計算f值，并將所得結(jié)果傳送給協(xié)調(diào)中心.

步驟4：上游成員把下游成員的X品作為子問題模型中參數(shù)xkit的輸入值，然后更新值，，并向根節(jié)點（即協(xié)調(diào)中心）發(fā)送可行性和值fe，同時迭代次數(shù)n減1.

步驟5：如果迭代次數(shù)達到最大值，則轉(zhuǎn)向步驟6，否則，根據(jù)白適應(yīng)方法，直到得到最優(yōu)結(jié)果，才停止運行.

步驟6：輸出最優(yōu)解后，停止運行.

3 實例與分析

采用文中標(biāo)準(zhǔn)MLCLSP問題中的ClassB集的非循環(huán)產(chǎn)品結(jié)構(gòu)，最終產(chǎn)出4個最終產(chǎn)品，用該實例驗證白適應(yīng)分布式搜索算法的如何求解多級供應(yīng)鏈生產(chǎn)計劃問題.每級對應(yīng)有一個成員（成員各有一種資源）的三級供應(yīng)鏈中，擁有10種物料，成員之問的物流結(jié)構(gòu)關(guān)系如圖2所示.利用文[3]中的方法，生產(chǎn)準(zhǔn)備成本可分為：1）生產(chǎn)規(guī)模均衡、準(zhǔn)備成本相對低；2）生產(chǎn)規(guī)模均衡、準(zhǔn)備成本適中；3），生產(chǎn)規(guī)模均衡、生產(chǎn)準(zhǔn)備成本高；4）下游準(zhǔn)備成本較低和上游準(zhǔn)備成本較高時；5）下游準(zhǔn)備成本較高和上游準(zhǔn)備成本較低時，其中p為變化的資源利用率，取值情況如表l所示.3種需求模式，通過不同的變異系數(shù)改變需求，變異系數(shù)（coefficients ofvariation）分別為0.1，0.4，0.7.共計75個問題，

平均每個時期的需求為最終產(chǎn)品的組裝結(jié)構(gòu)中被設(shè)置為100.實例中，大的正數(shù)M=1000，物料k的庫存保存成本和生產(chǎn)準(zhǔn)備成本參數(shù)如表2所示，

可利用Visual Studio 2005實現(xiàn)供應(yīng)鏈運作汁劃協(xié)調(diào)算法（拉格朗日松弛技術(shù)與自適應(yīng)分布式算法），對成員獨立的子問題的求解可用Liogo11軟件.拉格朗日乘子取值范圍介于-100到100之間，最大代數(shù)值為100.首先，將通過Lingol1軟件求解所得到最優(yōu)解作為評價其它算法性能的一個基準(zhǔn)，在拉格朗日松弛的基礎(chǔ)上，對比白適應(yīng)分布式算法和文中的LRCASCP算法求解問題的結(jié)果，如表3所示.表中的偏差由兩種算法的解與基準(zhǔn)對比可得，如圖3所示.

偏差為通過計算所得的最優(yōu)結(jié)果和基準(zhǔn)的之間的差：其中：t，為初始最優(yōu)解；J*為整個問題計算所得的最優(yōu)解.

如表2結(jié)果顯示，自適應(yīng)分布式搜索算法和LRGASCP算法的優(yōu)化性能基本不依賴于問題的結(jié)構(gòu)，相對比自適應(yīng)分布式算法的平均偏差更低些.

由表3和圖3可得，在75個問題中，應(yīng)用LR—CASCP算法所得偏差為1.47%；自適應(yīng)分布式搜索算法的情況，偏差在l%以內(nèi)占問題總數(shù)的61%，問題偏差在5%以內(nèi)占問題總數(shù)的97%.對比可知，自適應(yīng)分布式搜索算法具有優(yōu)越性和魯棒性.將自適應(yīng)分布式搜索算法、LRGASCP算法同文中所提到的中心強制、一般協(xié)調(diào)和最大公平協(xié)調(diào)，以及文中的內(nèi)部價格協(xié)調(diào)與基準(zhǔn)比較后的偏差進行對比，結(jié)果如表4所示.顯而易見，在相同問題集的情況下，白適應(yīng)分布式搜索算法的優(yōu)化性能在這幾種協(xié)調(diào)機制中是最高的.

在求解問題的計算過程中，各成員獨立子問題的求解占據(jù)了大部分的運行時間，自適應(yīng)分布式搜索算法具有分布式的特性，即成員子問題的決策計算過程都是并行進行計算，可減少子問題串行計算所消耗的時間，因此，該算法具有較高的運算效率.

4 結(jié) 論

本文針對多階段多項目批量供應(yīng)鏈協(xié)調(diào)優(yōu)化問題，在拉格朗日松弛算法的基礎(chǔ)上，運用白適應(yīng)分布式搜索算法協(xié)調(diào)產(chǎn)品的內(nèi)部價格協(xié)調(diào)策略，應(yīng)用拉格朗日松弛技術(shù)分解簡化本文中的數(shù)學(xué)模型，可得到多個成員獨立的子問題，子問題的運算復(fù)雜性較低，其中，協(xié)調(diào)中心主要是對拉格朗日乘子進行更新，來達到對各個成員決策的協(xié)調(diào)優(yōu)化目的，利用自適應(yīng)分布式搜索算法來求解成員的子問題，可降低了求解問題的復(fù)雜度，并具有高效性.實驗結(jié)果表明，與其它多種協(xié)調(diào)機制對比，自適應(yīng)分布式搜索算法具有優(yōu)越性以及魯棒性.