面向供應(yīng)鏈的高級(jí)計(jì)劃與排程的混合整數(shù)規(guī)劃模型

陳可嘉 葉舒婷

福州大學(xué)，福州，350108

0 引言

生產(chǎn)計(jì)劃與排程是制造企業(yè)生產(chǎn)運(yùn)作的核心內(nèi)容。當(dāng)前，許多制造企業(yè)都采用企業(yè)資源計(jì)劃（enterprise resource planning，ERP）進(jìn)行生產(chǎn)管理，但是ERP無論在計(jì)劃技術(shù)或功能方面都不具備協(xié)調(diào)多個(gè)企業(yè)資源的能力，它仍舊是面向企業(yè)內(nèi)部的事務(wù)處理系統(tǒng)［1－2］。在市場(chǎng)競(jìng)爭(zhēng)日益激烈、供應(yīng)鏈上各企業(yè)間合作日趨緊密的環(huán)境中，ERP已不能滿足現(xiàn)代制造企業(yè)的生產(chǎn)需求，尋找一種替代ERP的生產(chǎn)運(yùn)作管理系統(tǒng)勢(shì)在必行。面向供應(yīng)鏈的高級(jí)計(jì)劃與排程（advanced planning and scheduling，APS）的出現(xiàn)正迎合了這一趨勢(shì)，是生產(chǎn)計(jì)劃與排程技術(shù)的一個(gè)飛躍［3］。

隨著APS的重要性的日益凸顯，越來越多的學(xué)者開始對(duì)其進(jìn)行研究［4－5］。但是，對(duì)于 APS模型的研究仍然較少，并且多是采用啟發(fā)式方法進(jìn)行求解，未能給出模型的最優(yōu)解。文獻(xiàn)［6］研究了制造－裝配兩階供應(yīng)鏈中的APS問題，以最小化存儲(chǔ)和準(zhǔn)備成本為目標(biāo)，給出了混合整數(shù)規(guī)劃模型以及基于兩階段逆向求解的啟發(fā)式方法。文獻(xiàn)［7］考慮了具有柔性加工順序、機(jī)器可選等主要特征的供應(yīng)鏈生產(chǎn)系統(tǒng)，以最小化流程時(shí)間為目標(biāo)，建立了面向供應(yīng)鏈的APS模型，通過算例驗(yàn)證了遺傳算法在求解這一模型上的有效性。文獻(xiàn)［8］考察了每個(gè)客戶訂單有確定交付期且外包可用情形下的APS問題，以最小化總制造時(shí)間為目標(biāo)，提出了APS數(shù)學(xué)模型，并采用遺傳算法進(jìn)行了求解。

在日益重視合作生產(chǎn)的同時(shí)，現(xiàn)代制造企業(yè)也越來越強(qiáng)調(diào)準(zhǔn)時(shí)交貨的重要性。因此，最小化提前/拖期懲罰已成為排程研究的又一熱點(diǎn)［9－10］。文獻(xiàn)［11］分析了并行機(jī)提前/拖期排程問題，論證了該問題最優(yōu)加工順序的特點(diǎn)。文獻(xiàn)［12］針對(duì)提前/拖期Job Shop排程問題，建立了相應(yīng)的數(shù)學(xué)模型，提出了約束滿足與禁忌搜索相結(jié)合的混合求解算法。然而，在APS問題中考慮提前/拖期懲罰，尚沒有受到足夠重視。

本文在考慮供應(yīng)鏈物理約束、機(jī)器能力約束、工件加工順序約束、可選機(jī)器、訂單交付期的基礎(chǔ)上，以最小化提前/拖期懲罰為目標(biāo)，建立了面向供應(yīng)鏈的高級(jí)計(jì)劃與排程的混合整數(shù)規(guī)劃模型，應(yīng)用LINGO軟件對(duì)算例進(jìn)行了求解，得到了最優(yōu)生產(chǎn)排程，驗(yàn)證了模型的有效性。

1 模型構(gòu)建

1.1 基本假設(shè)

（1）工件的加工時(shí)間是預(yù)知的，輔助時(shí)間包含在加工時(shí)間內(nèi)；

（2）工件必須連續(xù)加工，一旦開始加工就不能中斷；

（3）每臺(tái)機(jī)器一次只能加工一個(gè)工件；

（4）一個(gè)工件不能同時(shí)在兩臺(tái)機(jī)器上加工；

（5）產(chǎn)品的加工批量、運(yùn)輸批量等于產(chǎn)品的訂貨量。

1.2 問題描述

