唐文娜, 劉 樂

(濟南大學(xué) 商學(xué)院, 濟南 250002)

為應(yīng)對全球化競爭加劇、原材料價格上漲以及外部經(jīng)濟環(huán)境的不確定性, 外包(outsourcing)成為眾多制造型企業(yè)不可或缺的運營策略[1]. 但外包策略的執(zhí)行會增加企業(yè)作業(yè)調(diào)度的難度, 決策者一方面需要從現(xiàn)有待加工作業(yè)中確定外包作業(yè), 另一方面還需對內(nèi)部作業(yè)進行有效調(diào)度. 近年來, 帶外包選擇的調(diào)度問題(scheduling problems with outsourcing options, SPOO)引起了調(diào)度學(xué)者的關(guān)注. 現(xiàn)有針對該問題的研究成果中, 絕大多數(shù)都把單個轉(zhuǎn)包商作為作業(yè)外包選擇的對象. 不過, 企業(yè)實際運營中外包選擇的對象往往是多個轉(zhuǎn)包商, 并且隨著企業(yè)經(jīng)營范圍的擴大會吸引越來越多的轉(zhuǎn)包商參與其作業(yè)外包的競爭. 因此, 面向多轉(zhuǎn)包商的作業(yè)外包選擇才是企業(yè)外包運營管理的常態(tài). 比起僅有單一轉(zhuǎn)包商可供選擇的情況, 企業(yè)在面對多個轉(zhuǎn)包商時作業(yè)外包的選項更多, 優(yōu)化決策的難度也更大. 如何得到作業(yè)的轉(zhuǎn)包商選擇與內(nèi)部調(diào)度聯(lián)合決策方案已成為當(dāng)今企業(yè)外包運營管理的一項挑戰(zhàn)性任務(wù).為此, 本文瞄準面向多轉(zhuǎn)包商的可外包作業(yè)調(diào)度問題開展理論與方法研究. 這類問題不僅能為企業(yè)外包選擇決策提供有效的解決方案, 還能幫助企業(yè)有效利用外包市場中的產(chǎn)能資源, 具有實踐指導(dǎo)意義和應(yīng)用價值.

帶外包選擇的調(diào)度問題的研究涌現(xiàn)出了豐碩的研究成果. 這些成果已經(jīng)涉及單機[2]、并行機[3]、流水車間[4]、作業(yè)車間[5]等多種機器環(huán)境. 帶多轉(zhuǎn)包商外包選擇的調(diào)度問題在帶外包選擇的調(diào)度問題的研究中占比較少. Chen等[6]較早關(guān)注到帶多轉(zhuǎn)包商外包選擇的調(diào)度問題, 他們對多轉(zhuǎn)包商參與作業(yè)外包的并行機調(diào)度問題進行了深入研究, 并開發(fā)一種啟發(fā)式算法求解該問題. Mokhtari等[7]也注意到帶多轉(zhuǎn)包商外包選擇的并行機調(diào)度問題, 構(gòu)建了以總成本最小化為目標的數(shù)學(xué)模型, 并為該問題設(shè)計出一種團隊過程算法. Ahmadiza等[8]研究了面向雙轉(zhuǎn)包商的雙機流水車間調(diào)度問題, 構(gòu)建了以完工時間和外包及運輸成本之和最小化為目標的數(shù)學(xué)模型, 并提出一種蟻群算法求解該問題.Goli等[9]研究了帶多轉(zhuǎn)包商外包選擇的流水車間調(diào)度問題, 通過考慮不同機器上加工作業(yè)工時的不確定性,提出了一種魯棒混合整數(shù)線性規(guī)劃模型, 并通過實例驗證了所構(gòu)建模型的魯棒性.

在并行批加工(parallel batch processing)環(huán)境下,批處理機能同時加工多個作業(yè), 同一批作業(yè)中最長的加工時間為此批作業(yè)的加工時間[10]. 該環(huán)境能幫助企業(yè)提高機器利用率、降低能耗, 很多產(chǎn)品加工過程中的瓶頸工序都是在該環(huán)境加工完成[11]. 并且在半導(dǎo)體制造、金屬冶煉、陶瓷燒制等行業(yè)中十分常見[12]. 從實際調(diào)研的情況來看, 在采用并行批加工模式的企業(yè)中, 加工時間相對較長的作業(yè)無論分配到哪個加工批次都會延遲同批次其他作業(yè)的完工時間并影響企業(yè)的整體交付服務(wù)水平. 在該情形下, 企業(yè)可考慮把這類作業(yè)分配給合適的轉(zhuǎn)包商進行委外加工. 這樣做既可以提高企業(yè)內(nèi)部產(chǎn)能的利用效率, 又有助于縮短企業(yè)的完工期, 提升其交付服務(wù)水平. 可見, 并行批加工環(huán)境對外包策略的有效運用有著迫切的需求. 基于此, 本文針對并行批加工環(huán)境下帶轉(zhuǎn)包商選擇的單機批調(diào)度問題(single-machine batch scheduling problem with subcontractor options, SBSP_SO)開展研究, 結(jié)合批處理機容量約束以及外包環(huán)節(jié)中的外包成本預(yù)算約束、外包作業(yè)最晚交付期約束構(gòu)建了整數(shù)規(guī)劃模型, 并設(shè)計改進型遺傳算法和貪婪算法求解該模型. 最后, 通過對實例進行靈敏度實驗分析, 為企業(yè)外包運營管理提供相關(guān)建議.

