考慮中斷的制造型供應鏈協調調度模型

薄洪光,白思航,韓 鵬,盧治兵

(1.大連理工大學 運營與物流管理研究所,遼寧 大連 116023;2.北京遙感設備研究所,北京 100854)

自然災害、機器故障、物料斷供等突發事件導致的供應鏈中斷會對供應鏈造成嚴重的損失,幾小時甚至幾分鐘的中斷,便會給企業造成數百萬美元的經濟損失[1-2]。研究表明,供應鏈管理者40%～60%的工作時間都花費在處理供應鏈的中斷問題上。中斷發生后,企業往往會重調度生產方案以減少損失[3]。然而,在供應鏈環境中,單一企業的生產調度方案會對其余企業的調度方案產生影響,企業需調整對自己最理想的調度方案,來配合完成其他企業的重調度方案,這可能會造成自身包括生產準備成本等在內的生產成本的增加,Dawande等[4]將這部分增量成本定義為沖突成本。由于沖突成本的存在,企業不會無償放棄對自己有利的調度方案,這導致供應鏈調度決策求解問題復雜度的提高。因此,研究中斷情境下的供應鏈協調調度問題具有重要的理論意義和應用價值。

基于上述分析可知,中斷情境下的供應鏈協調調度問題可以分為企業重調度問題和企業間調度決策的協調問題兩個子問題。在企業重調度問題方面,國內外學者已經取得了一定的研究成果。Peng等[5]同時考慮了機器故障等3種干擾事件情境下的混合流水車間重調度問題,建立了以最小化完工時間和系統不穩定性為目標的數學模型,并提出了一種MSVND 算法。Liu[6]針對新工件到達的情境,以完工時間和外包成本最小化為目標建立了數學模型,并設計了混合變鄰域搜索算法進行求解。Gao等[7]在新工件插入情境下建立了雙目標數學模型,其中一個目標為最小化不穩定性,另一個為完工時間、總流動時間、機器負載和總機器負載4個指標中的一個,并提出一種改進的Jaya 算法進行求解。Zhang等[8]研究了機器故障、作業取消兩種中斷情境下的重調度問題,提出了一種多目標候鳥優化算法進行求解。薄洪光等[9-11]分別研究了多擾動、雙擾動、工件變更情境下的混合流水線重調度問題,并提出智能優化算法進行求解。然而,上述文獻雖對不同中斷情境下的重調度問題進行了研究,但未考慮工件交貨期約束的情況,在實際生產過程中,企業訂單往往存在著交貨期約束,拖期交付需支付懲罰成本。具有交貨期約束的重調度領域,楊宏安等[12]針對帶有交貨期約束并對提前/拖期零件進行懲罰的作業車間調度問題,設計了一種改進的遺傳算法,降低了調度成本和拖期成本。劉樂[13]針對新工件突然到達情境下的單機重調度問題,以最小化延期時間為目標建立了數學模型,并提出了和聲變鄰域搜索算法進行求解。裴海燕等[14]針對臨時插單干擾情境下的重調度優化問題,提出了考慮交貨拖期/提前懲罰成本、設備維護成本和穩健性偏離成本3個指標的數學模型,基于問題特性設計了一種改進的遺傳算法。上述文獻建立重調度模型時,僅考慮了如何最小化自身損失,然而,在供應鏈環境中,企業自身最優的調度方案與其他企業往往是不協調的,需要其他企業更改加工次序來配合完成[4]。而在多產品類型工件生產情境中,企業從生產某一種類型工件轉向另一種類型工件的生產,會導致生產準備時間的出現,企業的生產準備成本與加工次序相關,無法忽略[14-16]。區別于現有研究在建立重調度模型時僅考慮自身損失最小化,本文還兼顧了重調度方案對供應鏈其余企業成本的影響。

