魏成平，張松柏

（烏魯木齊職業(yè)大學(xué)，新疆 烏魯木齊 830002）

1 引言

基于市場(chǎng)機(jī)遇而構(gòu)建的供應(yīng)鏈網(wǎng)絡(luò)是一個(gè)復(fù)雜的自組織系統(tǒng)[1]，具有后效性，對(duì)上游供應(yīng)商與下游需求商造成影響。增強(qiáng)系統(tǒng)的穩(wěn)定性與環(huán)境適應(yīng)性，提高系統(tǒng)的整體效率，成為供應(yīng)鏈理論與實(shí)踐應(yīng)用面臨的緊迫課題。

郭永輝[2]比較了供應(yīng)鏈產(chǎn)能規(guī)劃與傳統(tǒng)產(chǎn)能規(guī)劃的區(qū)別。齊二石等[3]通過(guò)對(duì)復(fù)雜零件協(xié)同制造任務(wù)進(jìn)行分解，建立了協(xié)同制造資源優(yōu)化配置模型。孫榮庭等[4]在需求為不確定的情況下，研究了存在零售商橫向競(jìng)爭(zhēng)的1:n結(jié)構(gòu)的供應(yīng)鏈協(xié)調(diào)問(wèn)題。蔡建湖，黃衛(wèi)來(lái)及周根貴[5]建立了供應(yīng)商與零售商之間的動(dòng)態(tài)博弈。桂云苗等[6]建立供應(yīng)鏈網(wǎng)絡(luò)設(shè)計(jì)的魯棒優(yōu)化模型，提出了模型求解的混合智能算法。劉小華和林杰[7]將供應(yīng)鏈調(diào)度優(yōu)化問(wèn)題進(jìn)行數(shù)學(xué)規(guī)劃建模，構(gòu)造了一種混合算法。

以往的研究?jī)?nèi)容缺乏對(duì)供應(yīng)鏈上下游企業(yè)間的互動(dòng)與協(xié)調(diào)方面的研究。但在當(dāng)今這種經(jīng)濟(jì)環(huán)境下，生產(chǎn)往往是在一個(gè)多級(jí)制造系統(tǒng)中完成，在生產(chǎn)過(guò)程中會(huì)根據(jù)各種實(shí)際情況在上下游制造企業(yè)之間出現(xiàn)優(yōu)先級(jí)的關(guān)系。所以，如果以提升整個(gè)供應(yīng)鏈競(jìng)爭(zhēng)力為目的來(lái)研究供應(yīng)鏈，則對(duì)于生產(chǎn)環(huán)節(jié)的研究特別是對(duì)多級(jí)制造環(huán)節(jié)的研究顯得尤為重要。本文旨在針對(duì)多級(jí)制造環(huán)節(jié)的供應(yīng)鏈系統(tǒng)研究其能力分配問(wèn)題，從而對(duì)該供應(yīng)鏈上各企業(yè)進(jìn)行把控，根據(jù)整個(gè)供應(yīng)鏈的生產(chǎn)能力以及生產(chǎn)和銷售需求情況及時(shí)發(fā)現(xiàn)瓶頸企業(yè)和異常問(wèn)題，以銷售需求為導(dǎo)向，調(diào)整生產(chǎn)計(jì)劃和資源分配，對(duì)各種突發(fā)事件做出即時(shí)響應(yīng)，以提高供應(yīng)鏈的整體競(jìng)爭(zhēng)力。

2 帶有多級(jí)制造環(huán)節(jié)的供應(yīng)鏈問(wèn)題模型

2.1 模型描述

