耿建一，劉 樂

(濟(jì)南大學(xué) 商學(xué)院，山東 濟(jì)南 250002)

隨著按單生產(chǎn) (make to order, MTO) 模式的普及，許多制造企業(yè)的庫存維持在接近于零的水平，使生產(chǎn)與配送兩個供應(yīng)鏈環(huán)節(jié)之間銜接愈加緊密。在零成品庫存這一新常態(tài)下，生產(chǎn)與配送的協(xié)同決策是供應(yīng)鏈視角下制造企業(yè)實現(xiàn)降本增效的重要出路[1]。因此，生產(chǎn)-配送聯(lián)合調(diào)度問題 (integrated production and distribution scheduling problem, IPDSP) 成為近年來供應(yīng)鏈管理領(lǐng)域的研究熱點(diǎn)。

IPDSP 研究已涉及多種機(jī)器環(huán)境類型，如單機(jī)[2-3]、平行機(jī)[4]、流水車間[5-6]等，它們都基于傳統(tǒng)生產(chǎn)模式，即一臺機(jī)器上同一時刻僅加工一個作業(yè)或一道工序。在集成電路燒機(jī)測試、陶瓷燒制等場合下作業(yè)的加工并不基于該模式，而是采用并行批加工模式 (parallel batching, p-batch)。p-batch 模式契合許多制造商提高產(chǎn)品吞吐量、充分利用產(chǎn)能的發(fā)展訴求。在p-batch 模式下分配到同一生產(chǎn)批次中的作業(yè)在同一臺批處理機(jī)上一起加工，一個批次的工時由其中用時最長作業(yè)的工時決定[7]。同一批次的作業(yè)具有相同的開工與完工時間，但其尺寸各異，尺寸之和不超過批處理機(jī)容量。p-batch 模式下的IPDSP研究近年來發(fā)展迅速，涌現(xiàn)出一批優(yōu)秀成果，如文獻(xiàn)[8-12]。

IPDSP 研究中配送模式按運(yùn)載能力和發(fā)貨運(yùn)輸方式的不同區(qū)分?？膳汕曹囕v的數(shù)量及其載荷量是衡量運(yùn)載能力的兩大指標(biāo)。在常見的發(fā)貨運(yùn)輸方式中，分批配送 (batch delivery, BD) 方式追求車輛滿載運(yùn)輸以減少派運(yùn)車次，是成品貨運(yùn)中最有效降低成本的策略之一[3]。根據(jù)同一批次送達(dá)客戶數(shù)的不同，BD 方式有直接發(fā)貨、環(huán)程發(fā)貨之分[1,4]。在直接發(fā)貨型BD 方式下每輛車裝載的產(chǎn)品都運(yùn)往同一客戶。文獻(xiàn)[2,4-5,8-9,11]都是在直接發(fā)貨型BD 方式下開展的IPDSP 研究工作。這一BD 方式常見于渠道商 (如零售商、經(jīng)銷商) 作為單一客戶的生產(chǎn)-配送管理系統(tǒng)中。渠道商在制成品流通中發(fā)揮集散作用，不僅成品需求量大，而且對它的配送服務(wù)具有點(diǎn)到點(diǎn)、多車次的特點(diǎn)。

由于大多數(shù)IPDSP 是NP 難的[1]，IPDSP 研究中運(yùn)用的優(yōu)化技術(shù)主要有精確解法[2]、確定型啟發(fā)式算法[9,11]和元啟發(fā)式算法[3-6,8,10,12]三類。由于具有良好搜索效率，元啟發(fā)式算法是IPDSP 研究中運(yùn)用最多的求解技術(shù)。作為元啟發(fā)式算法之一，遺傳算法 (genetic algorithm, GA) 備受IPDSP 研究者青睞。在Noroozi 等[3]、Joo 等[4]、Qin 等[5]的研究中均成功運(yùn)用GA 對IPDSP 模型進(jìn)行高效求解。

外包 (outsourcing) 是當(dāng)代制造企業(yè)快速響應(yīng)市場波動、規(guī)避產(chǎn)能短缺風(fēng)險、提升交付能力的重要策略之一[13]。在p-batch 模式下工時明顯更長的作業(yè)會對同批次其他作業(yè)的完工時間造成延遲影響；若此時合理運(yùn)用外包策略把它們外包出去，則有助于提升產(chǎn)品交付水平和內(nèi)部產(chǎn)能利用率。p-batch 模式下可外包作業(yè)批調(diào)度優(yōu)化已有研究成果問世[14]，但總體來看還處于起步階段。p-batch 模式下作業(yè)外包-生產(chǎn)-配送聯(lián)合調(diào)度較之更復(fù)雜，在研究進(jìn)展上更滯后于現(xiàn)實管理需求。作業(yè)的外包決策給p-batch模式下管理者的作業(yè)生產(chǎn)與配送聯(lián)合調(diào)度工作帶來挑戰(zhàn)，使決策的內(nèi)容涉及作業(yè)外包選擇、內(nèi)部作業(yè)批調(diào)度、成品配送調(diào)度3 個環(huán)節(jié)。它們在實際運(yùn)營中往往分部門、分階段獨(dú)立執(zhí)行，導(dǎo)致了運(yùn)營成本居高不下、周期冗長等痛點(diǎn)問題。為此，本研究聚焦p-batch 模式下基于單機(jī)環(huán)境和直接發(fā)貨型BD 方式的作業(yè)外包-生產(chǎn)-配送聯(lián)合調(diào)度問題 (integrated job outsourcing-production-distribution scheduling problem, IOPDSP)，旨在一體化高效得出作業(yè)外包選擇方案、內(nèi)部批調(diào)度方案和成品分批配送方案，以期為p-batch 模式下制造企業(yè)的作業(yè)外包、生產(chǎn)與配送聯(lián)合調(diào)度管理提供參考建議。

