程八一， 黃小曼， 楊艷艷， 胡笑旋

(1. 合肥工業(yè)大學管理學院， 合肥 230009； 2. 過程優(yōu)化與智能決策教育部重點實驗室, 合肥 230009)

?

差異分批模式下的聯(lián)合成本優(yōu)化問題及算法

程八一1， 2， 黃小曼1， 2， 楊艷艷1， 2， 胡笑旋1， 2

(1. 合肥工業(yè)大學管理學院， 合肥 230009； 2. 過程優(yōu)化與智能決策教育部重點實驗室, 合肥 230009)

提出了一類制造企業(yè)的聯(lián)合成本優(yōu)化問題，將企業(yè)的產(chǎn)品制造環(huán)節(jié)和配送環(huán)節(jié)進行協(xié)同運作，實現(xiàn)供應鏈環(huán)境下的聯(lián)合調(diào)度.在生產(chǎn)環(huán)節(jié)，考慮一類典型的差異分批制造模式，即待加工的作業(yè)尺寸有差異，而批處理設備的容量確定，設備環(huán)境為多臺并行設備；在配送環(huán)節(jié)，企業(yè)采用自有車輛進行運輸，車輛具有相同的運輸能力；若完工的作業(yè)在當前無可用車輛進行配送，則轉(zhuǎn)入產(chǎn)成品庫存；聯(lián)合成本為生產(chǎn)、庫存和配送三階段的總成本.本文首先構造了基于整數(shù)規(guī)劃的數(shù)學模型，證明了聯(lián)合成本的最小化問題是強NP-hard問題；然后設計了多項式時間的近似算法，分析了算法的時間復雜性，并證明了算法的求解性能.

供應鏈調(diào)度； 聯(lián)合成本； 差異作業(yè)； 近似算法

0　引　言

在當前激烈的市場競爭環(huán)境下，制造型企業(yè)不再單純的追求大批量、高速度的生產(chǎn)方式，而是將重點放在提高作業(yè)質(zhì)量、改善客戶服務水平等方面，統(tǒng)籌企業(yè)的采購、庫存、生產(chǎn)與配送環(huán)節(jié)，獲得經(jīng)濟效益的總體優(yōu)化，從而提升企業(yè)的綜合競爭力.供應鏈調(diào)度便是從制造企業(yè)所在供應鏈的視角出發(fā)，采用精確調(diào)度的方法，考慮面向供應鏈的多環(huán)節(jié)優(yōu)化與調(diào)度，包括制造企業(yè)的原材料采購、生產(chǎn)、庫存和配送過程.其思想由Hall和Potts[1]兩位學者提出，他們的研究表明，在傳統(tǒng)的制造模式下，通過供應鏈調(diào)度的方法，能夠?qū)⒅圃炱髽I(yè)的總成本降低20%以上.

