考慮外包選擇的分批處理與配送聯(lián)合調(diào)度模型研究

李紅葉，劉 樂（濟(jì)南大學(xué) 管理科學(xué)與工程學(xué)院，山東 濟(jì)南 250002）

0 引 言

生產(chǎn)與配送聯(lián)合調(diào)度問題(integrated production and distribution scheduling problem,IPDSP)，是近年來供應(yīng)鏈管理領(lǐng)域的一個(gè)研究熱點(diǎn)[1]。

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

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

在p-batch處理模式和直接發(fā)貨型BD方式下，面向多轉(zhuǎn)包商的作業(yè)外包-處理-配送聯(lián)合調(diào)度涉及轉(zhuǎn)包商選擇、內(nèi)部批調(diào)度、分批配送調(diào)度等決策環(huán)節(jié)。由于缺乏科學(xué)的理論指導(dǎo)，這些決策環(huán)節(jié)在實(shí)際運(yùn)作過程中往往分離執(zhí)行，導(dǎo)致總運(yùn)營成本和交付延誤率居高不下?；诖耍狙芯烤劢褂趐-batch模式下基于單機(jī)-多轉(zhuǎn)包商-單客戶條件、考慮外包選擇的作業(yè)分批處理-配送聯(lián)合調(diào)度問題（Integrated Batch Processing and Distribution Scheduling Problem with Outsourcing Options,IBPDSP_OO），旨在建立起混合整數(shù)規(guī)劃模型，使所建模型在軟件CPLEX中實(shí)現(xiàn)并對一個(gè)實(shí)例進(jìn)行精確求解。

1 問題描述與建模

1.1 符號定義

IBPDSP_OO的主要參數(shù)如下。其中，j、h、k、l分別是對作業(yè)、轉(zhuǎn)包商、內(nèi)部處理批次和配送批次的索引編號。

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

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

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

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

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

IBPDSP_OO的假設(shè)條件如下。

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

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

c.每個(gè)作業(yè)都可外包，且可外包給任意轉(zhuǎn)包商。

d.外包作業(yè)的處理與配送任務(wù)由包干委托給選定的轉(zhuǎn)包商完成。服務(wù)商內(nèi)部處理批次是其分批配送的基本單位。

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

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

g.內(nèi)部處理批次從完成到發(fā)車配送期間的在庫成本被折算到內(nèi)部批處理總成本和延誤時(shí)間總罰金當(dāng)中。

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

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

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

2 實(shí)例求解

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

2.1 聯(lián)合調(diào)度情景

在0時(shí)刻，滅菌服務(wù)商接到10個(gè)來自定點(diǎn)醫(yī)院的RMD滅菌作業(yè)，它們各自的尺寸、內(nèi)部滅菌時(shí)間以及兩家轉(zhuǎn)包商S1、S2對它們的外包報(bào)價(jià)和交付客戶的時(shí)間信息如表1所示。定點(diǎn)醫(yī)院對這10個(gè)作業(yè)向滅菌服務(wù)商提出的交付期限為CDD=20.0 h。另外，通過實(shí)地觀測，其他問題的參數(shù)取值如下：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。當(dāng)前情景下亟待服務(wù)商實(shí)施作業(yè)外包與分批處理-配送聯(lián)合調(diào)度，以使運(yùn)營總成本達(dá)到最低。

表1 RMD 信息表

2.2 求解結(jié)果

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

3 結(jié) 論

本研究針對基于單機(jī)批處理環(huán)境的服務(wù)商作業(yè)外包、內(nèi)部處理與分批配送的聯(lián)合調(diào)度問題，為其建立了以運(yùn)營總成本最小化為目標(biāo)的混合整數(shù)規(guī)劃模型，并將該模型在軟件CPLEX中完成了程序?qū)崿F(xiàn)。最后，利用已實(shí)現(xiàn)的程序?qū)碜阅翅t(yī)療滅菌服務(wù)商的實(shí)例進(jìn)行精確求解，驗(yàn)證了該模型的正確性與實(shí)用性。