1 問題描述與建模

1.1 符號定義

IOPDSP 的主要參數(shù)符號及其說明見表1。其中，j、k、l分別是對作業(yè)、內(nèi)部加工批次和配送批次的索引編號；在聯(lián)合調(diào)度解π=[Oπ,B,D]中 ，B={Bk;k=1,2,···,b} 由b個 內(nèi)部加工批次組成，D={Dl;l=1,2,···,d} 由d個配送批次組成。TCπ=OCπ+IPCB+DCD；不發(fā)生歧義時TCπ、OCπ、I PCB、D CD分別簡寫 為TC 、O C、IPC、DC 。另 有

表1 IOPDSP 中的參數(shù)符號及其說明Table 1 Notations and their definitions in IOPDSP

1.2 假設(shè)條件與問題描述

IOPDSP 假設(shè)條件如下 。

1) 批處理機(jī)采用p-batch 模式，在同一時刻最多處理一個加工批次，不允許批次之間搶占機(jī)器；

2) 所有作業(yè)都來自同一客戶的訂貨；

3) 每個作業(yè)的尺寸小于批處理機(jī)容量，經(jīng)加工后其尺寸不發(fā)生改變；

4) 外包作業(yè)的加工與配送環(huán)節(jié)包干委托給單一轉(zhuǎn)包商完成；

5) 制造商內(nèi)部批加工總成本與內(nèi)部批加工總時長成正比關(guān)系，有 I PCB=λCmax(B) ；

6) 內(nèi)部加工批次是分批配送的基本單位；

7) 配送車輛充足且最大載荷量統(tǒng)一，每完成一次送達(dá)任務(wù)都消耗相同的配送成本和時間；

8) 由于客戶以制成品最晚送達(dá)時間衡量制造商的交付質(zhì)量，提前完工的內(nèi)部作業(yè)無需立即分批配送給客戶，待全部內(nèi)部作業(yè)都完工后再統(tǒng)一安排制成品配送方案；

9) 內(nèi)部作業(yè)批加工與制成品配送兩環(huán)節(jié)之間所耗庫存成本折算到內(nèi)部作業(yè)的批加工成本中。

IOPDSP 可描述如下。在t=0 時刻作業(yè)集J到達(dá)制造商，待其聯(lián)合調(diào)度。這n個作業(yè)既可在內(nèi)部完成加工并在制成后分批送達(dá)客戶C1，也可外包出去，由轉(zhuǎn)包商S1包干完成加工和配送任務(wù)。對確準(zhǔn)外包的作業(yè)Jj，制造商為其支付外包成本oj。內(nèi)部作業(yè)在單臺批處理機(jī)上制成后，按BD 方式由同質(zhì)車輛從制造商處送至客戶C1處。在作業(yè)外包總成本受預(yù)算限制、機(jī)器容量和車輛載荷強(qiáng)約束條件下，IOPDSP 的目標(biāo)是將各個作業(yè)分配到外包作業(yè)集或不同的內(nèi)部加工批次，再將各內(nèi)部加工批次分配到不同的配送批次(求得π?=[O?π,B?,D?])，使TCπ?=OCπ?+IPCB?+DCD?達(dá)到最小。

1.3 數(shù)學(xué)模型與理論分析

為建立IOPDSP 的整數(shù)規(guī)劃模型，首先引入6 組0-1 決策變量xjk、yk、zj、ujl、vl和wkl(j=1,2,···,n;k=1,2,···,n;l=1,2,···,n)。

IOPDSP 的0-1 規(guī)劃模型如式 (1) ~ (16)所示。