供應鏈內企業間調度決策的協調問題又被稱為供應鏈調度問題[4]。Hall等[18]首次提出了供應鏈調度的概念,并以總調度成本和分批交付成本最小化為目標,量化了供應鏈協調決策的效益。Dawande等[4]研究了由一個制造商和一個分銷商組成的二級供應鏈的協調調度問題,量化了企業接受其他企業最優調度方案的額外成本,并提出了一種基于補償的激勵機制實現供應鏈調度決策的協調。蘇生等[19-20]分別研究了單一占優的制造商與單一分銷商和多分銷商組成的供應鏈的分銷商協商調度問題,建立了基于補償的分銷商協商調度模型,并提出相應算法進行了求解。常天田等[21]以裝配供應鏈為研究對象,提出了一種基于討價還價理論的供應鏈調度決策協調機制。通過對文獻總結可以發現,在供應鏈協調調度決策領域,現有研究多采取補償的方式來促進供應鏈企業間調度決策的協調。然而,在實際供應鏈環境中,企業地位通常有所差異,因此,針對不同企業補償條件也應有所區別,如何依據企業在供應鏈中的地位確定具體的補償條件是本文與現有文獻的區別所在。

通過對上述文獻分析可以看出,現有研究在重調度方面多是僅考慮單一企業的損失最小化,而在供應鏈環境中,企業重調度方案往往會對供應鏈其余企業的成本產生影響。如何在重調度過程中兼顧中斷企業與供應鏈其余企業的成本,實現供應鏈整體損失最小化,有待進一步研究;而針對企業間調度決策的協調問題,現有研究多數未考慮企業間地位差異對補償條件的影響,在現實供應鏈中,企業間地位往往是不對等的。基于此,本文研究了供應商受擾中斷情境下,具有交付時間約束的多產品類型制造供應鏈的協調調度問題,其中供應鏈為單一制造商和單一供應商組成的兩階段制造供應鏈,制造商與供應商存在地位差異。制造商接到包含多產品類型的工件加工訂單,每個工件均需先經供應商處理為原材料工件后,立即運送至制造商處加工,每個工件均有一個獨立的交付期[22],中斷發生后,供應商需重調度生產方案以減少損失。

本文區別于以往研究僅考慮單個企業損失最小化,在最小化供應商損失的同時,將供應商重調度方案對制造商的影響納入供應商重調度模型,建立了兼顧供應商拖期成本和制造商沖突成本兩個目標的重調度模型;將企業重調度后減少的損失定義為其收益。基于收益共享契約協調機制,建立了考慮企業在供應鏈中地位的協商補償模型,其中收益分配比例取決于企業地位。采用企業議價能力和風險規避程度來描述企業地位[23],提出了一個融合自適應鄰域算法的混合自適應遺傳算法(Hybrid Adaptive Genetic Algorithm,HAGA),設計仿真算例,驗證了所提模型和算法的有效性。

1 問題描述與假設

1.1 問題描述

制造商在一個時間周期內接收包含m種類型產品工件加工訂單JM={1,2,…,n},工件數量為n。每個工件均需供應商生產供應相應的同類型但規格尺寸存在差異的原材料工件,即供應商有n個原材料工件加工訂單JS={1,2,…,n},各原材料工件交貨期為dj(j=1,2,…,n),交付給制造商后,經制造商加工成完成品。其中,供應商由于各規格尺寸原材料工件的生產工藝十分相近,故不同工件之間的生產準備時間可忽略;而制造商不同產品類型工件間的生產工藝存在較大差異,工件的生產準備時間不可忽略。該情境在實際生產環境中較為常見,例如:某特殊鋼公司根據訂單要求向其下游軸承制造商供應不同牌號(標準)、規格的軸承鋼熱軋棒材,同一軋制輥期內不同規格尺寸的棒材之間可快速切換,即所需的生產準備時間忽略不計;而其下游軸承制造商接收熱軋棒材坯料進行后續加工、裝配作業,生產出不同規格型號的軸承產品,在該過程中,不同規格、不同精度要求的軸承產品在生產工藝工裝、開工技術條件等方面存在較大差異,這導致不同規格軸承產品生產切換時需要考慮生產準備時間。

具體而言,n個工件必須先經供應商在機器MS上加工為原材料工件,然后經制造商在機器MM上處理后完工,兩臺機器均在0時刻可用,可處理各種工件,但一次最多只能處理一個工件。制造商工件和供應商工件的處理時間分別為(j=1,2,…,n)。為制造商和供應商各工件的開始加工時間。制造商在加工過程中,從一種產品類型工件的加工轉向另一種產品類型工件的加工,需要對生產設備、員工等進行調整,從而導致生產準備成本的產生。本文中忽略相同產品類型工件加工處理之間的生產準備成本,從產品類型ti的生產轉向tj的生產所需的生產準備時間為

