李 巖，趙文卓

(1.吉林化工學(xué)院理學(xué)院，吉林 吉林132022;2.吉林化工學(xué)院工會(huì)，吉林吉林132022)

及時(shí)配送的概念在近幾年中越來越流行［1-2］.但是，及時(shí)配送的執(zhí)行要依賴于交易力和供求關(guān)系.例如汽車或電腦裝配廠，大多數(shù)的提供者不得不把原料運(yùn)送至第三方的倉庫，然后再從第三方的倉庫以及時(shí)配送的方式運(yùn)送至生產(chǎn)商進(jìn)行裝配.另一方面，由于購買者缺乏議價(jià)能力而使及時(shí)配送不能夠進(jìn)行.例如購買者要從汽車廠購買引擎，購買者想要尋找一個(gè)及時(shí)配送的提供商，這意味著按需送貨.然而，生產(chǎn)商規(guī)定了一個(gè)最小的配送數(shù)量，記為R.另一方面，當(dāng)?shù)氐牧闶凵坛兄Z以按需配送的形式提供購買者引擎，但是需要較高的價(jià)格.目前的問題購買者是繼續(xù)從生產(chǎn)商那里購買引擎還是轉(zhuǎn)向當(dāng)?shù)氐牧闶凵?

Wagner和Whitin［3-7］利用動(dòng)態(tài)規(guī)劃算法對整批運(yùn)送問題做了大量的工作.本文尋找了一個(gè)解析的方法［9］幫助購買者以最小的成本選擇提供者.如果購買者從零售商手中購買產(chǎn)品，由于是及時(shí)配送，所以成本很容易計(jì)算［11-13］.如果購買者從生產(chǎn)商手中購買產(chǎn)品，成本就為存儲(chǔ)費(fèi)用和運(yùn)輸費(fèi)用之和，我們設(shè)計(jì)了動(dòng)態(tài)批量模型來計(jì)算逐步增加到最小數(shù)量約束的貨物費(fèi)用.針對問題的幾種最優(yōu)性，我們設(shè)計(jì)了多項(xiàng)式最優(yōu)算法.

1 符號和公式

定義T為一個(gè)計(jì)劃周期的長度.定義t為一個(gè)計(jì)劃周期長度，t=1，…，T，定義符號如下:

dt:周期t的需求

xt:周期t的補(bǔ)充數(shù)量

R:每一次定單的最小補(bǔ)給數(shù)量

It:周期t結(jié)束后已有的存儲(chǔ)量，It≥0.

ht:周期t放置一個(gè)單元的費(fèi)用

P(xt):周期t補(bǔ)給xt個(gè)單元的費(fèi)用

其中n為確定的整數(shù)，S為每次運(yùn)輸?shù)墓潭ㄙM(fèi)用，W是一次貨物的容量，A是運(yùn)輸貨物的費(fèi)用.Min∑(P(xt)+htIt)

2 最優(yōu)性質(zhì)

定義:如果It=0，則稱周期t為新生點(diǎn)，如果xt＞0，則稱t為補(bǔ)給周期.補(bǔ)給周期稱為整車貨(FTL)周期，如果xt=nW，t稱為最小需求周期，如果xt=R，t稱為不規(guī)則補(bǔ)給周期，如果xt＞R且t不是FTL周期.

性質(zhì)1 存在一個(gè)最優(yōu)解，如果l-1和m是兩個(gè)連續(xù)的再生點(diǎn)，并且在l和m之間至多存在一個(gè)不規(guī)則的補(bǔ)給周期.

性質(zhì)2 存在一個(gè)最優(yōu)解，如果l-1和m是兩個(gè)連續(xù)的再生點(diǎn)，并且在l和m之間存在一個(gè)不規(guī)則的補(bǔ)給周期t，則在t之前必存在一個(gè)最小補(bǔ)給周期，并且這個(gè)補(bǔ)給周期是整車貨的周期.

性質(zhì)3 存在一個(gè)最優(yōu)解，如果l-1和m是兩個(gè)連續(xù)的再生點(diǎn)，并且在l-1和m之間沒有不規(guī)則的補(bǔ)給周期，則對任意兩個(gè)連續(xù)的補(bǔ)給周期s，t，其中l(wèi)-1＜s＜t≤m，若s是FTL，則t必為FTL周期.

3 多項(xiàng)式算法

令C(i，j)為從周期i到周期j中間沒有新生點(diǎn)的費(fèi)用，F(xiàn)(j)為從周期1到周期j的總的費(fèi)用.得到以下動(dòng)態(tài)規(guī)劃算法:

F(0)=0 對于 j=1，…，T，

F(j)=min{F(i-1)+C(i，j):1 ≤i≤j}

問題歸結(jié)為尋找最小的 C(i，j)，1 ≤i≤j≤T .由于當(dāng) d(i，j)＜ R，C(i，j)= ∞，則只需考慮 d(i，j)≥ R的情況.根據(jù)性質(zhì)1-3，只需考慮MR和FTL周期的情況.另外，我們可以得到以下性質(zhì).

性質(zhì)4對于(i，j)問題的最優(yōu)解問題，對于任意一個(gè)補(bǔ)給周期u，必滿足Iu-1＜du.