式 (1) 為模型的目標(biāo)函數(shù)，即最小化作業(yè)運(yùn)營總成本；約束 (2) 避免某個作業(yè)既被外包出去，又在內(nèi)部加工的可能性，限定每個內(nèi)部作業(yè)只在一個加工批次中；約束 (3) 排除某個作業(yè)既參與外包生產(chǎn)，又由制造商將其制成品送達(dá)客戶的可能性，并限定每個制成品只在一個配送批次中；約束 (4) 保證每個內(nèi)部作業(yè)都有相應(yīng)的配送批次將其制成品送達(dá)客戶；約束 (5) 排除某個內(nèi)部作業(yè)所在的加工批次未被創(chuàng)建的可能性；約束 (6) 排除一個配送批次所含加工批次未被創(chuàng)建的可能性；約束 (7) 確保某個制成品所在的配送批次已被創(chuàng)建；約束 (8) 確保某個內(nèi)部加工批次的制成品所在的配送批次已被創(chuàng)建；約束 (9) 和 (10) 聯(lián)合保證若作業(yè)Jj在批次Bk中完成加工，其制成品是否安排在配送批次Dl中取決于配送批次Dl中是否包含批次Bk的制成品；約束(11) 保證若無任何作業(yè)被分配到一個內(nèi)部加工批次中，則該加工批次不被創(chuàng)建；約束 (12) 保證若無任何內(nèi)部加工批次的制成品被分配到一個配送批次中，則該配送批次不被創(chuàng)建；約束 (13) 確保每個內(nèi)部加工批次中作業(yè)尺寸之和不超過批處理機(jī)容量；約束 (14) 保證每個配送批次中制成品尺寸之和不超過車輛最大載荷量；約束 (15) 施加作業(yè)外包總成本不超過給定預(yù)算值的硬約束；約束 (16) 指明6 組決策變量的二元屬性。

考慮基于下列假設(shè)的IOPDSP 特例：所有作業(yè)具有相等且足夠高的外包成本值，有o1=o2=···=on＞G(故無作業(yè)參與外包生產(chǎn))；車輛的單車次配送 成 本 μ =0 (故 D C=0 )；所 有 作 業(yè) 的 內(nèi) 部 工 時 相等，即p1=p2=···=pn。在 上 述 假 設(shè) 下IOPDSP的目標(biāo)函數(shù)等價于最小化加工批次數(shù)。若把加工批次視作箱子，此時IOPDSP 退化為一維裝箱 (bin packing) 問題：待裝箱的物品數(shù)為n；箱子容量為Q1； 物品體積為sj，目標(biāo)函數(shù)為最小化箱子 (加工批次) 數(shù)。一維裝箱問題已被證明是NP 難的問題[15]。作為一維裝箱問題的泛化，IOPDSP 的計算復(fù)雜性不低于一維裝箱問題，故IOPDSP 也是NP 難問題。

作業(yè)外包決策環(huán)節(jié)是解決IOPDSP 的首要任務(wù)，可根據(jù)以下性質(zhì)直接判斷符合特定條件的作業(yè)應(yīng)加入或不應(yīng)加入外包作業(yè)集。

性質(zhì)1若作業(yè)Jj滿足oj＞λpj+μ ，則它在π?中不加入。

性質(zhì)2若作業(yè)Jj滿足pj=pmax(J) ；oj＜λ[pmax(J)-pmax(J|{Jj})]，則它在π?中應(yīng)加入。

若將滿足性質(zhì)1 中指定條件的作業(yè)加入外包作業(yè)集，則通過估算、比較由此直接產(chǎn)生的 T C 增加量和減少量，可推斷存在比更優(yōu)的聯(lián)合調(diào)度解。π?定義上的前后矛盾可反證出性質(zhì)1 成立。性質(zhì)2 亦可通過該思路證實。

2 遺傳算法設(shè)計

為求解IOPDSP，本節(jié)設(shè)計出改進(jìn)型遺傳算法(improved genetic algorithm, IGA)。IGA 的改進(jìn)之處體現(xiàn)在兩方面。一是在染色體編碼上，考慮到IOPDSP 中的3 個決策環(huán)節(jié)和π的三元組結(jié)構(gòu)，對每個作業(yè)連續(xù)分配3 個基因位，分別對應(yīng)作業(yè)外包狀態(tài)、所在加工批次及其制成品的配送批次。二是將帶精英保留的錦標(biāo)賽選擇、均勻交叉、均勻變異3 個進(jìn)化機(jī)制組合應(yīng)用于IOPDSP 的GA 求解中。上述三機(jī)制的單獨(dú)應(yīng)用效果已獲認(rèn)可，但它們的組合應(yīng)用效果有待在IOPDSP 的求解中考察驗證。

2.1 聯(lián)合調(diào)度解的表示結(jié)構(gòu)設(shè)計

IGA 中采用含 3n個元素的一維數(shù)組結(jié)構(gòu)表示聯(lián)合調(diào)度解π。該結(jié)構(gòu)也是IGA 的染色體編碼結(jié)構(gòu)，每個元素對應(yīng)一個基因位。在該結(jié)構(gòu)中依照索引編號從小到大的次序為各個作業(yè)分別分配連續(xù)的3 個基因位，即g1、g2和g3。g1∈{0,1} ，指明當(dāng)前作業(yè)的外包狀態(tài)。g1=0 表示當(dāng)前作業(yè)在內(nèi)部完成加工；g1=1表示當(dāng)前作業(yè)被外包出去。g2指明當(dāng)前作業(yè)所在內(nèi)部加工批次的索引編號，g2∈{0,1,···,n}。g2=0 表示當(dāng)前作業(yè)不在任何內(nèi)部加工批次中。g3表示當(dāng)前作業(yè)制成品所在的配送批次。由于存在每個加工批次都僅容納單個作業(yè)的可能，故g3∈{0,1,2,···,「n·Q1/Q2?} ，「r?表 示不小于實數(shù)r的最小整數(shù)；g3=0 表示當(dāng)前作業(yè)不在任何配送批次中。由于每個作業(yè)僅有內(nèi)部加工和外包加工兩種選擇，故每個作業(yè)在g1和g2上不能同時取0。另因外包作業(yè)采取包干的方式，當(dāng)且僅當(dāng)g1=1 時 作業(yè)在g2和g3上的值都為0。為保證出自同一生產(chǎn)批次的制成品在同一配送批次中送達(dá)，規(guī)定：若兩個作業(yè)在g2上取值相等，則它們在g3上取值也相等。