近年來供應鏈調(diào)度的研究有了較快的進展，很多學者在供應鏈調(diào)度模型的構建以及優(yōu)化算法的設計方面做了大量的工作.按照供應鏈調(diào)度所涉及的范圍可以分為兩階段供應鏈調(diào)度和三階段調(diào)度，其中兩階段調(diào)度問題涉及到供應商-制造企業(yè)和制造企業(yè)-客戶這兩類模型，三階段調(diào)度則為供應商-制造企業(yè)-客戶模型.在供應商-制造企業(yè)模型中，Chen和Hall[2]和Agnetis等[3]研究了供應商和制造企業(yè)最優(yōu)方案的沖突，分別提出了一類兼顧二者利益的合作機制；Torabi等[4]考慮了供應商和制造企業(yè)的原材料庫存和配送總成本，提出了優(yōu)化總成本的智能算法.兩階段供應鏈調(diào)度問題的另一種模型便是制造企業(yè)-客戶模型，Chen和Vairaktarakis[5]考慮了古典生產(chǎn)模式下的生產(chǎn)與配送調(diào)度問題，證明了該模式下優(yōu)化制造跨度和成本問題均為NP-hard問題，提出了幾類啟發(fā)式算法；由于這類問題的計算復雜性，后期的研究集中在近似算法[6-7]和智能算法方面[8-9]，另外，學者們考慮了兩階段供應鏈調(diào)度問題的現(xiàn)實約束并設計了優(yōu)化算法，這些約束包括作業(yè)保質(zhì)期極短[10]和生產(chǎn)能力有限[11]等.另一方面，三階段供應鏈調(diào)度問題，則涉及到原材料設計、生產(chǎn)加工和成品配送三個部分，Hall和Potts[1]系統(tǒng)的構造了該類問題在古典生產(chǎn)模式下的模型，并設計了基于動態(tài)規(guī)劃的優(yōu)化算法；Selvarajah和Steiner[12]設計了一類優(yōu)化配送-庫存聯(lián)合成本的近似算法，最壞性能比為1.5；Sawik[13]考慮了一類優(yōu)化庫存、生產(chǎn)和配送總成本的問題，且作業(yè)具有很長的生命周期；Yimer和Demirli[14]則提出了一類分解算法，將三階段問題分解為生產(chǎn)和運輸兩個子問題，并采用遺傳算法進行優(yōu)化；后期的研究中學者們也考慮了工業(yè)中的實際約束，包括帶時間窗[15]和同步原料補給[16]的供應鏈調(diào)度問題.

但上述的供應鏈調(diào)度研究均在古典生產(chǎn)模式[17]下展開，這類模式的基本假定，就是加工設備同時生產(chǎn)一個作業(yè)或者固定數(shù)量個作業(yè)，前者稱為傳統(tǒng)生產(chǎn)模式，后者稱為批生產(chǎn)模式.但在現(xiàn)實工業(yè)中，大量的生產(chǎn)問題并不屬于這類生產(chǎn)模式，例如半導體芯片制造業(yè)、陶瓷制造業(yè)、食品加工業(yè)、金屬冶煉業(yè)等，以芯片制造業(yè)為例，芯片出廠前的最后一道工序是芯片的高溫預燒，工序的目的是通過高溫處理發(fā)現(xiàn)有質(zhì)量問題的芯片，從而保證出廠芯片的質(zhì)量.預燒的處理時間長，是其他工序的幾倍乃至幾十倍，芯片有不同的尺寸和預燒時間，均由客戶指定，而預燒爐的容積是確定的，在預燒時，芯片可以分批放在爐中進行，每一批芯片的總體積不能超過爐子的容積，同時，芯片的預燒時間可以大于客戶要求的時間，但不能小于這個時間，因此一批芯片的處理時間等于其中芯片的最長處理時間.稱這類生產(chǎn)模式為差異分批模式(production with batch-processing machines with arbitrary-size jobs)，在食品加工業(yè)、金屬冶煉業(yè)中，同樣有大量的該類問題.1994年，Uzsoy[18]提出了差異分批模式的單設備調(diào)度問題，證明了單設備的制造跨度最優(yōu)化問題是強NP-hard問題，總完工時間問題是NP-hard問題，并分別設計了啟發(fā)式算法；Zhang等[19]分析了Uzsoy提出的算法的性能，并進一步設計了一種最壞性能比為7/4的MLPT-FF算法；Tang等[20]針對一類考慮原材料庫存的差異作業(yè)批調(diào)度問題設計了近似算法，程八一等[21]和Tang等[22]分別提出了優(yōu)化流水車間問題的近似算法；文獻[23,24]采用了動態(tài)規(guī)劃方法對該問題進行了優(yōu)化；文獻[25]采用了聚類算法進行求解.除近似算法、動態(tài)規(guī)劃算法和聚類算法之外，一些性能優(yōu)異的智能算法也被引入到差異分批模式的優(yōu)化調(diào)度中，包括遺傳算法[26]、模擬退火算法[27]、蟻群算法[28-30]和微粒群算法[31]等.在作業(yè)配送方面，Sahin等[32]從經(jīng)濟分析的角度入手，提出了公路、鐵路、海上運輸?shù)确绞降膬?yōu)化組合方法；Rieksts等[33]和Janeiro等[34]將配送和庫存環(huán)節(jié)聯(lián)合起來，提出了基于庫存的配送策略以獲得最低的配送成本；Koca和Yildirim[35]考慮了一類特殊的成本結構，采用分級方法優(yōu)化配送成本，Ghoseti和Ghannadpour[36]則采用了智能優(yōu)化方法對配送成本進行優(yōu)化，獲得了較理想的實驗結果.

