轉(zhuǎn)包商選擇與單機(jī)批調(diào)度聯(lián)合優(yōu)化①

唐文娜, 劉 樂(lè)

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

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

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

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

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

1.1 問(wèn)題描述

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

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

1.2 假設(shè)條件

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

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

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

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

(5) 批處理機(jī)同一時(shí)刻僅能處理一個(gè)批次, 僅當(dāng)一

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

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

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

1.3 符號(hào)定義

表1列出了SBSP_SO問(wèn)題中若干符號(hào)表示及其說(shuō)明.

表1 符號(hào)表示及其說(shuō)明

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

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

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

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

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

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

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

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

2 改進(jìn)型遺傳算法和貪婪算法

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

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

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

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

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

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

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

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

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

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

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

(3) 機(jī)器容量約束Q.

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

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

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

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

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

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

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

2.3 交叉算子

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

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

圖2 均勻交叉算子示意圖

2.4 變異算子

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

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

圖3 均勻變異算子示意圖

2.5 終止條件

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

2.6 算法步驟

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

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

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

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

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

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

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

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

2.7 貪婪算法

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

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

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

將作業(yè)集J中的全部作業(yè)按照對(duì)應(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, 并找出對(duì)該作業(yè)外包成本報(bào)價(jià)最低的轉(zhuǎn)包商Sh.

步驟3. 確定轉(zhuǎn)包商 Sh′對(duì) 作業(yè) Jj′ 的 交付時(shí)間lj′h′.如果lj′h′＞ D, 將作業(yè) Jj′歸 入I′中, 從序列τ 中剔除作業(yè) Jj′,置e←e+1, 并返回步驟2. 否則, 確定轉(zhuǎn)包商Sh′對(duì)作業(yè)Jj′的 外包成本報(bào)價(jià)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 實(shí)例分析

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

3.1 實(shí)例介紹

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

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

3.2 改進(jìn)型遺傳算法的性能實(shí)驗(yàn)分析

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

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

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

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

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

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

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

3.3 實(shí)例的靈敏度實(shí)驗(yàn)分析

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

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

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

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

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

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

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

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

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

4 結(jié)論與展望

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

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

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

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

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