供應(yīng)鏈問(wèn)題共分為生產(chǎn)環(huán)節(jié)和銷售環(huán)節(jié)。其中生產(chǎn)環(huán)節(jié)由原材料供應(yīng)商和多級(jí)生產(chǎn)制造商組成，且最后一級(jí)為最終產(chǎn)品制造商（如圖1所示）。每級(jí)的供應(yīng)商或制造商均由多個(gè)企業(yè)組成，且同級(jí)各企業(yè)的產(chǎn)品在產(chǎn)品組成、產(chǎn)品用途方面有一定的相似度、而不同級(jí)別企業(yè)的產(chǎn)品是一種加工與被加工的關(guān)系，其中每一級(jí)的制造商所制造的產(chǎn)品均為下一級(jí)的制造商準(zhǔn)備，相鄰兩級(jí)的供應(yīng)商或制造商之間的供給存在一個(gè)多對(duì)多的關(guān)系。由于該供應(yīng)鏈模型主要研究帶有多級(jí)制造的生產(chǎn)環(huán)節(jié)，所以對(duì)銷售環(huán)節(jié)進(jìn)行簡(jiǎn)化，簡(jiǎn)化為由多個(gè)分銷商組成一級(jí)銷售環(huán)節(jié)，在以整體供應(yīng)鏈效益最優(yōu)的前提下，各個(gè)分銷商之間是一種相互合作同時(shí)又相互制約的關(guān)系。由于是以整個(gè)供應(yīng)鏈為研究對(duì)象，所以最終需要實(shí)現(xiàn)的目標(biāo)是在充分滿足銷售需求的情況下盡可能的使整體供應(yīng)鏈的利潤(rùn)最大化及合同飽和度最大化，從而提升其在市場(chǎng)中的競(jìng)爭(zhēng)力。

圖1 帶有多級(jí)制造環(huán)節(jié)的供應(yīng)鏈能力分配問(wèn)題

2.2 模型假設(shè)

為了便于建立數(shù)學(xué)模型，并使數(shù)學(xué)模型更接近現(xiàn)實(shí)生產(chǎn)，需要對(duì)該供應(yīng)鏈模型提出一些假設(shè)條件。

（1）整個(gè)供應(yīng)鏈中企業(yè)之間實(shí)現(xiàn)了信息共享，從而實(shí)現(xiàn)了供應(yīng)與需求的有機(jī)銜接。

（2）整個(gè)供應(yīng)鏈?zhǔn)且凿N售需求為導(dǎo)向來(lái)進(jìn)行生產(chǎn)的，即根據(jù)最終分銷商的合同需求量來(lái)安排生產(chǎn)流程及資源分配情況。

（3）假設(shè)所有企業(yè)生產(chǎn)的產(chǎn)品及整個(gè)銷售市場(chǎng)物價(jià)穩(wěn)定，暫不考慮隨市場(chǎng)供需關(guān)系等影響而出現(xiàn)物價(jià)波動(dòng)現(xiàn)象。

（4）每個(gè)分銷商均會(huì)有多個(gè)訂單需求即需求訂單集，且在為每個(gè)產(chǎn)品選擇最終制造商時(shí)也會(huì)有優(yōu)先級(jí)的關(guān)系。

（5）每個(gè)供應(yīng)商和制造商只生產(chǎn)一種產(chǎn)品，最終產(chǎn)品制造商生產(chǎn)的產(chǎn)品可能相同。

（6）為了能夠有效的表示在生產(chǎn)環(huán)節(jié)中各個(gè)生產(chǎn)企業(yè)本身的差異性，即各個(gè)企業(yè)之間存在不同的生產(chǎn)成本、運(yùn)輸成本、企業(yè)間合作程度等，所以為每一個(gè)制造商所對(duì)應(yīng)的上游供應(yīng)商或制造商添加優(yōu)先級(jí)。

（7）假設(shè)每個(gè)企業(yè)的生產(chǎn)能力有限，整個(gè)供應(yīng)鏈的產(chǎn)能并不能完全滿足銷售需求，所以需要進(jìn)行擇優(yōu)生產(chǎn)以實(shí)現(xiàn)利潤(rùn)最大化及合同飽和度最大化。

2.3 符號(hào)定義

在建立數(shù)學(xué)模型之前，首先定義符號(hào)如下：

2.4 數(shù)學(xué)模型

