實(shí)現(xiàn)供貨能力承諾的企業(yè)高級計(jì)劃系統(tǒng)研究

曾小青， 劉 寧， 肖海燕

(長沙理工大學(xué) 經(jīng)濟(jì)與管理學(xué)院，湖南 長沙 410076)

自20世紀(jì)90年代以來，以制造業(yè)為主的中國經(jīng)濟(jì)得到了長足發(fā)展，中國在全球制造業(yè)中比重從3%提高到2007年的13.2%[1]。目前，中國的制造業(yè)在全球占有重要地位，位居美國之后，已經(jīng)成為全球第二大制造業(yè)國家。然而，中國制造業(yè)生產(chǎn)技術(shù)特別是關(guān)鍵技術(shù)主要依靠國外的狀況仍未從根本上改變。特別是在由美國金融危機(jī)引發(fā)的全球經(jīng)濟(jì)放緩的大背景下，我國制造業(yè)的外部需求會(huì)有所減弱，這將給我國制造企業(yè)帶來挑戰(zhàn)。但與此同時(shí)，“次貸危機(jī)”與西方國家經(jīng)濟(jì)形勢的持續(xù)惡化，發(fā)達(dá)國家的制造業(yè)遭受巨大打擊，迫于利潤與生存的壓力，其制造企業(yè)將向發(fā)國中國家加速轉(zhuǎn)移，從而會(huì)促進(jìn)我國企業(yè)的產(chǎn)業(yè)結(jié)構(gòu)升級。因此，中國制造業(yè)應(yīng)妥善利用國際國內(nèi)兩個(gè)市場，加強(qiáng)產(chǎn)業(yè)鏈上下游企業(yè)的協(xié)作，在技術(shù)、管理和信息化建設(shè)方面進(jìn)行升級，以應(yīng)對這種嚴(yán)峻又復(fù)雜的局面。

一、供貨能力承諾(ATP)與高級計(jì)劃系統(tǒng)(APS)

(一)實(shí)現(xiàn)ATP需要強(qiáng)大的計(jì)劃系統(tǒng)

企業(yè)的主要目的是獲取利潤，而利潤來源于產(chǎn)品(或服務(wù))的銷售。對制造企業(yè)而言，在爭取盡可能多的訂單的同時(shí)，還得按約定交貨，履行訂單[2]。無論其最終產(chǎn)品具體表現(xiàn)為何種形式，其競爭優(yōu)勢無外乎來自兩種能力：一是及時(shí)交付產(chǎn)品的能力；二是對整個(gè)經(jīng)營范圍內(nèi)的供貨情況進(jìn)行實(shí)時(shí)查詢的能力，從而向顧客提供最快捷、最準(zhǔn)確的信息。這兩種能力可歸結(jié)為企業(yè)對供貨能力承諾(ATP：Available to Promise)的實(shí)現(xiàn)程度。ATP指在整個(gè)供應(yīng)鏈中對所訂購產(chǎn)品進(jìn)行部件和資源的供貨能力核查，基于當(dāng)前和預(yù)定義的計(jì)劃供給對供貨量作出承諾的能力[3]。ATP在供應(yīng)鏈的每一階段，從供應(yīng)商開始，經(jīng)過內(nèi)部設(shè)施，直到客戶，考慮各類提前期，從而可為客戶提供精確的、值得信賴的交貨承諾。

實(shí)現(xiàn)供貨能力承諾的關(guān)鍵是企業(yè)要具備強(qiáng)大的生產(chǎn)計(jì)劃系統(tǒng)[3]。一直以來，企業(yè)廣泛采用企業(yè)資源計(jì)劃ERP系統(tǒng)對企業(yè)運(yùn)作進(jìn)行管理，并曾創(chuàng)造了ERP實(shí)踐的輝煌時(shí)期[4]。然而ERP主要是針對企業(yè)內(nèi)部資源的管理，它的核心邏輯基于無限能力假設(shè)和固定提前期，缺乏優(yōu)化功能。同時(shí)它不具備協(xié)調(diào)多個(gè)企業(yè)資源的能力[5]。為尋求克服ERP的不足，在上個(gè)世紀(jì)90年代中期，出現(xiàn)了高級計(jì)劃與排程系統(tǒng)(Advanced Planning and Scheduling，又稱高級計(jì)劃系統(tǒng)或高級計(jì)劃與排產(chǎn)系統(tǒng))[6]。APS是一種基于供應(yīng)鏈管理和約束理論的先進(jìn)計(jì)劃與排程系統(tǒng)，包含了大量數(shù)學(xué)模型、優(yōu)化及模擬技術(shù)[7～10]。企業(yè)對APS系統(tǒng)的需求日漸增長[11]。