本文假設供應商總是緊鄰制造商的,并且有足夠多的車輛可用,為減少庫存成本和工件延期,每一個工件在供應商處被處理后均會被立即運輸至制造商[22]。制造商接收到原材料工件后,方可開始對應工件的加工處理。假定所有工件均在零時刻釋放。

由于供應商受到自然災害、物料斷供、機器故障等干擾事件的影響而發生中斷后,在某時間窗[t1,t2]內,無法進行生產加工,導致供應商無法按時交付工件,依照合同,需向制造商支付一定數額的拖期懲罰成本,單位時間拖期懲罰成本為ρS。為減少損失,供應商將重新制定加工方案,本文將重調度后減少的拖期懲罰成本定義為供應商的收益PfS。重調度方案的執行,需要制造商變更自身方案來配合完成,制造商生產方案的變更可能會導致其生產準備成本的增加,本文將增量生產準備成本定義為沖突成本CftM。考慮到決策主體的有限理性,制造商不可能無償配合供應商,供應商需提供不小于制造商沖突成本的補償μ激勵制造商配合完成重調度方案。將供應商重調度后的收益減去制造商的沖突成本定義為供應鏈整體收益PfSC。為確定合適的補償條件,實現供應鏈調度的協同,借鑒收益共享契約的概念,在補償制造商沖突成本之余,以收益分配的形式給予制造商一定的額外補償,激勵制造商配合執行重調度方案,收益分配比例σM和σS取決于雙方在供應鏈中的地位。

1.2 假設

(1)制造商和供應商在同一時間均最多只能加工處理一個工件。

(2)若供應商的某個工件在處理時被中斷,該工件需重新開始加工處理。

(3)制造商和供應商共享各工件的處理時間、開始時間、單位拖期成本以及單位沖突成本等信息。

(4)供應商加工的原材料工件均為同種產品類型但規格尺寸存在差異。

(5)制造商和供應商相同產品類型工件加工處理之間的生產準備時間可忽略。

(6)供應商中斷信息于所有工件被加工之前被知曉,且已有最優初始調度方案[24]。

1.3 符號說明

本文建模參數:

σM,σS——制造商和供應商的收益分配比例

λM,λS——制造商和供應商的討價還價能力權重

φM,φS——制造商和供應商的風險規避程度系數

ρS——供應商的單位時間拖期懲罰成本

εM——制造商的單位生產準備時間成本

tj——制造商工件的產品類型

dj——供應商工件的交付時間

Δt——各工件從供應商處運輸到制造商處所需的時間

PCS——供應商的拖期懲罰成本

CftM——制造商的沖突成本

PfM,PfS——制造商和供應商的收益

PfSC——供應鏈整體收益

μ——供應商支付的補償值

2 制造型供應鏈協調調度模型

本節研究供應鏈中斷發生后制造型供應鏈協調調度模型,模型主要包含重調度模型和協商補償模型兩部分。

2.1 重調度模型

(1)最小化供應商拖期成本。為了減少拖期懲罰成本,供應商以最小化拖期成本為目標,重調度加工方案。例如,供應商在一時間周期內有4個加工工件要處理,初始調度方案中各工件加工任務處理順序為,各工件的處理時間分別為3 h、2 h、1 h和5 h。干擾時間窗為[4,5],即供應商在4～5 h時間段內無法進行生產加工活動,如果供應商執行原方案,總拖期時間為6 h,若重調度方案為,則總拖期時間為5 h,拖期懲罰成本降低。供應商重調度目標之一為重調度收益最大化(拖期成本最小化),即

式中:max(0,dj-)為供應商工件的拖期時間;max(0)為中斷發生后,供應商繼續執行初始調度方案的拖期時間,其中為制造商與供應商相互約定的交貨期為中斷發生后仍執行初始調度方案時供應商工件的交貨時間。式(3)、(4)表示供應商各工件交貨時間的計算方式,其中,表示若無中斷發生的情況下,供應商工件的完工時間表示供應商工件執行初始調度方案的完工時間,為拖期成本,原方案由于不改變制造商的加工順序,不會造成其生產準備成本的變化,因此,供應商繼續執行原方案的懲罰成本中不包括制造商的生產準備成本,僅包含由于供應商拖期交貨給制造商造成的延期完工的損失。