基于以上符號(hào)定義，并根據(jù)之前提出的假設(shè)條件，則帶有多級(jí)制造環(huán)節(jié)的供應(yīng)鏈問(wèn)題的數(shù)學(xué)模型描述如下：

（1）目標(biāo)函數(shù)。最大化產(chǎn)品利潤(rùn)：

最大化合同飽和度：

其中：和分別表示第m個(gè)最終產(chǎn)品制造商對(duì)其第l個(gè)分銷商的產(chǎn)品供給量所對(duì)應(yīng)的產(chǎn)品利潤(rùn)；Contr表示第l個(gè)分銷商對(duì)產(chǎn)品j的合同需求量。

（2）約束。分銷商的最大供給量約束：

供應(yīng)商或制造商供應(yīng)或生產(chǎn)的最大產(chǎn)能約束：

上游供應(yīng)商或制造商對(duì)下游制造商的最大供應(yīng)量約束：

下游制造商選擇上游制造商或供應(yīng)商的優(yōu)先級(jí)約束：

生產(chǎn)中某企業(yè)的上下游關(guān)系平衡約束：

其中，約束（8）、（9）表示流向變量，其中約束（8）表示若產(chǎn)品p不能生產(chǎn)產(chǎn)品q則沒(méi)有產(chǎn)品流量，約束（9）表示若產(chǎn)品p能生產(chǎn)產(chǎn)品q則一定有產(chǎn)品流量；約束（10）表示共享資源約束下的某企業(yè)生產(chǎn)量的計(jì)算公式；約束（11）表示共享資源約束下的某企業(yè)得到的分配量的計(jì)算公式。

3 基于鄰域搜索的約束滿足算法設(shè)計(jì)

3.1 適應(yīng)度函數(shù)設(shè)計(jì)

根據(jù)第2 節(jié)的模型可以發(fā)現(xiàn)，式（1）、（2）兩個(gè)目標(biāo)函數(shù)均存在最大值，即所要求解的供應(yīng)鏈模型存在理想點(diǎn)，即是當(dāng)銷售需求完全滿足時(shí)，整個(gè)供應(yīng)鏈系統(tǒng)能實(shí)現(xiàn)的利潤(rùn)是最大的，同時(shí)合同飽和度也是最大的。所以本文在設(shè)計(jì)算法的適應(yīng)度函數(shù)時(shí)便采用理想點(diǎn)法。

首先，將式（1）進(jìn)行無(wú)量綱化處理：

其中，表示第l個(gè)分銷商在完成第j個(gè)產(chǎn)品的合同需求時(shí)只取該分銷商對(duì)應(yīng)的生產(chǎn)第j 個(gè)最終產(chǎn)品制造商集合中利潤(rùn)最大值。即如式（13）所示:

由上述分析可知，式（2）中f2和式（12）中的f3最大值均為1，所以解（1,1）即為該供應(yīng)鏈模型的理想點(diǎn)。由于產(chǎn)能限制不能完成所有合同訂單，所以真正所要求的最優(yōu)解只能無(wú)限逼近理想點(diǎn)，故算法的適應(yīng)度函數(shù)可以設(shè)為所有解與理想點(diǎn)之間的距離，即：

所以在算法迭代過(guò)程中便是求式（14）的最小值。

3.2 鄰域的構(gòu)造

本文所要求解的供應(yīng)鏈問(wèn)題模型為連續(xù)值組合優(yōu)化問(wèn)題，且編碼設(shè)計(jì)采用的是整數(shù)編碼制，所以本文采用交換的方式來(lái)構(gòu)造鄰域。結(jié)合本文所提出的數(shù)學(xué)模型，在交換操作后，由于存在每個(gè)訂單的最大合同量及每個(gè)產(chǎn)品的最大產(chǎn)能，所以如果交換后出現(xiàn)沖突，則根據(jù)式（15）進(jìn)行調(diào)整。