性質(zhì)5對于FTL周期的(i，j)問題的最優(yōu)算法，必滿足Iv-1＜min{dv，mW}，其中m=「R/W.

在周期MR和FTL這間可能有一個(gè)不規(guī)則的周期，對于i=1，2，…，T;j=T，T-1，…，1，定義

I(i，u-1)= 「d(i，u-1)/RR-d(i，u-1)其中 1 ≤i≤u ，

I′(v-1，j)=d(v，j)-d(v，j)/W?W 其中 1 ≤v≤j.

根據(jù)性質(zhì) 4，5，我們可以在 o(T2)時(shí)間內(nèi)計(jì)算 I(i，j)，I′(i，j)，其中1 ≤i≤j≤T .

尋找R(i，T)的算法:

Step0:設(shè) R(i，T)={i}，v=i+1 .

Step1:若 I(i，u-1)=0 或 I(i，u-1)+R ＞ d(u，T)，則停止.否則，轉(zhuǎn)到 Step2.

Step2:若 I(i，u-1)＜ du，則令R(i，T)=R(i，T)∪{u}，并轉(zhuǎn)到Step3.否則，令u=u+1 并轉(zhuǎn)到Step1.

Step3:若 I(i，u-1)+R ≤du，則停止.否則，令 u=u+1 并轉(zhuǎn)到 Step1.

定義S(i，u)是從周期i到周期u-1，存貨從0到I(i，u-1)時(shí)應(yīng)用MR供給的最小的費(fèi)用，有S(i，i)=0，同理定義T(v，j)′是從周期v到周期j，存貨從I′(v-1，j)到0時(shí)應(yīng)用FTL供給的最小的費(fèi)用.對于固定的 i和 j，定義 q(i，u)→(v，j)′是從周期 u 到周期 v-1，存貨從 I(i，u-1)到 I′(v-1，j)時(shí)的最小的費(fèi)用.則有

T(v，j)′的計(jì)算復(fù)雜性為O(T3).

因此，C(i，j)的計(jì)算復(fù)雜性為O(T4+T3+T2)=O(T4).

4 問題舉例

5 結(jié) 論

成本、速度和一致性是影響運(yùn)輸合理化的至關(guān)重要的因素.具體的運(yùn)輸作業(yè)涉及到運(yùn)輸方式的選擇和運(yùn)輸路線的選擇及計(jì)劃運(yùn)輸設(shè)備的使用時(shí)間(本文主要指倉庫).本文以這三個(gè)因素為標(biāo)準(zhǔn)，設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法幫助購買者合理選擇提供者和運(yùn)輸方式使總成本達(dá)到最小.例如上面問題舉例中所指，如果購買者一次購買產(chǎn)品的數(shù)量是15，批量運(yùn)輸?shù)目傎M(fèi)用130，則購買者可以根據(jù)零售商提供的報(bào)價(jià)合理選擇提供商而使自己的利益最大化.

［1］ R.W.Hall，Zero Inventories，Homewood，IL，Dow Jones Irwin.1983.

［2］ R.G.Moras，M.R.Jalali，R.A.Durek，A categorized survey of the JIT literature［J］.Prod.Planning Control，1992(2):322-334.

［3］ H.M.Wagner，T.M.Whitin.Dynamic version of the economic lot-size model［J］.Management Science 5，1958:89-96.

［4］ Z.M.Cheng，D.H.Xu.Parallel Machine Scheduling Problem With Preemptions and Release Times to Minimize Total Completion Time［J］.2007(16):77-84.

［5］ N.G.Hall，M.A.Lesaoana，C.N.Potts.Scheduling with fixed delivery dates［J］.Operations Research，2001(49):134-144.

［6］ H.Matsuo.The weighted total tardiness problem with fixed shipping times and overtime utilization［J］.Operations Research，1988，36:293-307.

［7］ C.L.Li，G.Vairaktarakis，C.Y.Lee，Machine scheduling with deliveries to multiple customer locations，European Journal of Operational Research，2005，164:39-51.

［8］ K.R.Baker..AComparetivesurv，y of Flowshop Algorithm［J］.Operations Research，1975，23:62-73.

［9］ B.Chen，C.N.potts，G.J.Woegiger.1998.A Review of Machine Scheduling:Complexity，Algorithms，and Approximability［J］.Operations Research Letters，1997，21:69-76.

［10］ J.Bruno，E.G.Coffman，JR.and R.Sethi.Scheduling Independent Tasks to Reduce Mean Finishing Time［J］.Commun.ACM，1974，17:382-387.

［11］ Rawls C.G.，Turnquist M.A.pre-positioning of Emergency Supplies for Disaster Response［J］.transportation Research，2010，44(4):521-534.

［12］ Widener M.J.，Horner M.A hierarchical Approach to Modeling hurricane Disaster Relief Goods Distribution［J］.Journal of Transport Geography，2011，19(4):821-828.

［13］ Afshar A.，Haghani A.Modeling Integrated Supply Chain Logistics in Real-time Large-scale Disaster Relief Operations［J］.Socio-Economic Planning Sciences，2012，46(4):327-338.

［14］ Rath S.，Gutjahr W.J.A Math-heuristic for the Warehouse Location-routing Problem in Disaster Relief［J］.Computers ＆Operations Research，InPress，Corrected Proof，Available online，2011(7).