(二)APS是ERP計(jì)劃系統(tǒng)的補(bǔ)充和優(yōu)化

APS能及時(shí)響應(yīng)客戶要求，快速同步計(jì)劃，提供精確的交貨日期，減少在制品與成品庫存，并發(fā)考慮供應(yīng)鏈的所有約束，自動(dòng)識別潛在瓶頸，提高資源利用率，從而改善企業(yè)的管理水平。

但是APS系統(tǒng)不能夠獨(dú)立的運(yùn)行，它需要大量基礎(chǔ)數(shù)據(jù)的支撐才能良好的運(yùn)行。一方面，APS的需求計(jì)劃從ERP的定單輸入中獲得，然后再結(jié)合外部數(shù)據(jù)中預(yù)測需求，通過APS計(jì)劃模塊中的約束條件，得到指導(dǎo)MRP的約束主生產(chǎn)計(jì)劃，傳回到ERP的主生產(chǎn)計(jì)劃模塊。因此，APS不能取代ERP系統(tǒng)，ERP系統(tǒng)采用的計(jì)劃模型又不能滿足目前的需要，ERP的計(jì)劃模型的改變同時(shí)將影響到整個(gè)系統(tǒng)結(jié)構(gòu)的變化。因此，用APS來優(yōu)化ERP生產(chǎn)計(jì)劃系統(tǒng)，既可以強(qiáng)化ERP的計(jì)劃功能，同時(shí)又不必影響到ERP其他成熟的商業(yè)流程。

然而，由于APS的計(jì)算復(fù)雜性和信息系統(tǒng)的處理能力，目前APS并未得到廣泛應(yīng)用[12]。本文提出了一個(gè)實(shí)現(xiàn)供貨能力承諾的企業(yè)高級生產(chǎn)計(jì)劃模型，并給出求解該模型的啟發(fā)式算法，并通過在某公司的應(yīng)用實(shí)例驗(yàn)證了該算法的有效性，力圖豐富APS的現(xiàn)有研究成果。

二、實(shí)現(xiàn)供貨能力承諾的企業(yè)高級生產(chǎn)計(jì)劃優(yōu)化方法

(一)問題的描述及模型建立

對實(shí)現(xiàn)供貨能力承諾的企業(yè)生產(chǎn)計(jì)劃問題經(jīng)過簡化、提煉后可描述為如下數(shù)學(xué)問題。

制訂生產(chǎn)計(jì)劃主要考慮關(guān)鍵工序的生產(chǎn)能力。對于關(guān)鍵工序，假設(shè)有n批工件p1,p2,…,pn(對應(yīng)著n個(gè)訂單)，在某一時(shí)間段(計(jì)劃周期階段)需經(jīng)過m臺并行設(shè)備M1,M2,…Mn加工處理。問如何選擇工件加工的批數(shù)、每批工件的數(shù)量，使得在滿足交貨期的同時(shí)，設(shè)備能力與負(fù)荷平衡。

對這個(gè)問題，可建立如下優(yōu)化模型：

(1)符號定義：

假設(shè)計(jì)劃周期為K，計(jì)劃周期中的每個(gè)時(shí)段為k(k=1,2,…K)；第k時(shí)段第j臺設(shè)備上加工的第i批工件的數(shù)量為xijk；tij為第i批工件在第j臺設(shè)備上的負(fù)荷(i=1,2,…n,j=1,2,…m)；第j臺設(shè)備提供的正常處理能力是NCj，最大能力為MCj；在第k時(shí)段第j臺設(shè)備上工件的轉(zhuǎn)換次數(shù)(比如涉及到換模)為CCjk；每次轉(zhuǎn)換的時(shí)間為τ；設(shè)備在不同批次工件之間轉(zhuǎn)換時(shí)，單次轉(zhuǎn)換的損失為α(出于簡化，這里假定每次轉(zhuǎn)換時(shí)間和損失與具體加工的工件批次無關(guān)，大多數(shù)情況下這與生產(chǎn)實(shí)際是貼近的)；第i批工件交期為Di；第i批工件的單件延期懲罰為βi；計(jì)劃周期內(nèi)第i批工件的訂單數(shù)量為pi，第i批工件是否延期表示為Li，如果不能如期完工，Li為1，否則為0。

(2)優(yōu)化目標(biāo)：

求一個(gè)工件加工方案(即求每個(gè)時(shí)段內(nèi)每臺設(shè)備加工的工件數(shù)xijk)，滿足：

(1)工件的延誤交貨懲罰和轉(zhuǎn)換的損失盡可能小；

(2)在計(jì)劃周期內(nèi)，系統(tǒng)中每臺設(shè)備負(fù)荷之差的絕對值總和要盡可能小。