考慮一個含6 個作業(yè)的IOPDSP 示例，取G=9 ，Q1=10，Q2=30 ， λ =1 ， μ =30 ，作 業(yè) 尺 寸、內(nèi) 部工時和外包成本信息如表2 所示。圖1 為該示例的一個可行解的表示結(jié)構(gòu)圖。其中，作業(yè)J1、J5被外包 出 去；內(nèi) 部 加 工 分B1和B2兩 批 次；作 業(yè)J2、J3和J6組 成B1， 作 業(yè)J4獨(dú) 自 在B2中 ；加 工 批 次B1和B2的制成品組成唯一的配送批次D1。

圖1 示例中一個可行解的表示結(jié)構(gòu)Figure 1 The representation structure of a feasible solution in the example

表2 IOPDSP 示例中的作業(yè)信息Table 2 Information for jobs in IOPDSP examples

2.2 初始種群的生成

IGA 中采用隨機(jī)方式生成初始種群 P op(0) 。該種群有 p opSize 條 染色體，每條染色體含 3n個基因位。P op(0) 中每條染色體按作業(yè)索引編號由小到大的次序逐步生成。對于滿足性質(zhì)1 中指定條件的作業(yè)，安排其到某個內(nèi)部加工批次中 (g1上的值為0)；對于滿足性質(zhì)2 中指定條件的作業(yè)，安排其到外包作業(yè)集中 (g1上的值為1)；對于性質(zhì)1 和2 中指定條件均不滿足的作業(yè)，其在3 個基因位上的值從各自有效范圍內(nèi)隨機(jī)產(chǎn)生。

2.3 染色體的適應(yīng)度評價

染色體的合法性判定是其適應(yīng)度評價的首要工作。IGA 中基于IOPDSP 特征的染色體合法性判定條件如下。

1) 作業(yè)外包總成本不超過G；

2) 每個加工批次所含作業(yè)尺寸之和不超過Q1；

3) 每個配送批次所含作業(yè)尺寸之和不超過Q2；

4) 每個作業(yè)在g1和g2上的值有且僅有一個為0；

5) 若兩個作業(yè)在g2上取值相同，則它們在g3上取值也相同。

一條染色體及其對應(yīng)的聯(lián)合調(diào)度解π若違反上述條件之一，則被視為非法染色體，記其適應(yīng)度值為0；若上述條件均滿足，則被視為合法染色體。對認(rèn)定合法的染色體，先按式 (1) 計算所對應(yīng)π的目標(biāo)函數(shù)值Z(π) ，再按式 (17) 計算適應(yīng)度值。

其中，M代表Z(π) 的最大可能值，文中取

2.4 染色體選擇機(jī)制

為避免高質(zhì)量染色體從種群中快速消失，以及尋優(yōu)過程易于陷入局部極優(yōu)的問題，IGA 采用帶精英保留的錦標(biāo)賽選擇機(jī)制產(chǎn)生新一代種群。IGA 中逐代執(zhí)行的染色體選擇步驟如下。

1) 從種群 P op(t) 中 選出適應(yīng)度值最大的elitCount條染色體直接進(jìn)入下一代種群 P op(t+1) ；

2) 從 種 群 P op(t) 中 隨 機(jī) 選 取 t ournmSize 條 染 色體，將它們置入錦標(biāo)賽選擇池 t ournament 中；

3) 對選擇池 t ournament 中所有染色體按適應(yīng)度值排序，從中選出適應(yīng)度值最大的染色體后置入下一代種群 P op(t+1) 中；

4) 重復(fù)執(zhí)行步驟2) 和3) p opSize-elitCount 次，直到 P op(t+1) 中 染色體條數(shù)達(dá)到 p opSize 。

2.5 染色體交叉與變異

鑒于在染色體編碼結(jié)構(gòu)中為每個作業(yè)分配3 個基因位，為防止因交叉操作產(chǎn)生大量非法染色體，每個作業(yè)對應(yīng)的3 個基因位需作為一個整體參與染色體交叉過程。IGA 借鑒文獻(xiàn)[16]中的均勻交叉法來實施染色體交叉，具體步驟如下。

首先從種群 P op(t) 中隨機(jī)選擇2 條親代染色體，分別為Parent1 和Parent2。然后判定染色體交叉執(zhí)行條件pc＞random(0,1) 是否滿足，pc為交叉率，反映均勻交叉的執(zhí)行概率； r andom(0,1) 表示區(qū)間 (0, 1) 上產(chǎn)生的隨機(jī)實數(shù)。若交叉執(zhí)行條件滿足，則按初始種群中染色體生成方式創(chuàng)建一個子代染色體Offspring。Offspring 中每個作業(yè)對應(yīng)的3 個基因位都有50%的概率取值為Parent1 中相應(yīng)基因位上的值，另有50%的概率取值為Parent2 中相應(yīng)基因位上的值。最后讓Offspring 取代Parent1，成為 P op(t) 中的一條染色體。圖2 為面向示例的染色體均勻交叉過程示意圖。

