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

0 引 言

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

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

設(shè)備長時間連續(xù)運轉(zhuǎn)會導(dǎo)致性能下降、出現(xiàn)安全隱患和故障停機等問題，為避免內(nèi)部服務(wù)過程中斷及其恢復(fù)后需二次處理的問題，服務(wù)商可將一部分作業(yè)外包，使所有內(nèi)部(未外包)作業(yè)的處理在給定的硬時間窗內(nèi)完成[5]。然而，作業(yè)的可外包性對IPDSP研究提出了新的挑戰(zhàn)，特別是在有多個轉(zhuǎn)包商可供選擇的情況下，每個作業(yè)都要面臨外包與否決策，每個外包作業(yè)都要面臨轉(zhuǎn)包商的選擇決策，每個內(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é)在實際運作過程中往往分離執(zhí)行，導(dǎo)致總運營成本和交付延誤率居高不下?；诖耍狙芯烤劢褂趐-batch模式下基于單機-多轉(zhuǎn)包商-單客戶條件、考慮外包選擇的作業(yè)分批處理-配送聯(lián)合調(diào)度問題（Integrated Batch Processing and Distribution Scheduling Problem with Outsourcing Options,IBPDSP_OO），旨在建立起混合整數(shù)規(guī)劃模型，使所建模型在軟件CPLEX中實現(xiàn)并對一個實例進(jìn)行精確求解。

1 問題描述與建模

1.1 符號定義

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

a.集合：J={J1，J2，...，Jn}表示含n個作業(yè)的待處理作業(yè)集；S={S1，S2，...，Sm}表示含m個轉(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個處理批次的調(diào)度方案（b≤n）；D={D1，D2，...，Dd}表示面向B、含d個配送批次的配送方案（d≤n）；

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

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

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è)備；因設(shè)備需定期維護，所以服務(wù)商對J的內(nèi)部批處理需滿足硬時間窗約束：限Ck處于0到R時刻之間（k∈{1，2，...，b}），即0≤Ck≤R。

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

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

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

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

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

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

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

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

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

2 實例求解

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

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

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

表1 RMD 信息表

2.2 求解結(jié)果

選用版本號為12.8的CPLEX軟件對上述實例進(jìn)行求解。首先，借助CPLEX軟件中的Java API對IBPDSP_OO以所建數(shù)學(xué)模型的形式（見1.3節(jié)）程序?qū)崿F(xiàn)；然后，基于實例數(shù)據(jù)運用已實現(xiàn)的程序進(jìn)行優(yōu)化求解。經(jīng)過3 328.05秒的運行時間，CPLEX軟件求出該實例的一個精確最優(yōu)解，其目標(biāo)函數(shù)值(運營總成本)為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個內(nèi)部滅菌處理批次，即B={B1，B2，B3}；處理批次B1由J1和J8組成，處理批次B2由J2和J7組成，處理批次B3由J9和J10組成；滅菌后作業(yè)的配送批次有2個，即D={D1，D2}；配送批次D1僅含有處理批次B1，處理批次B2和B3共同組成配送批次D2。

3 結(jié) 論

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