但上述差異分批生產(chǎn)模式的研究僅限于車間內(nèi)的優(yōu)化調(diào)度，配送研究也僅僅針對作業(yè)配送環(huán)節(jié)，并沒有立足制造企業(yè)的經(jīng)營決策高度對兩者進行協(xié)調(diào)優(yōu)化.生產(chǎn)環(huán)節(jié)的研究主要通過設計生產(chǎn)方案來獲得最低的生產(chǎn)成本，配送環(huán)節(jié)的研究主要是通過對車輛和產(chǎn)成品的獲得最低的配送成本，由于兩個環(huán)節(jié)內(nèi)的優(yōu)化目標不同，因此兩者的簡單相加必然不是制造企業(yè)的最優(yōu)策略，這兩種優(yōu)化方案對制造企業(yè)的借鑒和參考價值是有限的.尤其是在當前強調(diào)企業(yè)服務水平的環(huán)境下，應對制造企業(yè)的生產(chǎn)、庫存和配送進行集成思考和系統(tǒng)設計，從企業(yè)經(jīng)營決策的高度給出生產(chǎn)-庫存-配送的聯(lián)合調(diào)度策略，獲得作業(yè)生命周期內(nèi)從安排加工直至送達客戶的一體化運作方案，從而為制造企業(yè)提供全面、精細的運作支持.本文采用一類典型的差異分批制造模式，從制造企業(yè)的決策角度出發(fā)，設計集成化的分批、生產(chǎn)、庫存和配送方案，來優(yōu)化企業(yè)的供應點調(diào)度總成本.對制造企業(yè)來說，生產(chǎn)成本主要包括生產(chǎn)過程的能耗和操作人員工資費用，這些均取決于生產(chǎn)時間的長短；在庫存環(huán)節(jié)，成本包括庫存運行成本和人員工資等變動成本，庫存成本取決于庫存產(chǎn)品總量和庫存時間；而在配送環(huán)節(jié)，成本則主要包括運輸中的燃油費用和駕駛員工資，這些均取決于配送路線的長度和運輸?shù)拇螖?shù).首先建立基于上述聲明的生產(chǎn)-庫存-配送聯(lián)合成本的供應鏈調(diào)度模型，分析成本優(yōu)化問題的計算復雜性，然后設計有效的多項式時間算法，實現(xiàn)聯(lián)合成本的優(yōu)化，以期為制造企業(yè)的運作提供直接有效的借鑒和參考.

1　整數(shù)規(guī)劃模型與計算復雜性

定義下述決策變量

根據(jù)上述的問題描述，建立整數(shù)規(guī)劃模型如下

(1)

i=1,…,m; k=1,…,Ki

(2)

Tik=max{tj∶yjik=1}

i=1,…,m; k=1,…,Ki

(3)

Ci,h+1-Ti,h+1≥Cih

i=1,…,m; h=1,…,Ki-1

(4)

(5)

(6)

(7)

(8)

(9)

(10)

xik,yjik,wl,zjl∈{0,1}?i,j,k

(11)

模型中，KLB和LLB分別表示總批數(shù)K和總配送次數(shù)L的下界.目標函數(shù)(1)給出了供應鏈調(diào)度總成本的表達式；約束條件(2)要求同一批中的所有作業(yè)總體積不能超過設備的容量，式(3)和式(4)要求批的加工不允許中斷；式(5)和式(7)分別給出了總批數(shù)的上下界以及計算方法，其中「a?表示不小于a的最小整數(shù)；式(6)利用決策變量求出K(i)；式(8)給出了運輸中車次數(shù)量的下界，式(9)則利用決策變量wl求出車次數(shù)；式(10)要求每一車作業(yè)的總體積不能超過車輛的運輸能力；式(11)聲明模型中的決策變量均為0-1變量.