由于該模型中存在優(yōu)先級(jí)，使得該數(shù)學(xué)模型變?yōu)榉蔷€性模型，一個(gè)值的變動(dòng)會(huì)影響許多相關(guān)值的變動(dòng)，所以經(jīng)常會(huì)出現(xiàn)在生成鄰域解時(shí)，當(dāng)兩個(gè)值交換后在均未超出最大產(chǎn)能和合同量的前提下，兩個(gè)值仍存在沖突，導(dǎo)致整個(gè)解的不可行。根據(jù)式（1）可知，本文最終的最重要的目標(biāo)是要實(shí)現(xiàn)利潤(rùn)最大化，所以當(dāng)出現(xiàn)上述沖突時(shí)，優(yōu)先保證要交換的兩個(gè)合同訂單中利潤(rùn)大的訂單供應(yīng)量為交換后的結(jié)果，之后再根據(jù)約束傳播技術(shù)調(diào)整新解的可行性。

3.3 算法步驟

所設(shè)計(jì)的基于鄰域搜索的約束滿足算法首先通過(guò)貪婪思想生成初始解之后利用鄰域搜索技術(shù)生成新的解集以跳出局部最優(yōu)。整個(gè)算法是以約束滿足算法為整體，同時(shí)在其中嵌入鄰域搜索技術(shù)來(lái)實(shí)現(xiàn)的。具體算法步驟如下所述：

Step1（初始化變量選擇規(guī)則）算法的決策變量根據(jù)分銷商所提供的訂單產(chǎn)品按盈利能力即按從大到小排序。

Step2（生成初始解）

Step2.1 依次選取未賦值的決策變量為當(dāng)前變量，若決策變量集合中各變量均已賦值則轉(zhuǎn)向Step8，否則轉(zhuǎn)向Step3。

Step2.2為當(dāng)前變量賦初始值。

Step2.3 根據(jù)當(dāng)前變量的產(chǎn)品上下游關(guān)系確定上游變量集合USnd；若只有一個(gè)上游變量則轉(zhuǎn)向Step2.4；若存在多個(gè)上游變量，則轉(zhuǎn)向Step2.5；否則轉(zhuǎn)向Step2.6。

Step2.6 根據(jù)已遍歷路徑依次為路徑上各個(gè)變量賦值并轉(zhuǎn)向Step2.1。

Step2.7 輸出初始解。

Step3（終止條件判斷）算法是否已達(dá)到迭代次數(shù)，未達(dá)到迭代次數(shù)則轉(zhuǎn)向Step4.1，否則轉(zhuǎn)向Step5

Step4（鄰域搜索尋優(yōu)）

Step4.1 隨機(jī)交換解中任意兩個(gè)決策變量的值，生成新的鄰域解。

Step4.2 根據(jù)約束傳播技術(shù)，將新生成的鄰域解轉(zhuǎn)化為可行解。

Step4.3 根據(jù)適應(yīng)度函數(shù)更新當(dāng)前最優(yōu)解并轉(zhuǎn)向Step3。

Step5（輸出結(jié)果）輸出最優(yōu)解，算法結(jié)束。

4 鋼鐵企業(yè)實(shí)際應(yīng)用

為了驗(yàn)證算法的實(shí)用性，應(yīng)用算法對(duì)一些實(shí)際數(shù)據(jù)進(jìn)行計(jì)算，并希望借此進(jìn)一步挖掘算法對(duì)于實(shí)際應(yīng)用的價(jià)值。本算法用C#語(yǔ)言編寫，計(jì)算機(jī)配置：CPU：AMD Athlon（tm）Ⅱ×2 Processor2.90GHz；內(nèi)存：2GB。

4.1 試驗(yàn)設(shè)計(jì)

模擬數(shù)據(jù)仿真實(shí)驗(yàn)采用隨機(jī)生成數(shù)據(jù)的形式，分別對(duì)4、5、6、7 四個(gè)等級(jí)的供應(yīng)鏈問(wèn)題進(jìn)行約束滿足算法的求解。其中，在供應(yīng)鏈中每一級(jí)均有6個(gè)企業(yè)，即d=6，且預(yù)先給定上下游企業(yè)間的優(yōu)先級(jí)關(guān)系，同時(shí)模型中各種約束條件也以給定范圍的隨機(jī)數(shù)方式產(chǎn)生。