圖2 均勻交叉過程Figure 2 Processes of uniform crossover

為保持新一代種群中染色體的多樣性并避免輕易產(chǎn)生非法染色體，通過借鑒文獻(xiàn)[17]中相關(guān)做法，IGA 中采用均勻變異的方式實施染色體變異，具體步驟如下。

首先從種群 P op(t) 中按指定順序選出一條染色體，記作Chrm1，并按初始種群中生成染色體的方式生成另一條染色體，記作Chrm2。然后創(chuàng)建一個含 3n個元素的一維數(shù)組，用以保存變異后所得染色體Chrm3。

對染色體Chrm3 中每個作業(yè)，判定染色體變異執(zhí)行條件pm＞random(0,1) 是否滿足，pm為變異率，反映當(dāng)前作業(yè)發(fā)生變異的概率。若上述條件滿足，則Chrm3 中當(dāng)前作業(yè)對應(yīng)的3 個基因位取值為Chrm2 中相應(yīng)基因位上的值。若不滿足，則Chrm3中當(dāng)前作業(yè)對應(yīng)的3 個基因位取值為Chrm1 中相應(yīng)基因位上的值。變異后所得Chrm3 取代Chrm1，成為種群 P op(t) 中的一條染色體。圖3 為面向示例的染色體均勻變異過程示意圖。

圖3 均勻變異過程Figure 3 Processes of uniform mutation

2.6 迭代終止條件

IGA 中設(shè)定迄今最佳染色體的適應(yīng)度持續(xù)無改進(jìn)的最大迭代次數(shù)Imax=200n。IGA 會逐代更新并記錄迄今最佳染色體，當(dāng)它的適應(yīng)度值經(jīng)過連續(xù)200n次迭代未被更新時，IGA 終止運(yùn)行。

2.7 算法步驟

IGA 的執(zhí)行步驟如下。

步驟1設(shè)置下列參數(shù)的取值： p opSize ,elitCount,tournmSize,pc,pm,Imax。

步驟2按2.2 節(jié)所述生成初始種群 P op(0) ，設(shè)置迭代計數(shù)變量t，取其初值為1。

步驟3對種群 P op(t-1) 實施帶精英保留的錦標(biāo)賽選擇機(jī)制，其過程按2.4 節(jié)所述執(zhí)行。

步驟4對種群 P op(t-1) 先后實施均勻交叉和均勻變異操作，其過程按2.5 節(jié)所述執(zhí)行，得到新一代種群 P op(t) 。

步驟5設(shè)置t←t+1，判斷迭代終止條件是否滿足。若不滿足，則返回步驟3。

步驟6輸出種群中最佳染色體所對應(yīng)聯(lián)合調(diào)度解及其目標(biāo)函數(shù)值。

3 實例分析

3.1 實例描述

實例出自某陶瓷企業(yè)負(fù)責(zé)坯體燒制、外包及其制成品配送的管理一線。該企業(yè)中燒制坯體的設(shè)備是一臺高溫電窯爐，采用p-batch 模式，容量Q1=20 m3， 額定功率 P W=5 kW 。當(dāng)?shù)仄骄I(yè)用電目錄電價 E C=0.6 元/(kW·h) 。該企業(yè)單位時間上的批加工成本主要是單位時間上的用電成本，故λ=PW·EC·δ ， δ ＞0 為分時段的單位用電價格系數(shù)。該企業(yè)從第三方物流 (third-party logistics, 3PL) 公司租用車輛配送陶瓷制品，可租用的車型有多種。所有配送車輛都將陶瓷制品運(yùn)往同一經(jīng)銷商處。該企業(yè)可將坯體燒制與制成品配送包干轉(zhuǎn)包給合約制造商S1?？紤]到該企業(yè)與經(jīng)銷商之間距離、路況和行駛油耗等因素，3PL 公司對所有車型給出每單位體積運(yùn)力單車次的往返運(yùn)輸報價為 α ≈1.0 元/(m3·車次) 。對最大載荷量為Q2的車輛，其單車次配送成本μ=αQ2≈Q2元/車次。所關(guān)注的聯(lián)合調(diào)度情景如下。該企業(yè)的管理一線接到22 個坯體的燒制與配送任務(wù)，這些坯體來自同一經(jīng)銷商的訂貨，各自尺寸、內(nèi)部燒制時間和外包成本如表3所示，亟待利用合約制造商S1的產(chǎn)能，通過犧牲一定數(shù)額的外包成本而使 T C 顯著下降。該企業(yè)中坯體燒制時間的決定因素有多種，如材質(zhì)、厚度、釉面紋路等，與尺寸的相關(guān)度并不高。該企業(yè)肯付出的外包總成本有限，需事先根據(jù)經(jīng)營情況和融資能力設(shè)定預(yù)算值G=為外包總成本容許率。