1 問題描述及數(shù)學(xué)模型

1.1 問題描述

待加工作業(yè)集合J中有n個作業(yè)亟待制造商實施聯(lián)合調(diào)度, 這些作業(yè)均在0時刻可用. 現(xiàn)有兩種生產(chǎn)資源可供選擇, 可在其內(nèi)部單臺批處理機上加工或是外包給轉(zhuǎn)包商. 現(xiàn)有外包市場上可供制造商選擇的轉(zhuǎn)包商有H個. 如果作業(yè)Jj外包給轉(zhuǎn)包商Sh, 制造商則須向轉(zhuǎn)包商Sh支付ojh單位的外包成本, 轉(zhuǎn)包商Sh完成對作業(yè)Jj的加工后會在ljh時刻交付給制造商. 制造商需要確定外包給轉(zhuǎn)包商Sh的外包作業(yè)集和內(nèi)部作業(yè)集I在內(nèi)部批處理機上的調(diào)度方案B.容量約束的前提下, 得到最佳聯(lián)合方案B*]. 其中,表示π*中外包給轉(zhuǎn)包商Sh的外包作業(yè)

本文所考慮的SBSP_SO問題可描述如下. 在滿足外包成本預(yù)算約束、外包作業(yè)最晚交付期約束、機器集, 以使得作業(yè)外包總成本OC與內(nèi)部批加工總成本IBC之和(以下簡稱作業(yè)運營總成本)達到最小. 根據(jù)Graham等[13]提出的調(diào)度問題三參數(shù)法和Qi[14]提出的外包與調(diào)度聯(lián)合優(yōu)化問題簡記法, 本文所考慮的SBSP_SO問題可表示為 1+H | batch, sj≤Q, Budget |OC+IBC.

1.2 假設(shè)條件

(1) 每個作業(yè)的尺寸大小、內(nèi)部加工時間均已知.

(2) 每個作業(yè)的尺寸都不超過批處理機的容量.

(3) 所有作業(yè)均在0時刻可用.

(4) 內(nèi)部的批處理機采用并行批加工模式.

(5) 批處理機同一時刻僅能處理一個批次, 僅當(dāng)一

個批次中所有作業(yè)都完工時才釋放機器.

(6) 內(nèi)部加工批次總數(shù)僅當(dāng)所有批次都構(gòu)建完成后才能確定.

(7) 轉(zhuǎn)包商根據(jù)自身產(chǎn)能和市場條件主動將外包成本報價和交付時間信息提供給制造商.

1.3 符號定義

表1列出了SBSP_SO問題中若干符號表示及其說明.

表1 符號表示及其說明

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

根據(jù)以上描述, 本文考慮的SBSP_SO問題的數(shù)學(xué)模型如下.

其中, 式(1)為SBSP_SO問題的目標函數(shù); 式(2)排除了一個作業(yè)參與外包的同時又在制造商內(nèi)部分批加工的可能性, 并保證當(dāng)一個作業(yè)在制造商內(nèi)部加工時只能安排到一個加工批次中, 當(dāng)它參與外包生產(chǎn)時則僅能委托給一個轉(zhuǎn)包商加工; 式(3)確保每個內(nèi)部作業(yè)所在的加工批次一定不是空作業(yè)集; 式(4)保證每個內(nèi)部加工批次中作業(yè)的尺寸之和不超過批處理機的容量 Q ;式(5)表示作業(yè)外包總成本不能超過給定外包成本預(yù)算Budget; 式(6)表示各轉(zhuǎn)包商對其加工的每個外包作業(yè)的交付時間不得超過事先預(yù)定的外包作業(yè)最晚交付期D ; 式(7)指明了決策變量xjk、yk和vjh的二元屬性.