(2)最小化制造商沖突成本。重調度方案的實施,需要給予制造商一定補償來激勵其配合完成。為方便模型處理,本文將補償值分為沖突成本和額外收益兩部分。其中,沖突成本目的在于彌補制造商因配合執行重調度方案而增加的成本,額外收益目的在于激勵制造商配合重調度方案的執行,依據制造商在供應鏈中的地位,將重調度后供應鏈整體收益PfSC中的一定比例以收益共享的方式分享給制造商,供應商的實際收益為供應鏈整體收益的剩余部分。因此,在重調度中,若沖突成本過大,則會導致供應鏈整體收益的減少,造成供應商和制造商雙方收益的降低。因此,供應商在進行重調度時,需兼顧制造商的沖突成本最小化的目標,

因此,為降低懲罰成本,供應商需以最小化總拖期成本和最小化制造商沖突成本為目標進行重調度。為方便模型表述,定義二元決策變量xi,j∈{0,1},xi,j=1表示工件j是第i個被加工處理的工件,prej表示在工件j緊前加工工件。供應商重調度目標函數為:

其中:式(7)為重調度模型的目標函數,亦即供應鏈整體收益;式(8)表示供應商在同一時間只能處理一個工件;式(9)為供應商工件的完工時間計算公式;式(10)表示工件需等其緊前工件完工后方可開始加工;式(11)為制造商各工件生產準備時間計算方式;式(12)為重調度約束條件,即只有重調度后供應鏈收益為正,方可執行重調度方案,否則執行原方案;式(13)指明了決策變量的二元屬性。

2.2 協商補償模型

在供應商獲得其重調度方案后,需與制造商協商,以使其配合完成重調度方案。在協商補償時,補償金額應不小于沖突成本且不大于供應商的重調度收益。本文將供應商支付給制造商的補償分為兩部分:一部分為制造商的沖突成本,另一部分為制造商額外收益。在協商供應鏈額外利益分配的研究中,多數文獻采用收益共享契約的方法,研究表明,收益共享契約可以有效地協調供應鏈企業間的決策。因此,本文借鑒收益共享契約的概念,將供應鏈整體收益的一部分分享給制造商,以激勵其配合完成重調度方案。具體的分配比例取決于雙方在供應鏈中的地位,張云豐等[23]用供應鏈企業在博弈過程中的討價還價能力和相對風險規避程度來描述企業在供應鏈中的地位。參考其做法,本文中制造商和供應商的收益分配比例計算公式分別為:

式中:λM表示制造商的討價還價能力;λS表示供應商的討價還價能力;φM,φS∈(0,1)為制造商和供應商的風險規避程度。

通過重調度供應鏈整體收益為f,應支付的補償值計算公式為

因此,供應商與制造商確定好補償值μ后,獲得的收益為σS·f,制造商因配合供應商重調度方案而獲得的額外收益為σM·f。

3 算法設計

供應鏈調度優化問題的動態性、復雜性和不確定性將大大提升解的搜索空間[25]。任何一種新提出的調度策略都應能高效地探索擴展化的求解空間,并在一定計算時間的約束下,提供一個令供應鏈各方滿意的調度方案。單一算法往往無法兼顧全局搜索能力和局部搜索能力,基于此,本文綜合考慮遺傳算法的全局搜索能力和鄰域搜索算法的局部搜索能力,對兩種算法進行改進并融合,設計了帶有自適應交叉變異算子和自適應鄰域搜索算子的混合自適應遺傳算法來求解模型。

3.1 編碼與種群初始化

在研究調度問題的文獻中,基于順序的工件表示方法被廣泛使用。因此,本文也采用該方式進行編碼,用一個長度為n的工件集排列,表示調度結果。例如,排列πM={2,3,1,4}表示在制造商一方工件被最先加工,其次依次為和。供應商根據制造商提供的各個工件的交付時間,計算形成自身的工件集排序,例如,πS={2,1,3,4}。

采用供應鏈整體收益作為個體評價的適應值,適應值函數即為2.1節所構建的重調度目標函數。在種群初始化階段,為提高初始種群質量,只有個體為非劣可行解即供應鏈整體收益為正時,個體方可被放入初始種群,否則個體需重新生成。

3.2 選擇操作