優(yōu)化目標：最小化箱子的數(shù)量；

箱子容積：1；

物品j的體積：uj/U.

而上述裝箱問題是強NP-hard問題，因此，有下述結論.

推論1Pm|U,uj,batch|1|v,V|TC是強NP-hard問題.

2　優(yōu)化算法及其時間復雜性

下面給出本文的算法A.

算法A

步驟1將所有作業(yè)按照加工時間非增的順序排序，并重新編號為1, 2,…,n，即有t1≥t2≥…≥tn.

步驟2新建一個空批B1，將作業(yè)1放入B1，并將作業(yè)1從作業(yè)集J中刪除；然后從u2開始，逐個將作業(yè)j加入B1中，如果總體積仍然不超過U，則j∈B1，若j加入后總體積大于U，則j?B1，直至所有作業(yè)均判斷完畢.若此時J≠φ，則新建空批B2，按上述方法組批.重復上述組批過程，直到J=φ為止.此時得到一個可行的批集合Φ = {B1,B2,…,BK}.

步驟3將B1,B2,…,BK按處理時間非增順序排序，從處理時間最長的批開始，逐個分別安排到M1,M2,…, Mm上加工，同時將這些批從Φ中刪除若Φ≠φ，則等到任意設備上有一批作業(yè)處理完畢時，將Φ中處理時間最長的批安排到該設備上加工，直至Φ=φ為止，此時所有批次均安排完畢.

步驟4將完工的作業(yè)按下述方法分組配送.將Bk(k= 1,…,K)中的作業(yè)按任意順序排列，得到完整的作業(yè)序列1, 2,…,n.首先安排第一輛車配送的作業(yè)集d1：將作業(yè)1放入其中，對后續(xù)的所有作業(yè)，逐個放入d1，如果總容量不超過V，則j∈d1，否則j?d1.然后按照該分組方法，依次建立d2,d3,…,dL，直至所有完工作業(yè)均安排配送為止.此時得到一個可行的配送方案{d1,d2,…,dL}.若當前批已經(jīng)完工，且無可用車輛進行配送，則將完工作業(yè)轉(zhuǎn)入庫存.

在算法A中，步驟1-步驟2完成作業(yè)的分批，步驟3完成批次的生產(chǎn)加工，步驟4則獲得完工作業(yè)的配送方法，故最終獲得的可行解π是一個集成化的方案，給出了作業(yè)分批、生產(chǎn)和配送的完整過程.下面首先分析算法A的時間性能.

定理1算法A的時間復雜度為O(mn+nlnn).

證明A的時間復雜性可以通過分析4個步驟得到.

步驟1對n個作業(yè)排序， 時間復雜性為O(n×lnn).

步驟2等價于First Fit方法[18]求解裝箱問題，裝箱問題如推論1之前內(nèi)容所示，由于First Fit算法的時間復雜度為O(nlnn)，故步驟2的時間復雜度為O(nlnn).

步驟3中，對批排序的時間復雜度為O(K×lnK)，由于K≤n，故時間復雜度小于O(nlnn)；在安排加工時，安排前m個批的時間為O(m)，后(K-m)個批中每個批搜索設備的時間為O(m)，故步驟3的時間復雜度為O(m(K-m))，顯然不超過O(mn).

步驟4中的配送方法等價于First Fit算法求解下述的裝箱問題：物品數(shù)量為n；物品j體積為uj/V；箱子的容積為1.而庫存算法由生產(chǎn)、配送方案直接產(chǎn)生，其時間復雜度為O(n)，因此，步驟4的時間復雜度為O(nlnn).

綜上，通過四個步驟的時間復雜度可知，算法A的時間復雜度為O(mn+nlnn).

證畢.

下面給出具體的算例來說明算法A的求解過程.

3　算　例

那么根據(jù)A的步驟1，將作業(yè)按照tj的非增關系排序，可獲得排序后的作業(yè)序列如表2所示，表的結構與表1相同.

