考慮外包選擇的分批處理與配送聯合調度模型研究

李紅葉，劉 樂（濟南大學 管理科學與工程學院，山東 濟南 250002）

0 引 言

生產與配送聯合調度問題(integrated production and distribution scheduling problem,IPDSP)，是近年來供應鏈管理領域的一個研究熱點[1]。

IPDSP研究中現有的處理模式包括串行處理、串行批處理和并行批處理三種。并行批處理(parallel batching,p-batch)是醫療器械滅菌[2]、陶瓷燒制[3]等行業中常見的處理模式。在p-batch模式下，批處理設備具有限定的容量上限；一個批次的處理時間等于該批次用時最長作業的處理時間；同一處理批次的各個作業具有相同的開工時間與完工時間，但其尺寸卻各不相同。除了處理模式以外，發貨運輸方式也是區分不同IPDSP研究的一個依據。作為發貨運輸的常見方式之一，分批配送（batch delivery，BD）在載荷量的約束下使車輛盡量滿載運輸，以減少車輛的派遣次數；這種策略不僅能充分利用運力資源，還能有效節省配送開支[4]。文獻[3]和[4]是基于p-batch模式和BD方式的兩項IPDSP研究成果，但其均未考慮作業交付客戶的時間晚于指定交付期限時需承擔相應罰金這一情況。

設備長時間連續運轉會導致性能下降、出現安全隱患和故障停機等問題，為避免內部服務過程中斷及其恢復后需二次處理的問題，服務商可將一部分作業外包，使所有內部(未外包)作業的處理在給定的硬時間窗內完成[5]。然而，作業的可外包性對IPDSP研究提出了新的挑戰，特別是在有多個轉包商可供選擇的情況下，每個作業都要面臨外包與否決策，每個外包作業都要面臨轉包商的選擇決策，每個內部作業都要先后參與處理批次調度和配送批次調度。考慮外包選擇的IPDSP研究雖已有成果問世[6]，但尚處于起步階段。

在p-batch處理模式和直接發貨型BD方式下，面向多轉包商的作業外包-處理-配送聯合調度涉及轉包商選擇、內部批調度、分批配送調度等決策環節。由于缺乏科學的理論指導，這些決策環節在實際運作過程中往往分離執行，導致總運營成本和交付延誤率居高不下。基于此，本研究聚焦于p-batch模式下基于單機-多轉包商-單客戶條件、考慮外包選擇的作業分批處理-配送聯合調度問題（Integrated Batch Processing and Distribution Scheduling Problem with Outsourcing Options,IBPDSP_OO），旨在建立起混合整數規劃模型，使所建模型在軟件CPLEX中實現并對一個實例進行精確求解。

1 問題描述與建模

1.1 符號定義

IBPDSP_OO的主要參數如下。其中，j、h、k、l分別是對作業、轉包商、內部處理批次和配送批次的索引編號。

a.集合：J={J1，J2，...，Jn}表示含n個作業的待處理作業集；S={S1，S2，...，Sm}表示含m個轉包商的集合；π=[Oπ，B，D]表示聯合調度解；Oπ、Iπ分別表示面向π的外包作業集、內部作業集；Oπh表示π中外包給轉包商Sh的作業集（h∈1，2，...，m）；B={B1，B2，...，Bb}表示面向Iπ、含b個處理批次的調度方案（b≤n）；D={D1，D2，...，Dd}表示面向B、含d個配送批次的配送方案（d≤n）；

b.參數：TCπ、OCπ、TPCπ分別為面向π的運營總成本、外包總成本、延誤總罰金；IBCB為面向B的內部批處理總成本；TPCo為面向Oπ的外包作業延誤總罰金；DCD、TPCD分別為面向D的配送總成本、延誤總罰金；sj、pj分別為作業Jj的尺寸與內部工時（j∈1，2，...，n）；CDD為客戶面向J指定的公共交貨期；ljh、ojh分別為轉包商Sh對作業Jj的交付客戶時間、外包報價；t為從服務商到客戶的單程配送時長；Q1、Q2分別為批處理設備容量和配送車輛的最大載荷量；λ為單位時間內的內部批處理成本；μ為單車次的往返配送成本；β為J中所有作業每延誤單位時間所受懲罰的金額；M為足夠大的正實數；