選擇操作可以使優良的個體得以繼承保留,本文采用輪盤賭選擇方法完成個體選擇。第yth個體被選擇的概率為Py,其計算公式為

式中,fy為第yth個體的適應值。個體適應值越大,被保留的可能性越大。

3.3 自適應交叉算子

為了加快進化速度、增加個體多樣性,一個自適應交叉算子被提出,Pc為執行交叉操作的概率,其計算公式如下式所示。與傳統遺傳算法中交叉算子執行的概率固定不變相區別,所提交叉算子的個體執行交叉操作概率的大小會依據該個體適應值f的大小動態變化,故命名為自適應交叉算子,下文中自適應變異算子的定義與之類似。當執行交叉操作的兩個染色體中更大的適應值f*大于或等于種群的平均適應值favg,自適應交叉概率降低;反之,則保持最大值[26]。即

在執行交叉操作時,采用線性次序交叉方法(見圖1)[27]。采用隨機方式生成兩個隨機位置,交換兩父代個體兩個隨機位置之間的染色體片段,在原父代個體中,刪除從另一個父代個體繼承的基因,然后在交叉位置外按原基因次序,依次填補剩余基因。為保證個體的可行性,若交叉算子得到的個體為非可行解時,則需重新執行交叉操作。

圖1 染色體線性交叉示意圖

3.4 自適應變異算子

變異操作可以維持種群多樣性,避免算法過早收斂。本文采用自適應變異操作,Pm為執行變異操作的概率,其計算公式如下式所示。當變異操作的染色體的適應值f大于或等于種群平均值適應值favg時,自適應變異概率降低;反之,則保持最大值[25]。采用互換變異操作,隨機選擇兩個不同的位置,將其基因值互換。為保證個體的可行性,若變異操作得到的個體為非可行解時,則需重新執行變異操作。即

3.5 自適應鄰域搜索策略

現有研究普遍認為,有效的局部搜索能有效地改進進化算法的性能[28]。而遺傳算法雖然在全局搜索方面性能較好,但在局部搜索方面有所不足。為提升算法求解穩定性,本文提出了一種自適應鄰域搜索策略來改善遺傳算法的局部探索能力,提高算法求解穩定性(見圖2)。主要考慮了4種鄰域結構:insert-based 鄰域搜索、swap-based 鄰域搜索、invert-based鄰域搜索和double swap-based 鄰域搜索。

圖2 鄰域搜索結構示意圖

相較于傳統鄰域搜索采用固定的鄰域搜索順序,本文提出了一種兩階段自適應鄰域搜索策略。第1階段為概率初始化階段,每一個體的鄰域搜索均以隨機方式執行4種鄰域搜索結構,統計4種鄰域搜索的成功次數Ni,基于第1 階段統計結果,初始化4 種鄰域結構被選擇概率;第2 階段,在執行鄰域搜索操作時,依據4 種鄰域搜索結構被選擇的概率進行采樣,隨機選擇一種鄰域結構進行局部搜索,并根據搜索結果更新4種鄰域搜索結構的被選擇概率。

為提高算法求解質量,在進行鄰域搜索時,只有新個體的適應值優于原個體,才會對原個體進行更新,并記錄對應鄰域搜索成功更新的次數Ni。在第1階段結束后,統計4種鄰域搜索成功更新個體次數,初始化各鄰域搜索被選擇概率,即

被選擇概率之所以加上δ是為了避免在第1階段某個鄰域搜索一直未能成功更新個體,而出現被選擇概率為0的情況,令δ=0.05。

在第2階段,采用增量學習的方式對4種鄰域搜索結構的概率模型進行更新,即

3.6 HAGA算法流程框架

求解中斷情境下的供應鏈協調調度模型的HAGA 算法流程如圖3所示。

圖3 HAGA 算法框架圖

4 仿真實驗

本文隨機生成若干算例驗證所提出模型和算法的有效性。算例工件數量分別為10,20,40,60,80,100,制造商產品類型數量為2,3,5,兩者組合成10×2,10×3,10×5等18個算例,每個算例獨立運行10次。取10次運行結果的最大值和平均值以及算法收斂性衡量算法性能。變量設置:制造商和供應商風險規避程度分別為:φM=φS=0.5,供應商和制造商議價能力分別為:λS=0.6,λM=0.4,供應商單位拖期懲罰成本和制造商單位沖突成本分別為[1,3]內的隨機數,供應商和制造商各工件的處理時間以及制造商不同產品類型間的生產準備時間分別為[20,50]內的隨機數,隨機生成供應商受擾中斷時間窗[t1,t2]=[182,267]。