表1　作業(yè)尺寸和加工時間

表2　按tj排序后的序列

根據(jù)步驟2和步驟3，可以獲得如表3所示的分批結果.第一列表示所得的批序列，這些批尚未安排到設備上，記為ei；第二列表示分配到設備上之后的加工情況，可知在設備M1上加工的批集合為{e1,e6,e9}，M2上加工的批集合為{e2,e5,e8}，M3上加工的批集合為{e3,e4, e7}；第三列為每一個批中的作業(yè)集；第四列為每個批中作業(yè)的總體積，易見b13、b22和b33對設備容量的利用率為98%，而其他6批的利用率則均為100%；第五列表示每個批次的處理時間.

于是，根據(jù)PC的計算方法可以獲得生產(chǎn)總成本如表4所示.其中第一列表示設備編號，第二列～第七列分別表示設備上的每個批次及完工時間，每臺設備上的最后一批作業(yè)的完工時間即為設備的運行時間；第八列為每臺設備的生產(chǎn)總成本.

表3　分批結果

表4　設備加工時間與生產(chǎn)成本

表5　庫存方案

綜上，算法A產(chǎn)生的聯(lián)合調(diào)度方案總成本TC=PC+IC+DC=3 163.

下面分析A的優(yōu)化性能，主要指標是A的最壞性能比.

4　優(yōu)化算法的求解性能

最壞性能比，也即多項式時間算法的近似比，用R表示，對最小化問題來說，算法得出的解與理論最優(yōu)解的比值即為最壞性能比，比值越接近1，說明算法的優(yōu)化性能越好.在分析本文算法A的求解性能時，首先從生產(chǎn)環(huán)節(jié)展開分析.

引理1在生產(chǎn)環(huán)節(jié)，算法A產(chǎn)生的總批數(shù)不超過最優(yōu)解的兩倍.

證明從A的運行過程可以看出，產(chǎn)生分批方案的是步驟1和2.從步驟1和2得知，對任意的整數(shù)g,h∈[1,K]且g≠h，有

(12)

若否，則Bg和Bh中的作業(yè)可以合并到一個批中，不符合步驟2的要求.現(xiàn)從集合{(g,h)|g+h=K+1}中選擇整數(shù)對(g,h)，根據(jù)式(12)可得

(13)

由于A產(chǎn)生的解π中，所有的作業(yè)均分到批中，因此有

(14)

而在最優(yōu)解π*中，同理有

(15)

根據(jù)式(13)-式(15)得

(16)

也即K< 2K*.

證畢.

根據(jù)引理1，為了方便后續(xù)的證明，在A產(chǎn)生的可行解π中，增加(2K*-K)個虛擬批，所謂虛擬批，即該批的處理時間和作業(yè)總體積均為零.這樣在π中，生產(chǎn)環(huán)節(jié)的總批數(shù)為2K*個.

(k-1)U<(r-1)u0≤kU

(17)

結合u0>U/2得到r-1<2k，也即

r< 2k+ 1

(18)

根據(jù)式(18)，可知在Ψ2下，作業(yè)r分配在了批B1,…,B2k中，由于Ψ1和Ψ2兩種情形下的批結構相同，因此在最壞情形Ψ1中，r分配在B1,…,B2k中.故對其他各種情形，r均能分配在前2k批中，引理2得證.

證畢.

證明先將π和π*中的并行設備問題等價的轉(zhuǎn)換為單設備制造跨度問題，即

(19)

(20)

同理，在最優(yōu)解π*中，有

(21)

Γ2k+2≤Γ2k+1≤tr

(22)

(23)

根據(jù)式(22)和式(23)得到

(24)

(25)

(26)

根據(jù)式(26)， 結合式(19)～式(21)知， 定理1得證.

證畢.

引理3在配送環(huán)節(jié)，算法A產(chǎn)生的配送成本L< 2L*.

證明算法A中，配送方案的產(chǎn)生在步驟4中.分析步驟4知，A產(chǎn)生的可行車次集{d1,…, dL}滿足