考慮一個(gè)具有多個(gè)工廠的供應(yīng)鏈網(wǎng)絡(luò)，在每個(gè)工廠中，有多臺(tái)不同功能的機(jī)器，每臺(tái)機(jī)器都受到一定的能力約束。供應(yīng)鏈系統(tǒng)能夠生產(chǎn)多種產(chǎn)品，不同的產(chǎn)品具有不同的物料清單、工件加工順序，每一工件有一臺(tái)或多臺(tái)不同工廠的機(jī)器可供選擇加工。在供應(yīng)鏈系統(tǒng)中，有多份待加工的訂單，不同的訂單所需的產(chǎn)品不同、訂貨量不同、交付期不同。

面向供應(yīng)鏈的高級(jí)計(jì)劃與排程的目標(biāo)是：在充分考慮供應(yīng)鏈物理約束、機(jī)器能力約束、工件加工順序約束的基礎(chǔ)上，找到滿足客戶訂單要求的、跨越整個(gè)供應(yīng)鏈的、可行且最優(yōu)的生產(chǎn)方案，使得提前/拖期懲罰最小。

1.3 參數(shù)定義

本文所涉及的參數(shù)定義如下：n為訂單數(shù)；f為供應(yīng)鏈網(wǎng)絡(luò)中的工廠數(shù)；mk為工廠k的機(jī)器數(shù)，k＝1，2，…，f；Oi為訂單編號(hào)，i＝1，2，…，n；TQi為訂單Oi的訂貨量；Qip為訂單Oi的工件p的數(shù)量；Pi為訂單Oi的最終產(chǎn)品；tipkl為訂單Oi的工件p在工廠k的機(jī)器l上的單件加工時(shí)間；Tipkl為訂單Oi的工件p在工廠k的機(jī)器l上的批量加工時(shí)間；A（p）為工件p的子工件集；B為工件p的集合，即A（p）＝?；Npq為工件q需要的子工件p的數(shù)量，p∈A（q）；TRuv為工廠u與工廠v之間的運(yùn)輸時(shí)間，當(dāng)u＝v時(shí)，TRuv＝0（u，v＝1，2，…，f）；tt為機(jī)器每天的加工時(shí)間，即機(jī)器的加工能力；M為一個(gè)足夠大的整數(shù)；DDi為訂單Oi的交付期；ECi為訂單Oi的提前懲罰系數(shù)；TCi為訂單Oi的拖期懲罰系數(shù)。

1.4 變量定義

本文所涉及的變量定義如下：STipkl為訂單Oi的工件p在工廠k的機(jī)器l上的開始加工時(shí)間；FTipkl為訂單Oi的工件p在工廠k的機(jī)器l上的結(jié)束加工時(shí)間；當(dāng)訂單Oi的工件p先于訂單Oj的工件q在工廠k的機(jī)器l上加工時(shí)，Xipjqkl＝1，其他情況下Xipjqkl＝0；當(dāng)訂單Oi的工件p在工廠k的機(jī)器l上加工時(shí)，Yipkl＝1，其他情況下Yipkl＝0；Ci為訂單Oi的完工時(shí)間；Li為訂單Oi的拖后時(shí)間（實(shí)數(shù)值）；Ei為訂單Oi的提前時(shí)間（實(shí)數(shù)值）為訂單Oi的拖后時(shí)間（整數(shù)值）；為訂單Oi的提前時(shí)間（整數(shù)值）。

1.5 數(shù)學(xué)模型

（1）工件加工約束如下：

式（1）確保各個(gè)零件的開始加工時(shí)間大于或等于0。式（2）表明，訂單Oi的最終產(chǎn)品的數(shù)量等于訂貨量，訂單Oi的其他工件的數(shù)量等于該工件的上級(jí)工件需要該工件的數(shù)量乘以其上級(jí)工件的數(shù)量。式（3）表明，訂單Oi的工件p在工廠k的機(jī)器l上的批量加工時(shí)間等于工件p在工廠k的機(jī)器l上的單件加工時(shí)間乘以訂單Oi對(duì)工件p的總需求量。式（4）表明：當(dāng)Yipkl＝1時(shí)，即當(dāng)訂單Oi的工件p在工廠k的機(jī)器l上加工時(shí)，其結(jié)束加工時(shí)間等于該工件在工廠k的機(jī)器l上的開始加工時(shí)間加上批量加工時(shí)間；當(dāng)Yipkl＝0時(shí)，即當(dāng)訂單Oi的工件p不在工廠k的機(jī)器l上加工時(shí)，其在工廠k的機(jī)器l上的結(jié)束加工時(shí)間等于開始加工時(shí)間，即該工件在工廠k的機(jī)器l上的加工時(shí)間為0。式（5）表明，各訂單的完工時(shí)間等于該訂單的最終產(chǎn)品的結(jié)束加工時(shí)間。式（6）和式（7）確保同一機(jī)器在同一時(shí)刻只加工一個(gè)工件。式（6）表明，當(dāng)訂單Oi的工件p和訂單Oj的工件q都在工廠k的機(jī)器l上加工（Yipkl＝Y(jié)jqkl＝1）時(shí)，工件p和q必須按照一定的先后順序進(jìn)行加工，工廠k的機(jī)器l不得同時(shí)對(duì)二者進(jìn)行加工，即Xipjqkl＋Xjqipkl＝1。式（7）表明，當(dāng)訂單Oi的工件p后于訂單Oj的工件q在工廠k的機(jī)器l上加工（Xipjqkl＝0，Xjqipkl＝1）時(shí)，訂單Oi的工件p的開始加工時(shí)間不得小于訂單Oj的工件q的結(jié)束加工時(shí)間；當(dāng)Xjqipkl＝0時(shí)，式（7）恒成立。式（8）表明，訂單Oi的工件p在工廠k的機(jī)器l上的開始加工時(shí)間大等于其子工件的結(jié)束加工時(shí)間，若其子工件在其他工廠加工，則訂單Oi的工件p在工廠k的機(jī)器l上的開始加工時(shí)間大等于其子工件在工廠u的機(jī)器v上的結(jié)束加工時(shí)間加上工廠u與工廠k之間的運(yùn)輸時(shí)間。式（9）確保各個(gè)工件都能得到加工，并且一個(gè)工件只在一臺(tái)機(jī)器上加工。