SBSP_SO問題的計算復(fù)雜性可通過一類特殊情形A1獲知. 其中, 各轉(zhuǎn)包商Sh(h=1, 2, …, H)對每個作業(yè)Jj∈J的外包成本報價ojh均相等且遠遠大于由于作業(yè)的外包成本足夠高, 導(dǎo)致無任何作業(yè)參與外包, 于是此時SBSP_SO問題退化為差異尺寸作業(yè)在單臺批處理機上的調(diào)度問題, 即1 | batch, sj≤Q|Cmax(Cmax表示最大完工時間). 該問題已被證明是強NP-hard問題[15], SBSP_SO問題的計算復(fù)雜度不會低于該問題, 故SBSP_SO問題是強NP-hard問題.

SBSP_SO問題的求解過程包含兩個決策環(huán)節(jié): 一是確定出外包給各個轉(zhuǎn)包商的作業(yè)集合, 即作業(yè)外包決策; 二是對制造商內(nèi)部批處理機上加工的作業(yè)進行分批調(diào)度, 即內(nèi)部批調(diào)度決策. 作業(yè)外包決策是SBSP_SO問題的首要環(huán)節(jié), 包含外包與否和轉(zhuǎn)包商選擇兩個任務(wù). 事實上, 可根據(jù)下列性質(zhì)直接判斷符合特定條件的作業(yè)是否參與內(nèi)部分批調(diào)度.

性質(zhì)1. 如果作業(yè)Jj滿足不等關(guān)系 ojh＞λ·pj(h∈{1, 2, …, H}), 則它在最優(yōu)聯(lián)合方案中不會分配給轉(zhuǎn)包商Sh完成加工, 即

性質(zhì)2. 如果作業(yè)Jj滿足不等關(guān)系1,2,···,H}＞D, 則它在最優(yōu)聯(lián)合方案中參與內(nèi)部分批調(diào)度, 即Jj∈B*.

以上性質(zhì)均可通過反證法證明, 鑒于篇幅, 證明過程不在此詳述.

2 改進型遺傳算法和貪婪算法

本節(jié)為具備強NP-hard特性的SBSP_SO問題分別設(shè)計了改進型遺傳算法(improved genetic algorithm,IGA)和貪婪算法(greedy method, GM). 本節(jié)先對IGA算法中染色體編碼與初始種群生成、適應(yīng)度函數(shù)與選擇機制、交叉算子、變異算子和迭代終止條件這5個重要組成部分進行逐一詳述, 然后給出IGA算法的總體流程. 最后對GM算法的設(shè)計思路和執(zhí)行步驟進行表述.

2.1 染色體編碼與初始種群生成

根據(jù)SBSP_SO問題的描述, 聯(lián)合方案π 須給出外包給轉(zhuǎn)包商Sh的作業(yè)集和內(nèi)部批處理機上的調(diào)度方案. 任意一個作業(yè)Jj∈J, 首先要決定其是否外包, 若是外包, 則須為其尋找合適的轉(zhuǎn)包商; 若是在內(nèi)部批處理機上完成加工, 則須確定其所屬的內(nèi)部加工批次. 因此,在IGA算法中, 對染色體編碼時需要兼顧單個作業(yè)可選擇的外包對象與內(nèi)部加工批次. 其中, 每條染色體表示一個可行聯(lián)合方案π, 為每個作業(yè)設(shè)置兩個基因位,分別用g1和g2表示. g1表示作業(yè)可選擇的外包對象,g1可能取值為{0, 1, 2, …, H}, g1=0表示作業(yè)在內(nèi)部單臺批處理機上加工, g1=h則表示外包給轉(zhuǎn)包商Sh加工;g2表示作業(yè)的內(nèi)部加工批次, 考慮到一批作業(yè)的尺寸大小均接近Q的極端情況, g2可能的取值為{0, 1, 2, …,n}, 每條染色體的長度為2n. 任意一個作業(yè)要么參與外包, 要么在制造商內(nèi)部加工, 故它的兩個基因位不能同時取0且規(guī)定當(dāng)g1不等于0時g2一定等于0.

以一個包含8個作業(yè)、3個轉(zhuǎn)包商的問題為示例,各作業(yè)的信息(即內(nèi)部加工時間pj、尺寸大小sj)和轉(zhuǎn)包商的信息(即外包成本報價ojh、交付時間ljh)如表2所示. 此外, 示例中統(tǒng)一取Q=10, Budget=7, D=15.圖1為該示例的一個可行聯(lián)合方案的染色體表示結(jié)構(gòu)圖. 其中, J4外包給轉(zhuǎn)包商S2, OC=5

表2 示例中作業(yè)與轉(zhuǎn)包商的信息

圖1 染色體表示結(jié)構(gòu)示意圖