目標(biāo)函數(shù)為：

①按時(shí)交貨目標(biāo)：

(1)

②能力平衡目標(biāo)：

(2)

約束條件為：

(1)每臺設(shè)備的能力約束：

(3)

(2)工件數(shù)量約束：

(4)

(3)轉(zhuǎn)換次數(shù)：

(5)

(4)第i批工件是否延期：

MD=min(K,Di)

(6)

(5)其它約束：

xijk≥0,且xijk∈Z+;tij>0;i=1,…,n;

j=1,…,m;k=1,…,K.

(二)模型求解的啟發(fā)式算法

上述模型足夠簡化，且具有較好的普遍性和實(shí)用性。作為一個(gè)多目標(biāo)的整數(shù)規(guī)劃模型，可用運(yùn)籌學(xué)軟件來求解。然而，它的求解容易受組合優(yōu)化問題規(guī)模的限制，當(dāng)問題規(guī)模很大的時(shí)候，求最優(yōu)解是困難的。因此在實(shí)際應(yīng)用中通常是尋求效率高、優(yōu)化效果較好的啟發(fā)式算法。下面給出求解該模型的一種啟發(fā)式新算法：

通過分析認(rèn)為，目標(biāo)①中的式(1)作為第一優(yōu)先級，目標(biāo)②的式(2)為次優(yōu)先級的，因此有啟發(fā)式規(guī)則：先保證交期，再考慮負(fù)荷，在滿足交期的條件下，盡量均衡負(fù)荷；在不能滿足交期時(shí)，應(yīng)盡可能將該工件的加工任務(wù)安排得靠近Di。

出于算法描述的需要，另外定義幾個(gè)臨時(shí)變量：

第j臺設(shè)備在第k時(shí)間段已有負(fù)荷為：MLjk，初值為0；

第j臺設(shè)備在第k時(shí)間段的空余能力為：FLjk初值為NCjk；

當(dāng)前工件尚未安排的加工任務(wù)：LT；

Step1 TaskList={p1,p2,…,pn}

Step2i= {i|Di=min(Di0),i0=1,2,…,n}

LT=pi；

forj=1 tom

fork=1 toDi

ifMLjk=0 andLT>0

xijk= min(LT,NCj)

MLjk=MLjk+xijk

FLjk=NCj-MLjk

LT=LT-xijk

ifLT=0 then GOTO Step7

end if

nextk

nextj

end if

Step4 DO

(j,k)= {(j,k) |FLjk=max(FLj0k0),j0=1,2,…,m,k0=1,2,…,Di}

xijk= min(LT,FLjk)

MLjk=MLjk+xijk

FLjk=NCj-MLjk

LT=LT-xijk

ifLT=0 then GOTO Step7

GOTO step3

LOOP

forj=1 tom

fork=1 toDi

xijk=FLjk

MLjk=NCj

FLjk= 0

LT=LT-xijk

nextk

nextj

fork=Di+1 toK

j= {j|FLjk=max(FLj0k),j0=1,2,…,m}

xijk= min(LT,FLjk)

MLjk=MLjk+xijk

FLjk=NCj-MLjk

LT=LT-xijk

ifLT=0 then GOTO Step7

nextk

Step6 MessageBox(“Can not fulfill the order”)

Option=Prompt(“partly arrange or cancel?”,1,2)

if Option=2 then

forj=1 tom

fork=1 toK

MLjk=MLjk-xijk

FLjk=NCj-MLjk

xijk= 0

nextk

nextj

end if

Step7 ifN(TaskList)>0 then GOTO Step2

Step8 End. Each value ofxijkis set.

(三)應(yīng)用實(shí)例

表1 實(shí)現(xiàn)供貨能力承諾的某企業(yè)周生產(chǎn)計(jì)劃

其它生產(chǎn)線的周生產(chǎn)計(jì)劃的制定方法類似。圖1給出了該企業(yè)各生產(chǎn)線的周生產(chǎn)計(jì)劃計(jì)算結(jié)果。該企業(yè)的生產(chǎn)負(fù)荷與生產(chǎn)能力的比較如圖2所示。由圖2可知，各生產(chǎn)線的生產(chǎn)負(fù)荷均未超出其最大能力。生產(chǎn)負(fù)荷波動(dòng)情況這是由每條生產(chǎn)線在該計(jì)劃周期內(nèi)的訂單數(shù)量和交期決定的。從圖1中可以看出，a生產(chǎn)線的均衡性比較好(為97.29%)。

圖1 各生產(chǎn)線的周生產(chǎn)計(jì)劃計(jì)算結(jié)果

