曾小青， 劉 寧， 肖海燕

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

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

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

(一)實現(xiàn)ATP需要強大的計劃系統(tǒng)

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

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

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

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

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

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

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

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

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

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

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

(1)符號定義：

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

(2)優(yōu)化目標：

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

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

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

目標函數(shù)為：

①按時交貨目標：

(1)

②能力平衡目標：

(2)

約束條件為：

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

(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ù)規(guī)劃模型，可用運籌學軟件來求解。然而，它的求解容易受組合優(yōu)化問題規(guī)模的限制，當問題規(guī)模很大的時候，求最優(yōu)解是困難的。因此在實際應用中通常是尋求效率高、優(yōu)化效果較好的啟發(fā)式算法。下面給出求解該模型的一種啟發(fā)式新算法：

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

出于算法描述的需要，另外定義幾個臨時變量：

第j臺設備在第k時間段已有負荷為：MLjk，初值為0；

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

當前工件尚未安排的加工任務：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.

(三)應用實例

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

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

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

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

(四)算法分析

(1)計算復雜性

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

(2)算法有效性

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

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

三、結(jié)論

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

[參考文獻]

[1]東北證券. 金融危機加速中國制造業(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高級計劃APS供應鏈優(yōu)化引擎[M]. 廣東: 廣東經(jīng)濟出版社, 2004.9.

[5]石為人, 余兵. 高級計劃排產(chǎn)系統(tǒng)與ERP的集成設計及實現(xiàn). 重慶大學學報, 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]藍伯雄. 企業(yè)資源優(yōu)化與優(yōu)化模型[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]丁斌,陳曉劍. 高級排程計劃APS發(fā)展綜述[J]. 運籌與管理, 2004,13(3):155-159.