IGA算法中的每一代種群由popSize條染色體組成, 每條染色體包含2n個基因位. 初始種群中的每條染色體均在每個基因位的有效范圍內(nèi)隨機生成. 為進一步提高染色體的質(zhì)量, 在染色體的生成時充分結(jié)合性質(zhì)1和性質(zhì)2, 將滿足性質(zhì)1、性質(zhì)2中不等式條件的作業(yè)從外包作業(yè)集中排除.

2.2 適應(yīng)度函數(shù)與選擇機制

對于編碼后的染色體, 在計算其適應(yīng)度值之前需要判斷它的合法性. 染色體合法性的判斷需考慮以下4個方面:

(1) 外包成本預(yù)算約束Budget.

(2) 外包作業(yè)最晚交付期約束D.

(3) 機器容量約束Q.

(4) 每個作業(yè)的兩個基因位不能同時為0且至少有一個為0.z(π). 染色體的適應(yīng)度值按式(8)計算:

文中規(guī)定不滿足上述約束或條件的染色體為非法染色體, 記其適應(yīng)度值為0; 反之, 將合法染色體轉(zhuǎn)化為聯(lián)合方案3, 并按式(1)計算聯(lián)合方案3的目標函數(shù)值

本文采用結(jié)合精英保留策略的錦標賽選擇機制.該機制既保留了錦標賽選擇簡單易行、無需對所有適應(yīng)度值進行有序排列的優(yōu)點, 又能防止當(dāng)前種群中的最優(yōu)個體的基因在下一代丟失, 確保遺傳算法隨著迭代次數(shù)的增加一直收斂逐漸靠近最優(yōu)解[16]. IGA算法中選擇操作的具體步驟如下:

步驟 1. 從上一代完成交叉、變異操作的種群Pop(t-1)中選擇適應(yīng)度值最大的elitismCount個染色體直接進入當(dāng)代種群Pop(t).

步驟 2. 從上一代種群Pop(t-1)中隨機選取tournamentSize個染色體進入選擇池tournament.

步驟 3. 將選擇池tournament中的個體按其適應(yīng)度值從小到大排序, 從中選出適應(yīng)度值最大的個體, 置于當(dāng)代種群Pop(t)中.

步驟 4. 步驟2、步驟3重復(fù)執(zhí)行popSize-elitismCount次, 直到形成Pop(t+1).

2.3 交叉算子

在上述染色體的編碼結(jié)構(gòu)中, 因每個作業(yè)對應(yīng)兩個基因位, 在執(zhí)行交叉操作時需要兩個基因位一起操作. 為了保證執(zhí)行交叉操作后能以相對較高的概率獲得合法染色體, 在 IGA算法中借鑒文獻[17]中的均勻交叉方法實施逐代的染色體交叉操作. IGA算法中交叉操作的具體實施步驟如下.

首先, 從本代種群Pop(t)中隨機選擇2個親代染色體, 分別表示為Parent1、Parent2. 然后, 判斷是否滿足交叉實施條件. 若交叉實施條件滿足, 即pc＞random(a)(pc表示交叉率, random(a)∈[0, 1]), 為交叉實施后的后代染色體offspring分配2n個基因位, offspring中每個作業(yè)對應(yīng)的兩個基因位來自于Parent1或者Parent2的概率各有50%. 最后, 染色體offspring取代Parent1進入本代種群Pop(t) 中. 圖2為上述示例的均勻交叉過程的示意圖.

圖2 均勻交叉算子示意圖

2.4 變異算子

為盡量保證執(zhí)行變異操作后的染色體為合法染色體, 在IGA算法中選用均勻變異的方式實施逐代的染色體變異操作, 以一個較小的概率來替換染色體原有的基因?qū)? IGA算法中變異操作的具體實施步驟如下.

首先, 從本代種群Pop(t)中按順序選擇出一個染色體, 記作染色體1, 為保證有新的基因?qū)M入現(xiàn)有種群, 按照初始種群中生成染色體的方式(見第2.1節(jié))隨機生成另一條染色體, 記作染色體2. 對于染色體1中的每個基因?qū)? 若滿足當(dāng)前的變異實施條件, 即pm＞random(b) (pm表示交叉率, random(b)∈[0, 1]), 則將其替換為染色體2中對應(yīng)的基因?qū)? 否則, 基因?qū)Φ闹当３植蛔? 由此得到的染色體作為變異后的染色體進入種群Pop(t). 圖3為上述示例的均勻變異過程的示意圖.

圖3 均勻變異算子示意圖

2.5 終止條件

遺傳算法中可選用的終止條件有最大迭代數(shù)或無改進最大迭代數(shù)終止、選取偏差度終止、評價準則終止等. 本文將無改進最大迭代數(shù)(tmax)作為所設(shè)計IGA算法的迭代終止條件, 令tmax=200n. 具體操作如下.IGA算法的每一次迭代中都記錄并更新迄今最好解,當(dāng)迄今最好解的適應(yīng)度值在連續(xù)的200n次迭代中都未改進時IGA算法終止.