c.連續變量：Pk、Ck分別為處理批次Bk的工時、完成時間（k∈{1，2，...，b}）；dell為配送批次Dl的交付客戶時間（l∈{1，2，...，d}）；delj、Tj分別為作業Jj的交付客戶時間、相對于CDD的延誤時間；

d.決策變量：xjk表示若作業Jj在處理批次Bk中，就為1，否則為0；yk表示若處理批次Bk不為空集，就為1，否則為0；zjh表示若作業Jj由轉包商Sh加工配送，就為1，否則為0；ujl表示若作業Jj在配送批次Dl中，就為1，否則為0；vl表示若配送批次Dl不為空集，就為1，否則為0；wkl表示若處理批次Bk在配送批次Dl中，就為1，否則為0。

1.2 假設條件與問題描述

IBPDSP_OO的假設條件如下。

a.服務商的批處理設備采用p-batch模式，在同一時刻最多處理一個批次，不允許各處理批次搶占設備；因設備需定期維護，所以服務商對J的內部批處理需滿足硬時間窗約束：限Ck處于0到R時刻之間（k∈{1，2，...，b}），即0≤Ck≤R。

b.作業集J都來自同一客戶；每個作業的尺寸大小各異，但都不超過Q1，所有作業經處理后尺寸都不發生變化。

c.每個作業都可外包，且可外包給任意轉包商。

d.外包作業的處理與配送任務由包干委托給選定的轉包商完成。服務商內部處理批次是其分批配送的基本單位。

e.配送車輛充足且車型統一，它們每完成一次交付客戶任務都消耗相同的配送成本和時長。

f.內部處理批次不會立即發貨配送給客戶，而要等待其所在配送批次的全部處理批次都完成后才發貨配送。

g.內部處理批次從完成到發車配送期間的在庫成本被折算到內部批處理總成本和延誤時間總罰金當中。

IBPDSP_OO描述如下：在0時刻，作業集J到達擁有一臺批處理設備的服務商處等待聯合調度。J中每個作業既可在內部批次中完成處理并由同質車輛經t個時間單位按BD方式運往客戶C1，也可外包給某一轉包商包干完成其處理和配送任務。如果Jj（j∈1，2，...，n）外包給轉包商Sh（h∈1，2，...，m），則delj=ljh，服務商需為其向Sh支付Ojh；如果Jj在服務商內部處理，則delj等于其所在配送批次的交付客戶時間。一旦Jj的delj超過CDD，就會受到延誤懲罰，罰金為β·（delj-CDD）。在滿足服務商內部批處理硬時間窗約束、車輛載荷量和批處理設備容量均有上限的條件下，IBPDSP_OO的優化目標為：先將J中的作業合理分配到不同的內部處理批次和不同轉包商的外包作業集中，再將各個內部處理批次合理分配給不同配送批次，求出π*=[Oπ*，B*，D*]，使TCπ*=OCπ*+IBCB*+DCD*+TPCπ*達到最小。

1.3 數學模型