根據(jù)本文提出的供應(yīng)鏈數(shù)據(jù)模型及求解算法的需要，具體實(shí)驗(yàn)數(shù)據(jù)設(shè)置如下：

根據(jù)鄰域搜索相關(guān)文獻(xiàn)及實(shí)驗(yàn)數(shù)據(jù)規(guī)模設(shè)置算法最大迭代次數(shù)為100。

本實(shí)驗(yàn)上下游企業(yè)間優(yōu)先級(jí)關(guān)系在求解前需預(yù)先給出，表1即為一個(gè)5級(jí)供應(yīng)鏈問(wèn)題上下游企業(yè)間的優(yōu)先級(jí)關(guān)系。

表1 供應(yīng)鏈上下游企業(yè)優(yōu)先級(jí)關(guān)系

表1 中列表示供應(yīng)鏈等級(jí)，行表示每個(gè)等級(jí)下的企業(yè)編號(hào)，因?yàn)榈?級(jí)為供應(yīng)商，其沒(méi)有上游企業(yè)，故表中是從第2級(jí)開始。表中的優(yōu)先級(jí)序列即為其對(duì)應(yīng)上一級(jí)企業(yè)的優(yōu)先級(jí)關(guān)系，如第3 行第2 列的2,5,4,3 序列即表示第3 等級(jí)第2 號(hào)企業(yè)對(duì)應(yīng)第2 級(jí)企業(yè)集的優(yōu)先級(jí)關(guān)系為2 5 4 3，在實(shí)際計(jì)算時(shí)便會(huì)依照此序列順序安排生產(chǎn)。最后一級(jí)為分銷商，只有在最終產(chǎn)品制造商生產(chǎn)的產(chǎn)品相同時(shí)才會(huì)出現(xiàn)優(yōu)先級(jí)的概念，所以如表中所示，即可發(fā)現(xiàn)3 和6 號(hào)及2 和5 號(hào)企業(yè)生產(chǎn)的是同種產(chǎn)品。

4.2 實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證算法的有效性和實(shí)用性，將實(shí)驗(yàn)數(shù)據(jù)分別用傳統(tǒng)的約束滿足算法CSA與本文所設(shè)計(jì)的基于鄰域搜索的約束滿足算法NS-CAS求解計(jì)算，實(shí)驗(yàn)結(jié)果見(jiàn)表2、表3。

表2 CSA與NS-CAS計(jì)算結(jié)果比較

表3 CSA與NS-CAS求解完成時(shí)間比較

圖2 給出了以6 級(jí)供應(yīng)鏈為例將兩種算法分別計(jì)算20 次后求解完成時(shí)間變化曲線。

為了挖掘算法應(yīng)用價(jià)值，以4級(jí)供應(yīng)鏈系統(tǒng)為例將具體每個(gè)訂單的完成情況以及整個(gè)供應(yīng)鏈具體各級(jí)企業(yè)的產(chǎn)能利用情況繪制成圖進(jìn)一步分析研究，具體如圖3、圖4所示。

通過(guò)上述對(duì)比實(shí)驗(yàn)，可以得出以下幾點(diǎn)結(jié)論：

（1）通過(guò)表2 所示的數(shù)據(jù)可以得出，本文設(shè)計(jì)的約束滿足算法以及為了進(jìn)一步提高算法尋求能力而提出的基于鄰域搜索的約束滿足算法在處理4、5、6、7四個(gè)等級(jí)的供應(yīng)鏈問(wèn)題規(guī)模時(shí)均能求解出比較滿意的最優(yōu)解，證明所設(shè)計(jì)的算法具有良好的有效性和實(shí)用性，并且可以應(yīng)對(duì)諸如7級(jí)供應(yīng)鏈系統(tǒng)這樣等級(jí)層次高，數(shù)據(jù)規(guī)模大且數(shù)據(jù)間邏輯關(guān)系復(fù)雜的情況。