2.6 算法步驟

本文所設(shè)計的IGA算法的具體步驟如下所示.

步驟1. 進行參數(shù)設(shè)置, 包括種群規(guī)模popSize、交叉率pc、變異率pm、精英保留個數(shù)elitismCount、錦標賽規(guī)模tournamentSize, 并設(shè)定迭代終止條件.

步驟2. 初始種群Pop(0)的生成按照第2.1節(jié)中初始種群生成的相關(guān)內(nèi)容執(zhí)行, 設(shè)置變量t, 其初始值設(shè)定為1.

步驟3. 先對種群Pop(t-1)執(zhí)行結(jié)合精英保留策略的錦標賽選擇操作, 具體的步驟按第2.2節(jié)的相關(guān)內(nèi)容執(zhí)行.

步驟4. 然后對選中的染色體進行均勻交叉操作,具體的步驟按照第2.3節(jié)的相關(guān)內(nèi)容執(zhí)行.

步驟5. 最后, 對選中的染色體執(zhí)行均勻變異操作,具體的步驟按照第2.4節(jié)的相關(guān)內(nèi)容執(zhí)行, 生成新的種群Pop(t).

步驟6. t=t+1, 檢驗是否滿足迭代終止條件, 即每一代記錄的迄今最好解的適應(yīng)度值是否在200n代內(nèi)未得到改進; 若不滿足迭代終止條件, 則返回步驟3.

步驟7. 輸出聯(lián)合方案 π的目標函數(shù)值及求解時間、聯(lián)合調(diào)度方案等信息.

2.7 貪婪算法

貪婪算法在求解復(fù)雜組合優(yōu)化問題時, 通常不從整體最優(yōu)解出發(fā), 而總是基于當(dāng)前條件做出最好的選擇. 這種做法往往能在很多組合優(yōu)化問題的求解中獲得全局最優(yōu)解或全局近似最優(yōu)解[18]. 本節(jié)應(yīng)用所設(shè)計的GM算法完成SBSP_SO問題中的外包與否和轉(zhuǎn)包商選擇兩個任務(wù), 從而得到內(nèi)部作業(yè)集I′和面向每個轉(zhuǎn)包商的外包作業(yè)集在外包作業(yè)集確定后,可基于BFLPT (best-fit longest processing time)規(guī)則得出面向內(nèi)部作業(yè)集 I′的 批調(diào)度方案 B′.眾所周知, BFLPT規(guī)則能為差異尺寸作業(yè)批調(diào)度問題快速提供一個近似最優(yōu)批調(diào)度解[19], 文獻[19]中給出了該規(guī)則的具體步驟, 在此不再贅述. 當(dāng)外包作業(yè)集和內(nèi)部作業(yè)集 I′均確定后, 可根據(jù)式(1)計算出批調(diào)度方案π′=的目標函數(shù)值 z (π′).

用于確定SBSP_SO問題中內(nèi)部作業(yè)集I′和外包作業(yè)集的GM算法步驟如下:

步驟1. 對于任意作業(yè)Jj∈J, 按式(1)計算對應(yīng)的比值R :

將作業(yè)集J中的全部作業(yè)按照對應(yīng)的Rj(j=1, 2, …,n)值降序排序, 形成作業(yè)排序方案τ.并且, 執(zhí)行變量初始化操作: e←1、OC←0.

步驟2. 如果e＞n, 那么輸出內(nèi)部作業(yè)集I′和外包作業(yè)集GM算法結(jié)束. 否則, 取出當(dāng)前序列τ 中Rj值最大的作業(yè) Jj, 并找出對該作業(yè)外包成本報價最低的轉(zhuǎn)包商Sh.

步驟3. 確定轉(zhuǎn)包商 Sh′對 作業(yè) Jj′ 的 交付時間lj′h′.如果lj′h′＞ D, 將作業(yè) Jj′歸 入I′中, 從序列τ 中剔除作業(yè) Jj′,置e←e+1, 并返回步驟2. 否則, 確定轉(zhuǎn)包商Sh′對作業(yè)Jj′的 外包成本報價oj′h′.

步驟4. 更新當(dāng)前的OC值: 置OC←OC+oj′h′.如果OC ＞Budget, 將作業(yè) Jj′歸 入I′中, 從序列τ 中剔除作業(yè) Jj′, 置e←e+1, 并返回步驟2. 否則, 將作業(yè) Jj′歸入中, 從序列τ 中剔除作業(yè) Jj′, 置e←e+1, 并返回步驟2.

