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

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

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

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

供應(yīng)鏈內(nèi)企業(yè)間調(diào)度決策的協(xié)調(diào)問題又被稱為供應(yīng)鏈調(diào)度問題[4]。Hall等[18]首次提出了供應(yīng)鏈調(diào)度的概念,并以總調(diào)度成本和分批交付成本最小化為目標,量化了供應(yīng)鏈協(xié)調(diào)決策的效益。Dawande等[4]研究了由一個制造商和一個分銷商組成的二級供應(yīng)鏈的協(xié)調(diào)調(diào)度問題,量化了企業(yè)接受其他企業(yè)最優(yōu)調(diào)度方案的額外成本,并提出了一種基于補償?shù)募顧C制實現(xiàn)供應(yīng)鏈調(diào)度決策的協(xié)調(diào)。蘇生等[19-20]分別研究了單一占優(yōu)的制造商與單一分銷商和多分銷商組成的供應(yīng)鏈的分銷商協(xié)商調(diào)度問題,建立了基于補償?shù)姆咒N商協(xié)商調(diào)度模型,并提出相應(yīng)算法進行了求解。常天田等[21]以裝配供應(yīng)鏈為研究對象,提出了一種基于討價還價理論的供應(yīng)鏈調(diào)度決策協(xié)調(diào)機制。通過對文獻總結(jié)可以發(fā)現(xiàn),在供應(yīng)鏈協(xié)調(diào)調(diào)度決策領(lǐng)域,現(xiàn)有研究多采取補償?shù)姆绞絹泶龠M供應(yīng)鏈企業(yè)間調(diào)度決策的協(xié)調(diào)。然而,在實際供應(yīng)鏈環(huán)境中,企業(yè)地位通常有所差異,因此,針對不同企業(yè)補償條件也應(yīng)有所區(qū)別,如何依據(jù)企業(yè)在供應(yīng)鏈中的地位確定具體的補償條件是本文與現(xiàn)有文獻的區(qū)別所在。

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

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

1 問題描述與假設(shè)

1.1 問題描述

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

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

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

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

1.2 假設(shè)

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

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

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

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

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

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

1.3 符號說明

本文建模參數(shù):

σM,σS——制造商和供應(yīng)商的收益分配比例

λM,λS——制造商和供應(yīng)商的討價還價能力權(quán)重

φM,φS——制造商和供應(yīng)商的風(fēng)險規(guī)避程度系數(shù)

ρS——供應(yīng)商的單位時間拖期懲罰成本

εM——制造商的單位生產(chǎn)準備時間成本

tj——制造商工件的產(chǎn)品類型

dj——供應(yīng)商工件的交付時間

Δt——各工件從供應(yīng)商處運輸?shù)街圃焐烫幩璧臅r間

PCS——供應(yīng)商的拖期懲罰成本

CftM——制造商的沖突成本

PfM,PfS——制造商和供應(yīng)商的收益

PfSC——供應(yīng)鏈整體收益

μ——供應(yīng)商支付的補償值

2 制造型供應(yīng)鏈協(xié)調(diào)調(diào)度模型

本節(jié)研究供應(yīng)鏈中斷發(fā)生后制造型供應(yīng)鏈協(xié)調(diào)調(diào)度模型,模型主要包含重調(diào)度模型和協(xié)商補償模型兩部分。

2.1 重調(diào)度模型

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

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

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

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

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

2.2 協(xié)商補償模型

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

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

通過重調(diào)度供應(yīng)鏈整體收益為f,應(yīng)支付的補償值計算公式為

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

3 算法設(shè)計

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

3.1 編碼與種群初始化

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

采用供應(yīng)鏈整體收益作為個體評價的適應(yīng)值,適應(yīng)值函數(shù)即為2.1節(jié)所構(gòu)建的重調(diào)度目標函數(shù)。在種群初始化階段,為提高初始種群質(zhì)量,只有個體為非劣可行解即供應(yīng)鏈整體收益為正時,個體方可被放入初始種群,否則個體需重新生成。

3.2 選擇操作

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

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

3.3 自適應(yīng)交叉算子

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

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

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

3.4 自適應(yīng)變異算子

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

3.5 自適應(yīng)鄰域搜索策略

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

圖2 鄰域搜索結(jié)構(gòu)示意圖

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

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

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

在第2階段,采用增量學(xué)習(xí)的方式對4種鄰域搜索結(jié)構(gòu)的概率模型進行更新,即

3.6 HAGA算法流程框架

求解中斷情境下的供應(yīng)鏈協(xié)調(diào)調(diào)度模型的HAGA 算法流程如圖3所示。

圖3 HAGA 算法框架圖

4 仿真實驗

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

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

4.1 模型性能分析

為驗證所提出的供應(yīng)鏈協(xié)調(diào)調(diào)度模型的性能,對比了供應(yīng)商繼續(xù)執(zhí)行初始調(diào)度方案的拖期懲罰成本和執(zhí)行通過本文模型求解出的新調(diào)度方案的成本,結(jié)果如表1所示,其中供應(yīng)商成本降低比例計算公式為

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

表1 供應(yīng)鏈協(xié)商調(diào)度計算結(jié)果

4.2 算法性能分析

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

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

圖4 最大值指標對比結(jié)果

圖5 平均值指標對比結(jié)果

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

圖6 3種算法收斂性對比

5 結(jié)語

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

決策主體的行為因素也可能會影響供應(yīng)鏈協(xié)調(diào)調(diào)度的結(jié)果,未來將研究前景理論對模型的影響?？紤]更為復(fù)雜的供應(yīng)鏈協(xié)調(diào)調(diào)度問題,如多級供應(yīng)鏈。