表3 實例中坯體的尺寸、內(nèi)部燒制時間和外包成本信息Table 3 Sizes, inhouse firing time and outsourcing cost of ceramic bodies in the instance

3.2 基于實例的IGA 性能實驗分析

本節(jié)對IGA 開展IOPDSP 上的性能實驗分析，并與CPLEX 12.8 軟件的求解結(jié)果進(jìn)行比較。本實驗所用程序以Java 語言編程實現(xiàn)，運(yùn)行環(huán)境為處理器AMD Ryzen7 4800H；主頻2.90 GHz；RAM 內(nèi)存16.0 GB。預(yù)實驗中對IGA 的重要參數(shù)進(jìn)行校準(zhǔn)，得出的取值建議為 p opSize=50，pc=0.95，pm=0.01, e litCount=5 , t ournmSize=5 。

本實驗用到的6 個測試算例源于3.1 節(jié)所述實例。算例1 中坯體數(shù)為17，這17 個坯體的信息如表3中J1~J17對應(yīng)信息所示；算例2 中坯體數(shù)為18，這18 個坯體的信息如表3 中J1~J18對應(yīng)信息所示，以此類推。這6 個算例的其他參數(shù)取值如下：Q1=20 m3，Q2=40 m3， P W=5 kW ， δ =1.5 ， E C=0.6 元/(kW·h) ，μ=40 元/車次 ， η =0.3 。隨著坯體數(shù)增加，CPLEX在短時間內(nèi)得不到算例精確解的可能性增加。本實驗中將CPLEX 的求解時間上限設(shè)為3 600 s，運(yùn)用IGA 對每個算例獨(dú)立求解15 次，記下每次求解所得目標(biāo)函數(shù)值與耗時。此外，引入求解質(zhì)量偏差度量指標(biāo) G ap 來度量IGA 的求解性能。IGA 對各個算例的 G ap 指標(biāo)值為

其中，zIGA(π) 是IGA 獨(dú)立求解算例15 次所得目標(biāo)函數(shù)值的平均值；z*(π) 為CPLEX 求解當(dāng)前算例所得的最優(yōu)目標(biāo)函數(shù)值或在求解時長3 600 s 之外所獲可行解的目標(biāo)函數(shù)值。

表4 給出IGA 與CPLEX 對上述6 個算例的求解統(tǒng)計結(jié)果。其中，State 和Objective 分別表示CPLEX 在求解時限內(nèi)對當(dāng)前算例的求解狀態(tài)和所得最優(yōu)或可行解的目標(biāo)函數(shù)值；Min、Max、Avg和Sd 分別表示IGA 獨(dú)立求解當(dāng)前算例15 次所得目標(biāo)函數(shù)值的最小值、最大值、平均值及其標(biāo)準(zhǔn)差；Time表示IGA 獨(dú)立求解當(dāng)前算例15 次的平均耗時。由表4 可知，對n=17 的算例，在獨(dú)立運(yùn)行的15 次求解中IGA 多次求得精確最優(yōu)解，平均耗時僅約為CPLEX 求解平均耗時的1/700；對n∈{18, 19, 20, 21,22}的算例，CPLEX 耗時多達(dá)3 600 s 仍得不到各自精確解，僅能求出近優(yōu)解。對n∈{18, 19, 20}的算例，IGA 不僅能達(dá)到與CPLEX 相同的算例求解質(zhì)量 (Gap 值均為0.00)，且平均用時約為CPLEX 求得近優(yōu)解所耗時間均值的1/1 200，多次運(yùn)行所得解的質(zhì)量穩(wěn)定性也較高。對n∈{21, 22}的算例，在平均耗時不到4 s 的前提下IGA 在15 次獨(dú)立運(yùn)行中所得最差解比CPLEX 所得近優(yōu)解的質(zhì)量更優(yōu)，對應(yīng) G ap 值均在-0.5%以下。綜上，IGA 對6 個測試算例所得解的質(zhì)量可達(dá)到或優(yōu)于在限定3 600 s 運(yùn)行時間下CPLEX 所得解的質(zhì)量，且求解用時極短，體現(xiàn)出IGA 對IOPDSP 的求解有效性。

表4 IGA 與CPLEX 的算例求解統(tǒng)計結(jié)果1)Table 4 Solution results of IGA and CPLEX over test instances

3.3 基于實例的靈敏度實驗分析