?x≠y and x,y=1,…,L

(27)

從下述集合中選取整數(shù)對(x,y)∶{(x,y)|x+y=L+1}，可得

(28)

而最優(yōu)解π*中，顯然有

(29)

證畢.

(30)

同時，在庫存運行時間方面，有

2IS*=4τL*>2τL=IS

(31)

證畢.

以上對算法的生產(chǎn)環(huán)節(jié)和配送環(huán)節(jié)均展開了分析，下面給出算法的求解性能.

定理2在求解Pm|U,uj,batch|1|v,V|TC問題時，算法A的最壞性能比不大于2.

證明根據(jù)定理1和引理3、引理4，得到A的性能比如下

=2

定理2得證.

證畢.

5　結束語

本文考慮了制造企業(yè)的一類供應鏈調(diào)度問題，在生產(chǎn)環(huán)節(jié)，制造企業(yè)的生產(chǎn)設備為多臺并行批處理設備，每臺設備有固定的容量，而加工的作業(yè)具有任意的尺寸和處理時間，加工時分批進行，每一批作業(yè)的加工不允許中斷；在配送環(huán)節(jié)中作業(yè)的配送由企業(yè)的自有車輛進行運送，車輛具有相同的運輸能力；作業(yè)加工完畢后，若不能立即配送，則轉(zhuǎn)入產(chǎn)品庫存.建立了生產(chǎn)-庫存-配送聯(lián)合成本優(yōu)化問題的數(shù)學模型，證明聯(lián)合成本的最小化問題是強NP-hard問題，然后提出了一類O(mn+nlnn)時間的近似算法，最壞性能比不大于2.

在后續(xù)研究中，本文的供應鏈調(diào)度問題可以根據(jù)實際生產(chǎn)擴展為其他設備模型，如流水作業(yè)模型、車間作業(yè)模型等，由于單設備的供應鏈調(diào)度問題已經(jīng)是強NP-hard問題，因此流水作業(yè)、車間作業(yè)模型下的供應鏈調(diào)度問題是強NP-hard問題，對優(yōu)化算法的研究應集中在近似算法和智能算法兩個方面.另外，本文考慮的聯(lián)合成本優(yōu)化問題涉及到生產(chǎn)、庫存和配送環(huán)節(jié)，后續(xù)研究可以擴展到采購環(huán)節(jié)，將采購、生產(chǎn)、庫存和配送等環(huán)節(jié)綜合考慮，進行系統(tǒng)化建模，并設計有效的優(yōu)化算法.

[1]Hall N G, Potts C N. Supply chain scheduling: Batching and delivery[J]. Operations Research, 2003, 51(4): 566-584.

[2]Chen Z L, Hall N G. Supply chain scheduling: Conflict and cooperation in assembly systems[J]. Operations Research, 2007, 55: 1072-1089.

[3]Agnetis A, Hall N G, Pacciarelli D. Supply chain scheduling: Sequence coordination[J]. Discrete Applied Mathematics, 2006, 154(15): 2044-2063.

[4]Torabi S A, Ghomi S M T, Karimi B. A hybrid genetic algorithm for the finite horizon economic lot and delivery scheduling in supply chains[J]. European Journal of Operational Research, 2006, 173(1): 173-189.

[5]Chen Z L, Vairaktarakis G L. Integrated scheduling of production and distribution operations[J]. Management Science, 2005, 51(4): 614-628.

[6]Selvarajah E, Steiner G. Batch scheduling in a two-level supply chain： A focus on the supplier[J]. European Journal of Operational Research, 2006, 173(1): 226-240.

[7]Averbakh I, Xue Z. On-line supply chain scheduling problems with preemption[J]. European Journal of Operational Research, 2007, 181(1): 500-504.

[8]Naso D, Surico M, Turchaiano B, et al. Genetic algorithms for supply-chain scheduling: A case study in the distribution of ready-mixed concrete[J]. European Journal of Operational Research, 2007, 177(3): 2069-2099.