（2）提前/拖期約束如下：

式（10）和式（11）分別定義了訂單的提前時(shí)間和拖后時(shí)間。由于設(shè)定機(jī)器每天工作tt小時(shí)，在約束式（10）和式（11）中將訂單的完工時(shí)間除以tt，實(shí)現(xiàn)了將“小時(shí)（h）”換算成“天（d）”。當(dāng)提前/拖期懲罰以天為單位時(shí)，式（12）和式（13）將各訂單的提前時(shí)間和拖后時(shí)間轉(zhuǎn)換成整數(shù)。也就是說，如果一個(gè)訂單在交付期前0.5d完工，則認(rèn)為該訂單提前期為0d；反之，如果一個(gè)訂單在交付期后0.5d完工，則認(rèn)為其拖期為1d。為了保證計(jì)算的精確性，引入0.99來實(shí)現(xiàn)轉(zhuǎn)換。

（3）變量約束如下：

（4）目標(biāo)函數(shù)如下：

ECi和TCi分別為訂單Oi的提前、拖期懲罰系數(shù)，一般情況下ECi＜TCi。目標(biāo)函數(shù)式（18）表明，模型的優(yōu)化目標(biāo)是最小化提前/拖期懲罰，即盡量使各訂單準(zhǔn)時(shí)完工。

2 算例分析

為了驗(yàn)證模型的有效性，現(xiàn)參考文獻(xiàn)［13］中的算例進(jìn)行測(cè)試。

考慮如圖1所示的產(chǎn)品結(jié)構(gòu)，最終產(chǎn)品F1由組件S1、S2、S3與零件 C1、C2、C3、C4、C5組成。在所有工件中，C4與C6是通用件，其中C4是F1與S1的通用件，C6是S1與S3的通用件。零件C1、C2、C4與C5需要通過兩道工序（P1、P2）加工，因此它們可進(jìn)一步分解為CiP1與CiP2（i＝1，2，4，5）；零件C10需要通過三道工序（P1、P2、P3）加工，因此它可進(jìn)一步分解為C10P1、C10P2、C10P3。

圖1 產(chǎn)品結(jié)構(gòu)

供應(yīng)鏈中有兩個(gè)工廠（記為FAi，i＝1，2），每個(gè)工廠各有三臺(tái)機(jī)器（記為 Mik，i＝1，2，k＝1，2，3）。每臺(tái)機(jī)器每天的加工能力為8h。從工廠FA1到工廠FA2的單向運(yùn)輸時(shí)間為8h，并且產(chǎn)品的運(yùn)輸批量、加工批量等于產(chǎn)品的訂貨量。

表1中，工件（列）與機(jī)器（行）的對(duì)應(yīng)數(shù)字表示的是該工件在此機(jī)器上的加工時(shí)間，均以“小時(shí)”為單位，“－”表示該工件不能在此機(jī)器上進(jìn)行加工。

現(xiàn)有一個(gè)客戶訂單：訂購(gòu)2個(gè)產(chǎn)品F1，交付期為25d。提前懲罰系數(shù)為0.15/d，拖期懲罰系數(shù)為0.75/d。

表1 工件加工時(shí)間 h

將建立的混合整數(shù)規(guī)劃模型，運(yùn)用LINGO軟件進(jìn)行求解，關(guān)鍵代碼如下所示：