本節(jié)利用靈敏度實驗法探析特定場景下可控因素的變化對實例中陶瓷企業(yè)作業(yè)運(yùn)營總成本 T C 產(chǎn)生的影響，以降低 T C 為目標(biāo)對可控因素的取值或決策給出建議。鑒于IGA 對IOPDSP 的求解有效性，運(yùn)用IGA 對實例中可控因素的靈敏度進(jìn)行研究。實例中坯體的總數(shù)、尺寸和內(nèi)部燒制時間，電窯爐的容量和額定功率，合約商對坯體的外包索價確定后再發(fā)生變化的可能性很小，故它們屬于不可控因素。坯體外包總成本預(yù)算G、單位時間上坯體批加工成本 λ 和單車次分批配送成本 μ 分別會因企業(yè)經(jīng)營與融資狀況、用電分時選擇方案和選用車型的不同而出現(xiàn)取值上變化，故它們是實例中可控因素。G與 η 之間成正比關(guān)系，故外包總成本預(yù)算狀況會反映在η的取值上。λ 與 δ 之間成正比關(guān)系。根據(jù)當(dāng)?shù)毓ど虡I(yè)分 時 用電 政策 規(guī)定①《山東省發(fā)展改革委員會完善工商業(yè)分時電價政策的通知 (魯發(fā)改價格〔2021〕986 號) 》， δ 的可 能值 有0.5、1.0 和1.5，分別對應(yīng)燒制時間在用電低谷期、平時期和高峰期的情況，故 λ ∈{1.5,3.0,4.5} 。單車次配送成本μ由選用車型的最大載荷量Q2決定。3PL 公司提供9 種配送車型，最大載荷量從40 m3到80 m3不等，相鄰車型的最大載荷量相差約5.0 m3。

下 面考察 η 、 λ 和 μ 取 值變化對 T C 的 影響。經(jīng)預(yù)實驗發(fā)現(xiàn)，當(dāng) η ＜0.1 時坯體外包所帶來的降本效果很??；當(dāng) η ＞0.8 時 η 值的變化也基本不會對 T C 產(chǎn)生影響。本實驗中設(shè)定 η 的有效觀測區(qū)間為[0.1, 0.8]，觀測浮動步長為0.05，觀測點(diǎn)有15 個。為區(qū)分作業(yè)外包總成本預(yù)算特征，將 η 的有效觀測區(qū)間劃分為3 段：[0.1, 0.3]； (0.3, 0.5]； (0.5, 0.8]，分別對應(yīng)外包總成本預(yù)算的高度緊張、中度緊張和充足狀態(tài)。本實驗針對實例的以下兩種場景而展開。

場景1受經(jīng)銷商緊急催貨或配送車型可用性動態(tài)變化等情況所限，陶瓷企業(yè)不得不將坯體燒制時間安排在用電高峰期。因此時燒制成本高昂，該企業(yè)迫切希望通過安排一部分坯體外包或優(yōu)選配送車型而使 T C 下降。

場景2陶瓷企業(yè)因現(xiàn)金流狀況不佳，融資能力不足，導(dǎo)致對坯體外包總成本的預(yù)算高度緊張，亟待通過靈活安排內(nèi)部電窯爐的燒制時間，選用合適的配送車型而使 T C 下降。

在 面向 場景1 的 靈敏 度 實驗 中，取 λ =4.5 ，面向不同的 ( η,μ) 取 值組合觀測IGA 求得的 T C 值。由于 η 的有效觀測區(qū)間內(nèi)有15 個觀測點(diǎn)和9 種可選車型， ( η,μ) 取 值組合共計1 5×9=135 種。在每種(η,μ)取值組合下IGA 獨(dú)立求解實例15 次，并統(tǒng)計這15次所得目標(biāo)函數(shù)值的均值。圖4 給出135 種 ( η,μ) 取值組合下分別運(yùn)用IGA 所得的 T C 均值。由圖4 可得如下結(jié)果。

圖4 135 種 ( η,μ) 取值組合下的 T C 均值Figure 4 Means of TC using 135 combinations of (η,μ)

1) 不同的 ( η,μ) 取 值組合下 T C 的均值有明顯差異。圖中顯示的最高 T C 均值為474.8 元，出現(xiàn)在(η,μ)的 取值組合 ( 0.1,65.0) 下 ；最低 T C 均值為242.4元，出現(xiàn)在 ( η,μ) 的 取值組合 (0.8, 40.0) 下，最高TC均值約為其最低均值的1.96 倍。

2) 在 η 取值相同的情形下， μ 的不同取值對TC 有一定影響。當(dāng)外包總成本預(yù)算處于緊張狀態(tài)時(η≤0.5)，該影響的顯著性增強(qiáng)；但在整體上難以直觀確定使 T C 下降效果相對更好的配送車型。

3) 在 μ 取值相同的情形下， η 的不同取值對TC的影響更明顯，并在有效觀測區(qū)間內(nèi)隨著 η 值的按步長浮動增加， T C 逐漸下降。

4) 建議該企業(yè)在場景1 下通過融資、貸款等手段盡量增加外包總成本預(yù)算，使 η 值不小于0.75。

為驗證上述現(xiàn)象是否有統(tǒng)計學(xué)意義，以 T C 為因變量， η 和 μ 為自變量，對場景1 下收集的靈敏度實驗數(shù)據(jù)進(jìn)行雙因素方差分析，結(jié)果如表5 所示。其中， η 和 μ 組 成交互項的p值顯示為0.00，認(rèn)為不同(η,μ)取 值組合下 T C 的差異有統(tǒng)計學(xué)上顯著性，從圖4的結(jié)果1) 得以證實； η 和 μ 各 自單項的p值都顯示為0.00，但 η 對應(yīng)的F值遠(yuǎn)大于 μ 對應(yīng)的F值；可見相較于 μ ， η 對 T C 的影響顯著 性更高，從圖4 的結(jié)果2) 和3) 得以證實。