（2）通過(guò)表2中兩種算法的對(duì)比實(shí)驗(yàn)數(shù)據(jù)可以得出，在傳統(tǒng)的約束滿足算法中嵌入鄰域搜索技術(shù)，增強(qiáng)算法跳出局部最優(yōu)的能力，從而對(duì)算法的整體尋優(yōu)能力的提高有著重要作用?；卩徲蛩阉鞯募s束滿足算法求解出的利潤(rùn)率和合同飽和度基本上均大于用傳統(tǒng)約束滿足算法計(jì)算出的結(jié)果，且提升效果較為顯著，證明鄰域搜索技術(shù)可以有效的和約束滿足技術(shù)進(jìn)行結(jié)合，互補(bǔ)兩種技術(shù)的不足并提升整體尋優(yōu)能力。

圖2 CSA與NS-CAS求解時(shí)間變化曲線

圖3 各訂單滿足情況

圖4 各企業(yè)產(chǎn)能利用情況

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

（1）在問(wèn)題模型方面，本文根據(jù)所提出的供應(yīng)鏈問(wèn)題的特點(diǎn)，提出了一個(gè)優(yōu)先級(jí)的概念，并借此來(lái)表示多個(gè)企業(yè)之間關(guān)于運(yùn)輸成本、生產(chǎn)成本、庫(kù)存能力等多方面的差異性，最終建立了一種帶有多級(jí)制造環(huán)節(jié)的供應(yīng)鏈問(wèn)題模型。

（2）在求解算法方面，本文通過(guò)結(jié)合約束滿足算法能較為快速的求出滿意解的特點(diǎn)以及鄰域搜索技術(shù)能夠幫助算法跳出局部最優(yōu)解的特性設(shè)計(jì)了一種基于鄰域搜索的約束滿足算法。該算法以約束滿足算法為主體，并在其中嵌入鄰域搜索技術(shù)從而提高了算法的整體尋優(yōu)能力。

（3）在算法驗(yàn)證方面，利用C#語(yǔ)言實(shí)現(xiàn)了算法并設(shè)計(jì)了數(shù)據(jù)實(shí)驗(yàn)來(lái)驗(yàn)證算法的可行性和有效性。通過(guò)對(duì)比實(shí)驗(yàn)說(shuō)明了基于鄰域搜索的約束滿足算法可以有效的解決帶有多級(jí)制造環(huán)節(jié)的供應(yīng)鏈問(wèn)題，并比傳統(tǒng)約束滿足算法具有更好的全局尋優(yōu)能力。

[1]夏文祥,王宗喜.淺析軍隊(duì)運(yùn)用地方物流的基本方略[J].物流技術(shù)與應(yīng)用,2003,(9):88-92.

[2]郭永輝.基于瓶頸思想的供應(yīng)鏈多階多廠產(chǎn)能規(guī)劃[J].工業(yè)工程,2010,(4):62-66.

[3]齊二石,李輝,劉亮.基于遺傳算法的虛擬企業(yè)協(xié)同資源優(yōu)化問(wèn)題研究[J].中國(guó)管理科學(xué),2011,19(1):77-83.

[4]孫榮庭,孫林巖,李剛.不確定需求下多零售商競(jìng)爭(zhēng)的供應(yīng)鏈協(xié)調(diào)研究[J].工業(yè)工程與管理,2010,2(1):49-58.

[5]蔡建湖,黃衛(wèi)來(lái),周根貴.多零售商競(jìng)爭(zhēng)環(huán)境下季節(jié)性商品訂購(gòu)策略研究[J].管理學(xué)報(bào),2010,7(7):1 070-1 074.

[6]桂云苗,龔本剛,程幼明.不確定條件下供應(yīng)鏈網(wǎng)絡(luò)魯棒優(yōu)化與算法[J].統(tǒng)計(jì)與決策,2011,(8):172-174.

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