圖2 各生產(chǎn)線的生產(chǎn)負(fù)荷與生產(chǎn)能力比較

(四)算法分析

(1)計(jì)算復(fù)雜性

在分析計(jì)算復(fù)雜性時(shí)，只考慮其最高階的變化，因?yàn)檫@是影響復(fù)雜性函數(shù)取值大小的主要因素。在該算法中，復(fù)雜性主要集中在步驟3和步驟5，其復(fù)雜性最大為0(nmk)(為時(shí)間多項(xiàng)式算法)。影響步驟3和步驟5復(fù)雜性的因素主要有3個(gè)：訂單批數(shù)n，并行設(shè)備數(shù)m以及計(jì)劃周期k，此外還受交貨期Di的影響。如果交貨期Di

(2)算法有效性

此處算法有效性是指計(jì)劃問題求解過程的有效性，即該過程是否可以保證至少得到一個(gè)計(jì)劃方案。

算法的有效性受訂單數(shù)量、設(shè)備的加工能力以及訂單要求的交貨期的限制。如果設(shè)備的能力充足，并且交貨期寬松，則算法能保證獲得該計(jì)劃問題的解。否則，表明不能在該計(jì)劃周期內(nèi)完成加工任務(wù)，能力不足，計(jì)劃失敗。

三、結(jié)論

企業(yè)廣泛采用企業(yè)資源計(jì)劃ERP系統(tǒng)對企業(yè)運(yùn)作進(jìn)行管理，高級計(jì)劃系統(tǒng)APS是ERP的重要補(bǔ)充。而企業(yè)制定生產(chǎn)計(jì)劃的需求信息和資源信息來自多方面，計(jì)劃的不確定性因素多，要實(shí)現(xiàn)供貨能力承諾，難度較大，需綜合考慮多種約束，綜合運(yùn)用多種優(yōu)化算法，進(jìn)行優(yōu)化求解。本文提出了一個(gè)實(shí)現(xiàn)供貨能力承諾的企業(yè)高級生產(chǎn)計(jì)劃模型，給出了求解該模型的啟發(fā)式算法，并通過算例驗(yàn)證了該算法的有效性。

[參考文獻(xiàn)]

[1]東北證券. 金融危機(jī)加速中國制造業(yè)格局調(diào)整[DB].http://www.nesc.cn/jsp/front/Study/ Index.jsp, 2008-10-30.

[2]Chen,C.Y.,Zhao Z.Y., Ball,M.O. Quanntity and Due Date Quoting Available to Promise[J]. Information Systems Frontiers, 2001,3:477-488.

[3]Bongju Jeong,Seung-Bae Sim,Ho-Sang Jecong et al. An available-to-promise system for TFT LCD manufacturing in supply chain[J]. Computer & Industrial Engineering, 2002,43:191-212.

[4]蔡穎. ERP高級計(jì)劃APS供應(yīng)鏈優(yōu)化引擎[M]. 廣東: 廣東經(jīng)濟(jì)出版社, 2004.9.

[5]石為人, 余兵. 高級計(jì)劃排產(chǎn)系統(tǒng)與ERP的集成設(shè)計(jì)及實(shí)現(xiàn). 重慶大學(xué)學(xué)報(bào), 2003, 26(11): 87-90.

[6]H. Stadtler, C. Kilger (Eds.), Supply Chain Management and Advanced Planning: Concepts, Models, Software and Case Studies, second ed., Springer, Berlin, 2002.

[7]J.W.M. Bertrand, J.C. Fransoo, Operations Management Research Methodologies using quantitative modeling[J].International Journal of O’perations and Production Management 22 (2), 2002, pp. 241-264.

[8]藍(lán)伯雄. 企業(yè)資源優(yōu)化與優(yōu)化模型[J]. 計(jì)算機(jī)集成制造系統(tǒng)-CIMS, 2004, 10 (3):241-251.

[9]Steger-Jensen, Kenn, Hvolby, Hans-Henrik. Analysis of the planning and scheduling functionality in APS systems[C]. Proceedings of SPIE -The International Society for Optical Engineering, 2001, 4566:109-116.

[10]Shin, Kaikou. Feasibility study of real-time scheduling using the Lagrangean relaxation method under an APS environment[J]. JSME International Journal, Series C: Mechanical Systems, Machine Elements and Manufacturing, 2003,46(1):39-45.

[11]Tinham, Brian. APS holds the keys to AWS’manufacturing future[J]. Manufacturing Computer Solutions, 2002,8(3):52-53.

[12]丁斌,陳曉劍. 高級排程計(jì)劃APS發(fā)展綜述[J]. 運(yùn)籌與管理, 2004,13(3):155-159.