式（1）是面向π的運營總成本的最小化函數；式（2）排除了Jj既被外包又在內部分批處理的可能，并限定每個內部作業只能在同一個處理批次中、每個外包作業只能分配給一個轉包商；式（3）排除了Jj既被外包又經服務商處理后將其配送給客戶的可能，并限定每個內部作業經處理后只能在一個配送批次中；式（4）確保每個內部作業經處理后都有一個配送批次將其配送給客戶；式（5）排除了某個內部作業所在處理批次及其所在配送批次未被創建的可能；式（6）既排除了某個內部處理批次所在的配送批次未被創建的可能，又能保證分配到每個配送批次的內部處理批次都已被創建；式（7）保證若無Jj分配到一個內部處理批次中則該處理批次不被創建；式（8）保證若一個配送批次中不存在任何處理后的作業，則該配送批次不被創建；式（9）保證若一個配送批次中，不存在任何處理批次，則該配送批次不被創建；式（10）、式（11）聯合保證若Jj在批次Bk中完成處理，則它是否被安排到配送批次Dl中交付取決于配送批次Dl中是否存在批次Bk；式（12）、式（13）分別規定服務商按編號依次創建內部處理批次和配送批次；式（14）確保每個內部處理批次中作業尺寸之和不超過批處理設備的容量；式（15）確保每個配送批次的作業尺寸之和不超過車輛的最大載荷量；式（16）、式（17）聯合保證若Bk已被創建，則其工時等于其所含各個作業的最大工時，若Bk未被創建，則其工時等于0；式（18）提出各個內部處理批次完工時間的計算方式；式（19）保證每個內部處理批次的完工時間都不得晚于R時刻；式（20）、式（21）聯合保證若Dl已被創建，則其交付客戶時間等于其中各個處理批次的最大完工時間與單程配送時長之和，若Dl未被創建，則其交付客戶時間等于0；式（22）明確了當Jj在Bk中完成處理時，它的延誤時間下限值；式（23）、式（24）給出Jj在不同交付情形下延誤時間的計算式，前者對應作業Jj在配送批次Dl中完成交付的情形，后者對應作業Jj外包給轉包商Sh后由Sh完成交付的情形；式（25）指明6組整型變量的二元屬性；式（26）指明4組連續變量的非負屬性。

2 實例求解

實例來自采用p-batch模式、為定點醫院提供可復用醫療器械（reusable medical devices,RMD）滅菌服務的服務商，RMD滅菌作業外包-內部批處理-分批配送聯合決策是該企業運作管理的關鍵難題之一，恰好與本研究所建立的模型解決的問題相吻合。

2.1 聯合調度情景

在0時刻，滅菌服務商接到10個來自定點醫院的RMD滅菌作業，它們各自的尺寸、內部滅菌時間以及兩家轉包商S1、S2對它們的外包報價和交付客戶的時間信息如表1所示。定點醫院對這10個作業向滅菌服務商提出的交付期限為CDD=20.0 h。另外，通過實地觀測，其他問題的參數取值如下：Q1=25.0 m3、Q2=50.0 m3、t=3.0 h、λ=3.0、μ=50.0 ￥/車次、R=30 h、CDD=20.0 h、β=6.0 ￥/h。當前情景下亟待服務商實施作業外包與分批處理-配送聯合調度，以使運營總成本達到最低。

表1 RMD 信息表

2.2 求解結果

選用版本號為12.8的CPLEX軟件對上述實例進行求解。首先，借助CPLEX軟件中的Java API對IBPDSP_OO以所建數學模型的形式（見1.3節）程序實現；然后，基于實例數據運用已實現的程序進行優化求解。經過3 328.05秒的運行時間，CPLEX軟件求出該實例的一個精確最優解，其目標函數值(運營總成本)為823.0 ￥。它所對應的聯合調度方案詳情如下：作業J3、J4、J6轉包給S1，J5轉包給S2，其余RMD滅菌作業在該企業內部完成分批處理和分批配送。其中包括3個內部滅菌處理批次，即B={B1，B2，B3}；處理批次B1由J1和J8組成，處理批次B2由J2和J7組成，處理批次B3由J9和J10組成；滅菌后作業的配送批次有2個，即D={D1，D2}；配送批次D1僅含有處理批次B1，處理批次B2和B3共同組成配送批次D2。

3 結 論

本研究針對基于單機批處理環境的服務商作業外包、內部處理與分批配送的聯合調度問題，為其建立了以運營總成本最小化為目標的混合整數規劃模型，并將該模型在軟件CPLEX中完成了程序實現。最后，利用已實現的程序對來自某醫療滅菌服務商的實例進行精確求解，驗證了該模型的正確性與實用性。