[9]Zegordi S H, Abadi I N K, Nia M A B. A novel genetic algorithm for solving production and transportation scheduling in a two-stage supply chain[J]. Compters & Industrial Engineering, 2007, 58(3): 373-381.

[10]Chen Z L, Pundoor G. Order assignment and scheduling in a supply chain[J]. Operations Research, 2006, 54(3): 555-572.

[11]Hall N G, Liu Z. Capacity allocation in supply chains[J]. Operations Research, 2010, 58(6): 1711-1725.

[12]Selvarajah E, Steiner G. Approximation algorithms for the supplier’s supply chain scheduling problem to minimize delivery and inventory holding costs[J]. Operations Research, 2009, 57(2): 426-438.

[13]Sawik T. Coordinated supply chain scheduling[J]. International Journal of Production Economics, 2009, 120(2): 437-451.

[14]Yimer A D, Demirli K. A genetic approach to two-phase optimization of dynamic supply chain scheduling[J]. Computers & Industrial Engineering, 2010, 58(3): 411-422.

[15]Yeung W K, Choi T M, Cheng T C E. Supply chain scheduling and coordination with dual delivery models and inventory storage cost[J]. International Journal of Production Economics, 2011, 132(2): 223-229.

[16]Osman H, Demirli K. Economic lot and delivery scheduling problems for multi-stage supply chains[J]. International Journal of Production Economics, 2012, 136(2): 275-286.

[17]Pinedo M. Scheduling: Theory, Algorithms and Systems[M]. 2nd ed., New Jersey: Prentice-Hall, 2002.

[18]Uzsoy R. Scheduling a single batch-processing machine with arbitrary job sizes[J]. International Journal of Production Research, 1994, 32(7): 1615-1635.

[19]Zhang G, Cai X, Lee C Y, et al. Minimizing makespan on a single batch-processing machine with nonidentical job sizes[J]. Naval Research Lnistics, 2001, 48(3): 226-240.

[20]Tang L X, Gong Hua. A hybrid two-stage transportation and batch scheduling problem[J]. Applied Mathematical Modelling, 2008, 32(12): 2467-2479.

[21]程八一， 胡笑旋. 差異作業(yè)批調(diào)度的流水車間問題及近似算法[J]. 系統(tǒng)工程學報， 2011, 26(3): 393-399.

Cheng Bayi, Hu Xiaoxuan. Approximation algorithm for scheduling batch processing machines with non-identical job sizes in flow shop[J]. Journal of Systems Engineering, 2011, 26(3): 393-399.(in Chinese)

[22]Tang L X, Liu P. Two-machine flowshop scheduling problems involving a batching machine with transportation or deterioration consideration[J]. Applied Mathematical Modelling, 2009, 33(2): 1187-1199.

[23]Tang L X, Liu P. Minimizing makespan in a two-machine flowshop scheduling with batching and release time[J]. Mathematical and Computer Modelling, 2009, 49(5/6): 1071-1077.

[24]馮大光, 唐立新. 一類新型批處理機調(diào)度問題的理論分析[J]. 管理科學學報, 2012, 15(6): 33-48.

Feng Daguang, Tang Lixin. The oretical analysis of scheduling of a new batching machine[J]. Journal of Management Sciences in China, 2012, 15(6): 33-48. (in Chinese)

[25]杜冰, 陳華平, 楊勃, 等. 聚類視角下的差異工件平行機批調(diào)度問題[J]. 管理科學學報, 2011, 14(12): 27-37.

Du Bing, Chen Huaping, Yang Bo, et al. Scheduling parallel batching machines with non-identical job sizes from a clustering perspective[J]. Journal of Management Sciences in China, 2011, 14(12): 27-37. (in Chinese)

[26]Damodaran P, Manjeshwar P K, Srihari K. Minimizing makespan on a batch-processing machine with arbitrary job sizes using genetic algorithm[J]. International Journal of Production Economics, 2006, 103(2): 882 -891.

[27]Melouk S, Demodaran P, Chang P Y. Minimizing makespan for single machine batch-processing with arbitrary job sizes using simulated annealing[J]. International Journal of Production Economics, 2004, 87(2): 141-147.