3 實例分析

下面以某陶瓷制造企業(yè)的作業(yè)外包與批調(diào)度聯(lián)合決策場景為例進行仿真實驗分析, 整個實驗分為兩部分. 在第1部分, 通過對比實驗考察IGA算法的優(yōu)化性能, 以驗證IGA算法對SBSP_SO問題的求解有效性.在第2部分, 旨在運用IGA算法對SBSP_SO問題實例中的可控參數(shù)進行靈敏度實驗分析, 以探尋影響作業(yè)運營總成本的關(guān)鍵可控參數(shù)及其影響效果.

3.1 實例介紹

所選取的實例來自于某陶瓷企業(yè)中進行胚體燒制的批加工生產(chǎn)線. 經(jīng)實地調(diào)研發(fā)現(xiàn): 該生產(chǎn)線采用并行批加工模式, 生產(chǎn)線燒制所使用的電爐的容量Q為25 m3;企業(yè)內(nèi)部單臺批處理機單位時間的批加工成本λ 為1;外包市場上可供陶瓷廠選擇的轉(zhuǎn)包商有4個; 外包成本預(yù)算被稱作外包成本容許率. 所關(guān)注的聯(lián)合調(diào)度決策場景如下所述: 該批加工生產(chǎn)線共有35個待燒制作業(yè); 各作業(yè)的內(nèi)部加工時間pj(以h為單位)、尺寸大小sj(以m3為單位) 已知, 如表3所示; 各轉(zhuǎn)包商對每個作業(yè)的外包成本報價ojh(以RMB為單位)、交付時間ljh(以h為單位)也已知, 如表3所示. 由于該廠自身的產(chǎn)能有限,難以按時完成所有待燒制作業(yè)的加工任務(wù), 不得不考慮將一部分待燒制作業(yè)外包, 以犧牲一定數(shù)額的外包成本, 使作業(yè)運營總成本下降.為保證完工的陶瓷品能按時送達客戶, 該企業(yè)限定各個轉(zhuǎn)包商在60 h內(nèi)完成對委外燒制任務(wù)的交付.

表3 實例中的作業(yè)與轉(zhuǎn)包商信息

3.2 改進型遺傳算法的性能實驗分析

下面選用商業(yè)優(yōu)化軟件 IBM ILOG CPLEX 12.8和GM算法作為比較對象, 考察所設(shè)計IGA算法對SBSP_SO問題的優(yōu)化性能表現(xiàn). 運行環(huán)境如下: 計算機系統(tǒng)為Windows 10, 處理器為Intel?Core?i7-7500@2.70 GHz 2.90 GHz, RAM內(nèi)存為 4.0 GB. 另外, 實驗中用到的各種算法、程序均采用Java語言編程實現(xiàn). 在預(yù)實驗中, 通過對所設(shè)計IGA算法的控制參數(shù)進行校準實驗, 得出各參數(shù)的建議取值如下: popSize=50, pc=0.95, pm=0.01, elitismCount=5, tournamentSize=5.

當(dāng)前性能實驗中的6個測試算例源于第3.1節(jié)所述實例. 算例1中的待燒制作業(yè)數(shù)為30, 這30個作業(yè)的相關(guān)信息如表3中前30個作業(yè)所示; 算例2中的待燒制作業(yè)數(shù)為31, 這31個作業(yè)的相關(guān)信息如表3中前31個作業(yè)所示, 以此類推. 此外, 這6個算例中其他參數(shù)取值統(tǒng)一為: η=0.1, D=48 h , Q=25 m3. 隨著作業(yè)規(guī)模的增大, CPLEX短時間內(nèi)得不到精確解的可能性會提升. 為了便于比較IGA算法、GM算法和CPLEX的求解結(jié)果, 在當(dāng)前實驗中將CPLEX求解時間上限設(shè)置為3 600 s, 將迄今最好解的適應(yīng)度值在連續(xù)200n次迭代中都未改進作為IGA算法的迭代終止條件. IGA算法本質(zhì)上屬于元啟發(fā)式算法, 在IGA算法的性能實驗中需要記錄獨立運行多次的求解結(jié)果(目標函數(shù)值和求解時間). 在本性能實驗中, 為測算IGA算法和GM算法在求解能力上的差距, 特引入一個求解質(zhì)量偏差度量指標Gap, 兩算法的Gap指標值按下式計算:

其中, HA為IGA算法和GM算法的通稱變量, 即HA∈{IGA, GM}. zIGA(π) 是IGA算法獨立運行15次所得目標函數(shù)值的均值, zGM(π)是GM算法所得解的目標函數(shù)值. z*(π)=m in{zIGA(π),zGM(π)}.GapABA的值; Obj2 、Time和 Gap分別表示貪婪算法單獨運行的求解結(jié)果、對應(yīng)目標函數(shù)值的求解時間以及G apGM的值.