對(duì)于上述算例，混合整數(shù)規(guī)劃模型共有7702個(gè)約束條件，3892個(gè)變量，其中3600個(gè)整數(shù)變量。在Pentium（R）Dual－Core E5500 2.8GHz處理器、2GB內(nèi)存、Windows XP系統(tǒng)下，算例通過軟件LINGO進(jìn)行求解用時(shí)為18min29s，主要結(jié)果歸納于表2中。根據(jù)求解結(jié)果繪制出甘特圖，如圖2所示。其中，通用件表示為“通用件上級(jí)工件編號(hào)＋通用件自身編號(hào)”。例如，S1C6表示用于裝配S1的C6部件，而S3C6表示用于裝配S3的C6部件。由圖2可以看出，算例訂單的最優(yōu)完工時(shí)間為200h，即25個(gè)工作日，訂單準(zhǔn)時(shí)完工，提前/拖期懲罰為0。

表2 求解結(jié)果

圖2 求解結(jié)果的甘特圖

上述結(jié)果說明，本文所建立的模型能在滿足供應(yīng)鏈物理約束、機(jī)器能力約束、工件加工順序約束的基礎(chǔ)上，得出使訂單提前/拖期懲罰最小化的最優(yōu)排程。

3 結(jié)語

以ERP為代表的傳統(tǒng)生產(chǎn)計(jì)劃排程系統(tǒng)多局限于單個(gè)企業(yè)內(nèi)部，并且多以最小化流程時(shí)間為目標(biāo)，難以適應(yīng)現(xiàn)今面向供應(yīng)鏈的準(zhǔn)時(shí)生產(chǎn)模式。本文在考慮供應(yīng)鏈物理約束、機(jī)器能力約束、工件加工順序約束、可選機(jī)器、訂單交付期的基礎(chǔ)上，以最小化提前/拖期懲罰為目標(biāo)，建立了面向供應(yīng)鏈的高級(jí)計(jì)劃與排程的混合整數(shù)規(guī)劃模型。構(gòu)建的APS模型突破了ERP的局限，針對(duì)供應(yīng)鏈范圍內(nèi)的合作生產(chǎn)問題，優(yōu)化了不同節(jié)點(diǎn)企業(yè)的生產(chǎn)排程，更加符合現(xiàn)實(shí)的需要，為進(jìn)一步研究供應(yīng)鏈優(yōu)化問題提供了重要的參考。

［1］藍(lán)伯雄，陳暉娜.一個(gè)集成化企業(yè)生產(chǎn)計(jì)劃模型［J］.系統(tǒng)工程理論與實(shí)踐，2001，21（9）：33－41.

［2］Rom W O，Tukel O I，Muscatello J R.MRP in a Job Shop Environment Using a Resource Constrained Project Scheduling Model［J］.OMEGA－International Journal of Management Science，2002，30（4）：275－286.

［3］徐曉芳，張偉，葉春明.APS剖析［J］.計(jì)算機(jī)輔助設(shè)計(jì)與制造，2002，8（4）：13－17.

［4］Marriott P，Kleinschmidt R，Glatzer V，et al.Advanced Production Planning as the Core Element of a Supply Chain［J］.Metallurgical Plant and Technology International，2002，25（1）：78－80.

［5］陸杉.淺析APS在供應(yīng)鏈中的應(yīng)用［J］.中國(guó)管理信息化，2008，11（20）：76－79.

［6］Kolisch R.Integrated Assembly and Fabrication for Make－to－order Production［J］.International Journal of Production Economics，2000，68（3）：287－306.

［7］Moon C，Kim J S，Gen M.Advanced Planning and Scheduling Based on Precedence and Resource Constraints for E－plant Chains［J］.International Journal of Production Research，2004，42（15）：2941－2955.

［8］程文明，齊二石.制造業(yè)供應(yīng)鏈外包下的高級(jí)計(jì)劃與排程［J］.組合機(jī)床與自動(dòng)化加工技術(shù)，2005（5）：90－92.

［9］Gordon V，Proth J M，Chu C B.A Survey of the State－of－the－art of Common Due Date Assignment and Scheduling Research［J］.European Journal of Operational Research，2002，139（1）：1－25.

［10］Singh A.A Hybrid Permutation－coded Evolutionary Algorithm for the Early/tardy Scheduling Problem［J］.Asia－Pacific Journal of Operational Research，2010，27（6）：713－725.

［11］Toksari M D，Güner E.Parallel Machine Scheduling Problem to Minimize the Earliness/Tardiness Costs with Learning Effect and Deteriorating Jobs［J］.Journal of Intelligent Manufacturing，2010，21（6）：843－851.

［12］李俊芳，李鐵克，王偉玲.約束滿足混合算法求解提前/拖期Job Shop調(diào)度問題［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46（16）：12－15.

［13］Lee Y H，Jeong C S，Moon C.Advanced Planning and Scheduling with Outsourcing in Manufacturing Supply Chain［J］.Computers and Industrial Engineering，2002，43（1/2）：351－374.