[28]Cheng B Y, Li K, Chen B. Scheduling a single batch-processing machine with arbitrary job sizes in fuzzy environment using an improved ant colony optimization[J]. Journal of Manufacturing Systems, 2010, 29(1): 29-34.

[29]Cheng B Y, Wang Q, Yang S L, et al. An improved ant colony optimization for scheduling identical parallel batching machines with arbitrary job sizes[J]. Applied Soft Computing, 2013, 13(2): 765-772.

[30]王栓獅, 陳華平, 程八一, 等. 一種差異工件單機批調(diào)度問題的蟻群優(yōu)化算法[J]. 管理科學學報, 2009, 12(6): 72-82.

Wang Shuanshi, Chen Huaping, Cheng Bayi, et al. Minimizing makespan on a single batch processing machine with non-identical job sizes using ant colony optimization[J]. Journal of Management Sciences in China, 2009, 12(6): 72-82. (in Chinese)

[31]程八一, 陳華平, 王栓獅. 基于微粒群算法的單機不同尺寸工件批調(diào)度問題求解[J]. 中國管理科學, 2008, 16(3): 84-88.

Cheng Bayi, Chen Huaping, Wang Shuanshi. Scheduling a single batch-processing machine with non-identical job sizes based on particle swarm optimization[J]. Chinese Journal of Management Science, 2008, 16(3): 84-88. (in Chinese)

[32]Sahin B, Yilmaz H, Ust Y, et al. An approach for analyzing transportation costs and a case study[J]. European Journal of Operational Research, 2009, 193(1): 1-11.

[33]Rieksts B Q, Ventura J A. Two-stage inventory models with a bi-modal transportation cost[J]. Computers & Operations Research, 2010, 37(1), 20-31.

[34]Janeiro M G, Jurado I G, Meca A, et al. A new cost allocation rule for inventory transportation systems[J]. Operations Research Letters, 2013, 41(5): 449-453.

[35]Koca E, Yildirim E A. A hierarchical solution approach for a multicommodity distribution problem under a special cost structure[J]. Computers & Operations Research, 2012, 39(11): 2612-2624.

[36]Ghoseti K, Ghannadpour S F. Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm[J]. Applied Soft Computing, 2010, 10(4): 1096-1107.

[37]Chen Z L. Integrated production and outbound distribution scheduling: Review and extensions[J]. Operations Research, 2010, 58(1): 130-148.

Algorithm for minimizing joint cost for manufacturers with batching machines and arbitrary-size jobs

CHENG Ba-yi1, 2, HUANG Xiao-man1, 2, YANG Yan-yan1, 2, HU Xiao-xuan1, 2

1. School of Management, Hefei University of Technolny, Hefei 230009, China；2. Key Laboratory of Process Optimization and Intelligent Decision-making, Hefei 230009, China

A class of problems for manufacturers are proposed to minimize joint cost. Production and outbound distribution are combined to achieve a joint scheduling in supply chain. In the production process, the manufacturers have identical parallel batching machines to process arbitrary-size jobs. The machines have a fixed capacity in size and the total size of jobs in a batch cannot exceed the machine capacity. In the distribution process, the manufacturers deliver the products using their own vehicles and the vehicles have identical transport capacities. If there are no available vehicles to deliver the products, they should be put in inventory. The total cost consists of the production cost, the distribution cost and inventory cost. An integer programming model of the problem is presented and the problem under investigation is shown to be NP-hard in the strong sense. Then a polynomial time algorithm is provided. The time complexity and performance guarantee of the proposed algorithm are analyzed.

supply chain scheduling; joint cost; arbitrary-size jobs; approximation algorithm

2013-06-04；

2015-10-30.

國家自然科學基金資助項目(71202048; 71471052; 71521001); 教育部人文社會科學基金資助項目(13YJC630051).

程八一(1981—)， 男， 安徽安慶人， 博士， 副教授. Email： bycheng@mail.ustc.edu.cn

TP301

A

1007-9807(2016)08-0102-11