表4給出的是改進型遺傳算法、貪婪算法與CPLEX求解測試算例的統(tǒng)計結(jié)果. 其中, Obj1 和State分別表示CPLEX單獨運行的求解結(jié)果、對應(yīng)目標函數(shù)值的時間狀態(tài); Min、Max、AVG、SD、Time和 Gap分別為改進型遺傳算法獨立運行15次的最小值、最大值、均值、標準差、求解時間以及

表4 改進型遺傳算法、貪婪算法與CPLEX的實例求解結(jié)果比較

由于CPLEX是基于數(shù)學(xué)規(guī)劃法求解測試算例, 其耗時會隨作業(yè)數(shù)n的增大而指數(shù)增長. 從表4可以看出, 對于作業(yè)數(shù)n≥31的算例, CPLEX在設(shè)定的3 600 s內(nèi)無法得到精確最優(yōu)解, 只能求得近似最優(yōu)解. 而IGA算法卻能在更短的時間得出更高質(zhì)量的聯(lián)合調(diào)度解,運行時間僅為CPLEX所耗時間的1/500. 在n=30、31、32這3個算例的求解中, IGA算法全部15次實驗中均得到和CPLEX相等的目標函數(shù)值. 在n=33、34、35這3個算例的求解中, 改進型遺傳算法在全部15次實驗中均達到或優(yōu)于CPLEX求解結(jié)果水平. 可見, 與CPLEX相比, IGA算法在測試算例上的優(yōu)化質(zhì)量和時間上的表現(xiàn)更好.

另外, 從IGA算法和GM算法對上述6個算例的求解結(jié)果來看, 雖然IGA算法比GM算法花費的時間多, 但是這些時間并不是徒勞的, 而是有效提升了解的質(zhì)量. IGA算法的Gap值均為0, 而GM算法的Gap值均在15%以上. 這說明IGA算法的優(yōu)化質(zhì)量明顯優(yōu)于GM算法, 進一步體現(xiàn)出IGA算法的收斂能力.

3.3 實例的靈敏度實驗分析

本節(jié)力圖利用靈敏度實驗分析法找出影響企業(yè)作業(yè)運營總成本的關(guān)鍵可控參數(shù), 通過對實例中關(guān)鍵可控參數(shù)的有效調(diào)整, 使企業(yè)所花費的作業(yè)運營總成本進一步降低. 實例中, 轉(zhuǎn)包商提供的外包成本報價ojh和交付時間ljh、作業(yè)數(shù)n等屬于不可控因素. 由于企業(yè)內(nèi)部單臺批處理機單位時間的批加工成本 λ主要受人員工資、機器設(shè)備等影響, 在現(xiàn)實中改變的可能性不大, 也屬于實例中的不可控參數(shù). 實例中的可控參數(shù)主要有外包成本預(yù)算Budget和外包作業(yè)最晚交付期D, 而外包成本預(yù)算Budget的實際值由外包成本容許率η決定. 因此, 針對該實例的靈敏度實驗主要圍繞外包成本容許率η和外包作業(yè)最晚交付期D展開.

下面將使用IGA算法進行實例的靈敏度實驗, 基于上述實例、基于外D和η的不同組合(D, η), 進而得到不同的作業(yè)運營總成本的值, 并將IGA算法獨立運行15次的均值作為實驗分析的數(shù)據(jù). 其中, 作業(yè)運營總成本用TC表示, 外包作業(yè)最晚交付期上限用lmax表示. 考慮到企業(yè)預(yù)算不夠充足更符合現(xiàn)實情況, 在進行靈敏度實驗時, η的范圍取[0.05, 0.5], 單位浮動數(shù)值為0.05. 把lmax作為基準, 將提前50%、25%作為間隔點, 將D劃分為早(0, 30]、中(30, 45]、晚(45, 60]三個階段. 在D范圍的選取上, 考慮到D過早在現(xiàn)實中難以實現(xiàn), 在此選取D∈[20, 60]的范圍進行實驗, 單位浮動數(shù)值為3. 圖4給出的是不同參數(shù)組合(D, η)所對應(yīng)的作業(yè)運營總成本TC.

圖4 不同參數(shù)組合(D, η)下的作業(yè)運營總成本

