李 巖，趙文卓

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

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

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

1 符號和公式

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

dt:周期t的需求

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

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

It:周期t結束后已有的存儲量，It≥0.

ht:周期t放置一個單元的費用

P(xt):周期t補給xt個單元的費用

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

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

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

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

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

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

3 多項式算法

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

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

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

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

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

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

在周期MR和FTL這間可能有一個不規(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)時間內(nèi)計算 I(i，j)，I′(i，j)，其中1 ≤i≤j≤T .

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

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

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

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

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

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

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

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

4 問題舉例

5 結 論

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

［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).