算法用C#語言編寫,運行于Dell筆記本電腦,CPU 為Inter(R)-i5、主頻1.6 GHz、內存4 GB。遺傳算法部分的參數設置與參考文獻保持一致[25],鄰域搜索學習速率為多次求解后選擇的最優參數:種群規模N=50=0.9=0.6=0.1=0.01,α=0.2。

4.1 模型性能分析

為驗證所提出的供應鏈協調調度模型的性能,對比了供應商繼續執行初始調度方案的拖期懲罰成本和執行通過本文模型求解出的新調度方案的成本,結果如表1所示,其中供應商成本降低比例計算公式為

由表1可以發現,通過應用本文提出的協調調度模型,在18 個算例中,供應商的成本均得到一定程度的降低,其中,最大降低比例為43.44%,最小降低比例為18.70%,供應商成本得到顯著降低。制造商通過接受補償的方式,獲得的額外收益均為正,在額外收益的激勵下,制造商也會積極配合供應商完成重調度方案。由此可見,本文提出的供應鏈協調調度模型能夠有效降低供應鏈中斷情境下供應鏈的整體成本,提高供應鏈企業快速響應中斷的能力。

表1 供應鏈協商調度計算結果

4.2 算法性能分析

本文HAGA 算法與基本遺傳算法(Genetic Algorithm,GA)和自適應遺傳算法(Adaptive Genetic Algorithm,AGA)進行對比,算法參數來自相應文獻與HAGA 算法參數設置保持一致[25]。為驗證HAGA 算法的性能,采用改進程度進行對比分析,計算公式為:

圖4、5給出了HAGA 算法在不同規模工件數量下,在最大值和平均值兩個指標上相較于GA 和AGA 算法的改進程度。由圖4可以看出,在最大值指標方面,當工件數量小于20時,HAGA 算法求得的結果并未明顯優于對比算法;而隨著工件數量的增大,改進程度逐漸增大,當工件數量超過40 時,HAGA 算法求得的解的質量明顯優于GA 算法;當工件數量大于60時,明顯優于文獻提出的AGA 算法。由圖5可以看出,當工件數量大于20時,在平均值指標方面,HAGA 算法求得的解的質量明顯優于兩種對比算法。

圖4 最大值指標對比結果

圖5 平均值指標對比結果

圖6給出了3種算法的收斂曲線。由圖6可見,HAGA 算法在求解過程中始終保持優勢,能以較少迭代次數快速收斂至最優解,而AGA 算法則需迭代更多次數才能收斂至最優解,GA 算法改善最優解的能力較弱,易陷入至早收斂狀態。綜上所述,HAGA 算法相較對比算法,在求解本文提出的供應鏈協商調度問題方面具有更好的性能。

圖6 3種算法收斂性對比

5 結語

本文以單一制造商與單一供應商組成的兩階段制造型供應鏈為研究對象,研究了中斷情境下具有交付時間約束的多產品類型制造供應鏈的協調調度問題。其中制造商接到包含多產品類型的工件加工訂單,每個工件均需先經供應商處理為原材料工件后,立即運輸至制造商處加工。區別于現有重調度文獻僅考慮中斷企業自身的成本指標以最小化損失,本文在建立供應商重調度模型時,還兼顧了供應商單方面加工順序的調整對制造商成本的影響,并設計了考慮企業間地位差異的補償機制以激勵制造商配合完成重調度方案。以最小化供應商總拖期交付成本和最小化制造商總沖突成本為目標,建立了基于收益共享契約協調機制的供應鏈協調調度模型,并設計了一種帶有自適應交叉變異算子與自適應鄰域搜索算子的混合自適應遺傳算法用于模型求解,通過算例仿真,驗證了所提出的協調調度模型的作用以及HAGA 算法的有效性。

決策主體的行為因素也可能會影響供應鏈協調調度的結果,未來將研究前景理論對模型的影響。考慮更為復雜的供應鏈協調調度問題,如多級供應鏈。