表5 對場景1 下實驗數(shù)據(jù)的雙因素方差分析結(jié)果Table 5 Two-factor ANOVA results using experimental data in Scenario 1

在 面向 場景2 的 靈敏 度 實驗 中，取 η =0.2 ，面向不同的 ( λ,μ) 取值組合觀測IGA 求得的 T C 值。由于分時用電價格系數(shù)的3 種選項和可選的9 種車型， ( λ,μ) 取值組合共計 3 ×9=27 種。在每種 ( λ,μ) 取值組合下IGA 獨(dú)立求解實例15 次，并統(tǒng)計這15 次所得目標(biāo)函數(shù)值的均值。圖5 給出27 種 ( λ,μ) 取值組合下分別運(yùn)用IGA 所得的 T C 均值。由圖5 可發(fā)現(xiàn)以下4 個結(jié)果。

圖5 27 種 ( λ,μ) 取值組合下的 T C 均值Figure 5 Means of T C using 27 combinations of(λ,μ)

1) 不同的 ( λ,μ) 取值組合下 T C 的均值存在差異。圖中顯示的最高 T C 均值為449.0 元，出現(xiàn)在(λ,μ) 的取值組合 ( 4.5,80.0) 下 ；最低 T C 均值為278.5元，出現(xiàn)在 ( λ,μ) 的取值組合 ( 1.5,60.0) 下 ，最低TC均值約為其最高均值的62.03%。

2) 在 λ 取值相同的情形下， μ 的不同取值對TC有 明 顯 影 響。當(dāng) μ =60 時 該 企 業(yè) 在 T C 上 取 得 相 對 更好的下降效果，故不建議在場景2 下選用最大載荷量與60 m3相差過大的車型。

3) 在 μ 取值相同的情形下， λ 的不同取值對TC的影響更加明顯。坯體的內(nèi)部燒制時間安排在用電平時期和低谷期所耗 T C 均值比安排在用電高峰期分別下降13.93%和29.17%，故建議該企業(yè)在場景2 下把坯體燒制時間安排在用電非峰時段。

4) 當(dāng)把坯體燒制時間安排在用電低谷期時，通過優(yōu)選配送車型可使 T C 進(jìn)一步下降。從3PL 公司選用Q2= 6 0 m3的車型比選用Q2= 8 0 m3的車型在TC值上會下降12.15%。

為驗證上述現(xiàn)象是否有統(tǒng)計學(xué)意義，以 T C 為因變量， λ 和 μ 為自變量對場景2 下收集的靈敏度實驗數(shù)據(jù)進(jìn)行雙因素方差分析，結(jié)果如表6 所示。其中， λ 和 μ 組 成交互項的p值顯示為0.00，認(rèn)為不同的 ( λ,μ) 取值組合下 T C 的差異具有統(tǒng)計學(xué)上顯著性，從圖5 的結(jié)果1) 得以證實； λ 和 μ 各 自單項的p值都顯示為0.00，但 λ 對應(yīng)的F值遠(yuǎn)大于 μ 對應(yīng)的F值，可見 λ 對 T C 的影響顯著性比 μ 更高，從圖5 的結(jié)果2) 和3) 得到驗證。

表6 對場景2 下實驗數(shù)據(jù)的雙因素方差分析結(jié)果Table 6 Two-factor ANOVA results using experimental data in Scenario 2

4 結(jié)論

本研究關(guān)注p-batch 模式下單機(jī)差異尺寸作業(yè)外包、生產(chǎn)與配送聯(lián)合調(diào)度問題 (IOPDSP)，為其構(gòu)建0-1 規(guī)劃模型，并依賴問題特征設(shè)計出改進(jìn)型遺傳算法 (IGA)。利用來自某陶瓷企業(yè)的IOPDSP 測試算例，對比分析了IGA 與CPLEX 軟件的求解表現(xiàn)。結(jié)果表明，IGA 所得解的質(zhì)量不低于CPLEX 在3 600 s 時限內(nèi)所得解的質(zhì)量，且求解耗時小于4 s。而后，運(yùn)用IGA 針對IOPDSP 實例分場景開展靈敏度實驗分析，圍繞外包總成本容許率、分時單位電價和配送車型三因素探究取值變化對作業(yè)運(yùn)營總成本 T C 的影響，得出以下主要結(jié)論。

1) 當(dāng)陶瓷企業(yè)將坯體燒制時間安排在用電高峰期時，相較于配送車型的變化，外包總成本容許率的變化對 T C 的影響更顯著。建議企業(yè)通過融資或貸款等手段努力增加外包總成本預(yù)算。

2) 當(dāng)陶瓷企業(yè)的外包總成本預(yù)算處于高度緊張狀態(tài)時，分時單位電價和配送車型上的變化都對TC有顯著影響，前者的顯著性更高。建議企業(yè)將坯體燒制時間安排在用電非峰時段，優(yōu)選最大載荷量為60 m3的車型承擔(dān)制成品分批配送任務(wù)。