由圖4可發(fā)現(xiàn)以下4個現(xiàn)象: (1) 外包作業(yè)最晚交付期D對作業(yè)運營總成本TC的影響較為明顯, 而外包成本容許率η對作業(yè)運營總成本TC的影響不明顯;(2) 當(dāng)η＞0.15時, 無論D取何值, TC的值幾乎與η=0.15時TC的值持平. (3) 不建議企業(yè)將D定至早(0,30]或中(30, 45]兩個階段. 究其原因在于外包作業(yè)最晚交付期的硬約束使得幾乎所有作業(yè)在內(nèi)部批處理機上加工, 企業(yè)無法從外包策略中獲益. 四是在外包成本預(yù)算相對充足的情況下, D的取值越接近lmax, TC降低效果越明顯. 當(dāng)D=54, 57, 60 h時, 與早(0, 30]、中(30, 45]兩個階段相比, TC分別降低15.70%、21.07%、23.97%.

為驗證上述第一個現(xiàn)象是否有統(tǒng)計學(xué)意義, 取外包成本容許率η和外包作業(yè)最晚交付期D作為自變量, 作業(yè)運營總成本TC作為因變量, 使用上述靈敏度實驗得出的數(shù)據(jù)進行雙因素方差分析檢驗. 表5給出的是雙因素方差分析的檢驗結(jié)果. 從表5可以看出, 外包成本容許率η和外包作業(yè)最晚交付期D組成的交互項的p值大于0.05, 故沒有統(tǒng)計學(xué)意義. 值得注意的是,外包成本容許率η和外包作業(yè)最晚交付期D的p值分別為0.991、0.000, 可認為外包成本容許率η的不同對TC沒有顯著影響, 而外包作業(yè)最晚交付期D對TC有顯著影響.

表5 雙因素方差分析檢驗結(jié)果

下面針對外包作業(yè)最晚交付期 D 接近lmax的4種情況即D=48, 51, 54, 57 h觀測并分析外包成本容許率η在[0.01, 0.15]范圍內(nèi)對作業(yè)運營總成本TC的影響趨勢, η的單位浮動值取0.01. 首先, 運用所設(shè)計的IGA算法在60種參數(shù)組合(D, η)下分別獨立運行15次. 然后, 統(tǒng)計出每種參數(shù)組合(D, η)所得的15個目標函數(shù)值的均值, 并將其繪于圖5中.

圖5 外包作業(yè)最晚交付期接近上限時外包成本容許率的變化對作業(yè)運營總成本的影響

從圖5可以看出, 當(dāng)η≤0.15時, η對TC的影響明顯, 并且外包作業(yè)最晚交付期D越接近lmax, IGA算法的作業(yè)運營總成本優(yōu)化效果越顯著. 此外, 在外包作業(yè)最晚交付期D的4種不同取值情況下, TC都是隨著η的增大而先快速下降后又保持穩(wěn)定. 在D的4種不同取值情況下, η的適宜取值范圍也有所不同. 當(dāng)D=48, 51, 54 h時, 建議外包成本容許率η的設(shè)定值不應(yīng)低于0.07. 當(dāng)D=57 h, η的取值維持在0.10以上較優(yōu).

4 結(jié)論與展望

本文研究了帶轉(zhuǎn)包商選擇的單機批調(diào)度問題. 通過考慮該問題的特征并結(jié)合相關(guān)優(yōu)化性質(zhì)設(shè)計了改進型遺傳算法和貪婪算法. 從算法性能實驗結(jié)果可知, 貪婪算法的求解質(zhì)量偏差即Gap值均超過15%. 這說明改進型遺傳算法的優(yōu)化質(zhì)量明顯優(yōu)于貪婪算法. 在驗證所設(shè)計改進型遺傳算法有效性的基礎(chǔ)上, 使用改進型遺傳算法對實例中的可控參數(shù)進行靈敏度實驗, 以找出關(guān)鍵可控參數(shù)并對其進行有效調(diào)整, 最大限度降低該企業(yè)的作業(yè)運營總成本, 為企業(yè)日常運營提供決策支持. 實例研究發(fā)現(xiàn):

(1) 相較于外包成本容許率, 外包作業(yè)最晚交付期對作業(yè)運營總成本的影響更顯著, 合理的外包作業(yè)最晚交付期設(shè)置可節(jié)省超過20%的作業(yè)運營總成本.

(2) 制造商不宜將外包作業(yè)最晚交付期設(shè)定太早,否則無法從外包中獲益, 在條件允許的情況下, 應(yīng)讓其設(shè)定值盡量接近外包作業(yè)最晚交付期上限.

(3) 外包成本容許率不宜低于0.1, 制造商可通過融資或銀行貸款等方式增加外包成本預(yù)算, 以確保降本效果顯著.

在下一步的研究中, 力求在外包運營實踐方面為企業(yè)提供更多的管理啟示, 并進一步尋找該問題的應(yīng)用場景, 在其他行業(yè)的相關(guān)實例中驗證所設(shè)計改進型遺傳算法的適用性.