1 引言

    九十年代以來，市場競爭的不斷加劇、產(chǎn)品的多樣化和更高顧客化需求給企業(yè)帶來了很大的壓力，企業(yè)越來越意識到在生產(chǎn)過程中引進操作柔性的重要性。一臺SMC插置機器可以通過增加插頭或者在插頭上增加可以插接不同元件的取件器而提高自身的操作柔性。而一條裝配線通常通過安裝不同的插置機器使其能夠生產(chǎn)不同種類的產(chǎn)品類。

    從1990年代以來，關(guān)于FMS生產(chǎn)能力調(diào)整問題已經(jīng)有了相當?shù)难芯俊Ｎ墨I[2]提出了一個在多產(chǎn)品背景下，多種技術(shù)可供選擇時的生產(chǎn)能力擴充模型，正如他在文中所述，這個模型的一個主要的局限在于需求不減的假設(shè)和柔性生產(chǎn)能力只生產(chǎn)特定的產(chǎn)品類的假設(shè)。文獻[3]研究了在多計劃期多種機器生產(chǎn)單產(chǎn)品類，并且設(shè)備規(guī)模離散時，生產(chǎn)能力的擴充、縮減以及替換的策略。文獻[4]和文獻[5]研究了生產(chǎn)能力擴充的最優(yōu)策略，盡管在模型中考慮了剛性設(shè)備和柔性設(shè)備之間的選擇，但是，他們的模型和求解方法不能直接應(yīng)用到PWB裝配線問題上，文獻[6]研究了不同計劃期上需求變化且多產(chǎn)品類背景下，剛性設(shè)備和完全柔性設(shè)備之間的權(quán)衡問題。文獻[7]隨后在隨機多種需求情形以及產(chǎn)品生命周期不確定的背景下將其結(jié)果進行了擴展．文獻[8]用一類模型來比較在不同的生產(chǎn)環(huán)境和控制策略下，產(chǎn)品的多樣性和生產(chǎn)的過程柔性對于生產(chǎn)的影響．這和本文的模型有一定的類似之處，但是要指出的是他們并沒有考慮產(chǎn)品的結(jié)構(gòu)，也就是產(chǎn)品的BOM約束．文獻[9]研究了需求隨時間變化的情形下生產(chǎn)能力的擴充問題，他們以最小化新設(shè)備投資成本、設(shè)備運作成本和庫存成本為目標，提出了一個多階段的混合整數(shù)規(guī)劃模型，并且通過Lasransian松弛的方法來尋找有效的新設(shè)備投資計劃。文獻[10]考慮了在一系列離散的需求情形下，并在廣定的投資約束下購買新設(shè)備，以未滿足需求最小化為目標建立了一個隨機整數(shù)規(guī)劃模型。他們找到了一個不隨需求變化的購買設(shè)備的集合，在該集合中選擇購買設(shè)備，可以以最小的投資成本滿足最大的需求．在多計劃期，多產(chǎn)品類，需求確定但會隨不同計劃期發(fā)生變化的情況下，文獻[11]提出了一個PWB裝配線能力擴充的模型，該模型考慮了機器的柔性以及產(chǎn)品的BOM約束．文獻[12]在該基礎(chǔ)上擴展到隨機的多種需求情形下的生產(chǎn)能力擴充問題，提出了一種通過求解多個背包問題來分解原問題的方法。但是，文獻[12]只研究了能力擴充問題，而沒有考慮能力縮減以及能力轉(zhuǎn)移問題，當考慮能力縮減以及能力轉(zhuǎn)移時，無法用背包問題來描述能力調(diào)整，需要開發(fā)其他的算法來求解這一問題．本文將研究隨機多種需求情形下的生產(chǎn)能力調(diào)整問題，在這種不確定的情形下進行生產(chǎn)能力的調(diào)整，將會帶來風(fēng)險，因此在模型中將加入對于風(fēng)險的描述，本文提出的求解方法不僅僅解決能力擴充問題，而且還能夠得到完整的能力調(diào)整決策(包括設(shè)備拆卸以及設(shè)備轉(zhuǎn)移)。

    文章的結(jié)構(gòu)如下：第2節(jié)提出了PWB裝配線的一個能力規(guī)劃模型；第3節(jié)提出了減少搜索空間的一個啟發(fā)式算法，得到模型的調(diào)整略集；第4節(jié)運用遺傳算法對調(diào)整略集進行搜索；第5節(jié)通過實例驗證了本文方法的正確性和可行性；第6節(jié)為文章的結(jié)論部分。

2 BOM約束下的能力規(guī)劃問題

    本文將要考慮隨機需求下的能力規(guī)劃問題，在多個時間段上需求有多種可能情形，在這種不確定的情形下進行生產(chǎn)能力的調(diào)整，將會帶來風(fēng)險，因此在做出能力調(diào)整決策時，需要考慮兩個目標，即最大的期望收益和最小的風(fēng)險．在文獻[13]的FMS能力規(guī)劃模型中，運用期權(quán)定價的方法描述了風(fēng)險，本文也將采用這種方法表述風(fēng)險。

    具體模型眠如下，其中的符號和參數(shù)見表1。

表1 模型中的符號和參數(shù)

    上述模型加入了對于風(fēng)險的描述，其中r是帶有風(fēng)險的收益率(投資報酬率)，a為年期望風(fēng)險收益率(風(fēng)險貼水)，α = r－rf，rf為無風(fēng)險利率。模型中(1)式為目標函數(shù)，前三項是裝配線的調(diào)整成本，分別對應(yīng)于調(diào)整新機器、拆卸已有機器、轉(zhuǎn)移機器的成本，第四項和第五項為期望的外包成本和期望的生產(chǎn)成本之和。(2)式和(3)式為能力約束，分別要求每臺機器的總插置數(shù)不超過其總能力和第i種元件的生產(chǎn)計劃不超過每臺機器的能力。(4)式為BOM約束，要求每個產(chǎn)品類必須在同一條裝配線上完成，也即要求每條裝配線上產(chǎn)品類的元件生產(chǎn)計劃必須滿足BOM約束。(5)式為需求約束，要求每種元件的生產(chǎn)計劃不能超過需求。(6)式為投資預(yù)算約束，要求調(diào)整新設(shè)備的總投資不能超過預(yù)算。(7)式為非負和整數(shù)約束。

    模型M0是一個大規(guī)模混合整數(shù)規(guī)劃問題，一個實際的問題如18條裝配線用5類元件制造3個產(chǎn)品類，每條裝配線計劃期初平均有6臺插置機器，可選用的機器種類為40，計劃期(兩年)被等分為8個時間段(季度)，則模型有159，840個對應(yīng)于生產(chǎn)計劃的連續(xù)決策變量，106，560個對應(yīng)于裝配線調(diào)整的整數(shù)決策變量和297，224個約束．該模型無法直接進行求解。

3 減小搜索空間的略集求解方法

    如上節(jié)所述，一個實際的問題中含有106，560個能力調(diào)整整數(shù)決策變量，但是事實上可能只是某幾種機器加到某幾條裝配線上，也就意味著很多整數(shù)決策變量的值為零．一個直觀的解釋是，對于每一條裝配線，由于生產(chǎn)要滿足需求和成本約束以及產(chǎn)品類的BOM約束，同時考慮裝配線上已有的機器，某些種類的機器加到該條裝配線上是不可取的。因此可以通過一些啟發(fā)式算法把這些不可取的決策變量從搜索空間中去掉，本文先求解模型M0，得到一個對應(yīng)于每個時間段每條裝配線需要加某些機器的集合(稱為增裝略集，略集中的每一個元素表示在某個時間段上某種機器加到某條裝配線是合適的)，然后應(yīng)用一些規(guī)則對其進行修正，得到設(shè)備調(diào)整略集(包括增裝、拆卸以及轉(zhuǎn)移)，最后應(yīng)用遺傳算法(GA)搜索調(diào)整略集以得到問題的一個近似最優(yōu)解。

    用{A(t，m，Z)}表示時間段t上對應(yīng)所有需求情形時第m種機器應(yīng)該加到第z條裝配線上的集合，{B(t，n，m，L)}表示時間段t上對應(yīng)每種需求情形rt時第m種機器應(yīng)該加到第Z條裝配線上的集合，則集合{B(t，n，m，L)}可以通過類似于確定需求下增裝略集的求解方法得到(具體算法見文獻[11])．
    在得到{B(t，n，m，L)}之后，如何得到{A(t，m，L)}，一個直觀的方法如下：

     (8)式實際上是一種求所有市場需求情形下的最大的增裝略集的方法。

    在確定調(diào)整略集時，雖然求得的{A(t，m，L)}是一個增加機器的集合，但是在多計劃期時在該略集下求解，仍然會出現(xiàn)拆卸機器的情況，一個直觀的原因是由于開始的計劃期增加了較多的某種機器而導(dǎo)致后期的時間段上需要拆卸．基于這個原因，需要對集合{A(t，m，L)}作如下的修正：在確定每個時間段的調(diào)整略集時，都使它包含以前各期略集中相應(yīng)的元素．同時由于求得的{B(t，n，m，L)}是每個時間段t上每種需求情形n下應(yīng)該增加的機器集合，無法得到該時間段上該需求情形下應(yīng)該拆卸的機器集合．解決這個問題的一個方法是，由于在計劃期初存在一個初始的裝配線布局，而考慮到機器的拆卸只能是對應(yīng)于某時間段上某條裝配線存在這種機器的情形，因此可以進一步的修正集合{A(t，m，L)：再在每個時間段集合的元素中，加入初始布局上存在的機器種類．做了上述兩次修正后，可以得到最終的集合{A(t，m，L)}必然也包含了需要拆卸機器的集合．由于初始的裝配線布局對于機器種類也是稀疏的，作如上的處理雖然會使問題的規(guī)模仍然較大，但是相比較原始問題而言，它仍然在很大程度上縮小了搜索空間。

    當模型M0。的調(diào)整略集確定后，可以通過求解新的模型M1。來得到近似最優(yōu)解．模型。只需把肘。中的(7)式替換成：

4 遺傳算法搜索調(diào)整略集

    應(yīng)用遺傳算法搜索調(diào)整略集，以下將主要介紹算法的編碼方法和個體適應(yīng)度評價方法，編碼方法：

    算法中染色體直接用0—20的十進制整數(shù)進行編碼，在每一位整數(shù)前加一個符號位，“－”表示拆卸機器，“+”則表示增加機器。生成初始群體時，考慮到不增加任何機器(對應(yīng)染色體的所有基因位為零)是問題的一個可行解，而且考慮到最優(yōu)解對應(yīng)的染色體的很多基因位將會為零，算法中將不增加任何機器總是作為一個初始解。其他的初始解將由系統(tǒng)隨機生成，為了能夠確保隨機生成的初始解是問題的可行解，需要記錄每一期的裝配線結(jié)構(gòu)，某一期的裝配線調(diào)整決策變量必須以上一期的裝配線結(jié)構(gòu)為依據(jù)，只有當上一期裝配線包含某種機器，對應(yīng)于該條裝配線的該種機器的基因才可能取負數(shù)，并且負數(shù)的絕對值不能超過原有機器的臺數(shù)；其他的基因只能隨機的取正數(shù)，這條原則在變異操作和交叉操作同樣需要遵循。

    個體適應(yīng)度評價方法：

    記MIN和MAX分別為某一代染色體中所有染色體對應(yīng)的模型肘．的目標函數(shù)值的最小值和最大值，本文定義如下地適應(yīng)度函數(shù)：

    在(10)式中，Zˊ(y)是模型M1的目標函數(shù)值上增加超過投資預(yù)算的適應(yīng)性懲罰因子P(g，y)后的總成本，g為遺傳算法進化的代數(shù)，即

    在(12)式中，參數(shù)α≥0，β＞0，y，g1>1與P均是可調(diào)參數(shù)，用以調(diào)整懲罰因子的大小．其中，g，>l的作用在于算法開始的若干代不考慮投資預(yù)算約束．y的值可正可負，若取正，則相對而言有縮小超預(yù)算后果的作用，反之則有放大超預(yù)算后果的作用．參數(shù)α>0的作用在于對投資預(yù)算的約束隨進化代數(shù)的增加而要求越來越嚴厲。β>0是調(diào)整懲罰因子整體水平的參數(shù)，P為懲罰因子的上限。

    在上述的染色體中沒有基因位表示機器的轉(zhuǎn)移，但是實際上由于編碼時在整數(shù)變量前加了符號位，使得染色體中已經(jīng)隱含了機器轉(zhuǎn)移的情況．考慮到模型的形式和求解順序，通過遺傳算法搜索解空間，得到一個表示機器增減的解串，此時生產(chǎn)能力調(diào)整已經(jīng)確定，然后再在此能力調(diào)整方案下求解一個生產(chǎn)計劃問題(模型肘，的(2)式和(3)式)。

    若一個解串只是考慮增加或者減少機器兩種情況而不考慮機器轉(zhuǎn)移的情況，則通過(10)式確定的適應(yīng)度函數(shù)值偏高，而對于模型肘。中生產(chǎn)能力的約束沒有影響．如對于某個時間段t某種機器m得到調(diào)整略集{A(t，m，1)，A(t，m，2)，A(t，m，4)}，即在第1、2、4條裝配線上需要調(diào)整機器m，在遺傳算法中用三個基因位表示。由于每個解串的每個基因位表示的是相應(yīng)時間段相應(yīng)裝配線上相應(yīng)機器的增減情況，則在求解生產(chǎn)計劃問題時，只需要把這三個基因代入到能力約束((2)式和(3)式)中，即可得到時間段t上裝配線的實際布局，也即對于模型M1．中的生產(chǎn)能力約束沒有影響。

    若某個染色體中這三個基因分別為a，-b和C(其中a，b，C均為大于零的整數(shù)，并假定a>b)，則暗示著在一個實際的調(diào)整方案是將第m種機器從第2條裝配線轉(zhuǎn)移b臺到第1條裝配線上，實際調(diào)整成本：

    如果殘值按照購買單價的30％計算，則C—Cˊ<70％Cp(t，m)<0，即通過遺傳算法得到的適應(yīng)度函數(shù)值偏高。同時可以看出，遺傳算法得到的投資成本也偏高．解決這個問題的一個方法是，在評價一個染色體的適應(yīng)度時，首先識別略集中t和m相同的元素，并同時識別是否存在機器轉(zhuǎn)移的情況，如果存在，則需要根據(jù)(13)式計算生產(chǎn)能力調(diào)整成本以修正該染色體的總成本，并同時修正適應(yīng)度函數(shù)值。

5 實例研究

    5.1 小規(guī)模仿真實例

    應(yīng)用上述算法對隨機需求下的裝配線能力調(diào)整問題進行仿真計算．假設(shè)企業(yè)有2條生產(chǎn)線，共有3種機器可供選擇，生產(chǎn)的產(chǎn)品類為2種，且共有3種元件組成各種產(chǎn)品類，計劃期為2個(具體數(shù)據(jù)見文獻[11])。

    在上述的規(guī)模下，可以通過數(shù)學(xué)軟件LP_solver直接求解，用Y(t，m，L)表示第t時間段上第Z條裝配線第m種機器的調(diào)整臺數(shù)，y(t，m，L)為正表示增加，為負表示拆卸，則可以得到最優(yōu)解如下：

    y(1，1，1)=1，y(1，1，2)=1，y(1，3，1)=3，y(1，3，2)=3，r(2，2，2)=-l，r(2，3，2)=-1，對應(yīng)的總成本凈現(xiàn)值為$1600767。

    應(yīng)用第三部分提出的方法求解得到的調(diào)整略集為(其中取δ=0.5)：A(1，1，1)，A(1，1，2)，A(I，2，2)，A(1，3，1)，A(1，3，2)，A(2，1，1)，A(2，1，2)，A(2，2，2)，A(2，3，1)，A(2，3，2)，其中一共有10個元素．再應(yīng)用第四部分提出的遺傳算法搜索略集，得到的最優(yōu)解為：y(1，1，1)=1，y(1，I，2)=1，y(1，3，1)=3，y(1，3，2)=3，r(2，2，2)=-1，g(2，3，2)=一1，對應(yīng)的總成本凈現(xiàn)值為$1600767。

     從上述小規(guī)模仿真計算的結(jié)果可以看到，通過求取模型M。的調(diào)整略集，使得遺傳算法的搜索空間減少了(小規(guī)模問題減少了兩個元素，效果不是很明顯，但是對于大規(guī)模問題，搜索空間將會有較大幅度的減少)。同時可以看到通過計算得到的調(diào)整略集在減少搜索空間的同時能夠較好的保持搜索空間的完整性，從而提高了算法收斂到最優(yōu)解的可能性。

表2 生產(chǎn)線初始布局

    5.2 大規(guī)模的仿真實例

    某企業(yè)有12條生產(chǎn)線生產(chǎn)3個產(chǎn)品類．初始生產(chǎn)線布局如表2所示，共有20種機器可供選擇，其特征如表3所示，產(chǎn)品類結(jié)構(gòu)如表4所示，市場需求如表5所示，各種市場需求情形出現(xiàn)的概率如表6所示．根據(jù)論文[11]的略集求解方法得到機器增裝略集如表7所示。

表3 可用機器特征

表4 產(chǎn)品類結(jié)構(gòu)

表5 多時間段上市場需求情形

表6 各市場需求情形出現(xiàn)的概率

表7 時間段上的增裝略集

    應(yīng)用本文提出的修正方法對增裝略集進行修正得到設(shè)備調(diào)整略集，然后在相同的條件下進行十次計算，得到的十個收斂解中最差的個體對應(yīng)的生產(chǎn)線調(diào)整決策如下(對應(yīng)的總成本凈現(xiàn)值為$31772412．oo)：

    Y(1，2，4)=2，y(1，3，7)=10，Y(2，14，2)=1，Y(6，3，5)=7，y(6，3，7)=1，l，(7，3，2)=3，y(7，3，4)=5，Y(8，3，12)=1。

    最優(yōu)的個體對應(yīng)的生產(chǎn)線調(diào)整決策如下(對應(yīng)的總成本凈現(xiàn)值$31720234.00)：

    y(1，2，7)=3，l，(1，3，4)=4，l，(3，3，7)=5，y(4，3，7)=2，y(5，3，4)=6，y(5，3，5)=4，l，(6，3，8)=1．在上述實例中，十組解中目標函數(shù)值之間的最大誤差為0．16％，可以認為已經(jīng)收斂到了近似解，于是我們把這個最優(yōu)個體作為企業(yè)最后的生產(chǎn)線調(diào)整策略。

    5.3 算法的優(yōu)越性

    由于本文建立的生產(chǎn)能力調(diào)整模型是一個大規(guī)模的混合整數(shù)規(guī)劃模型，目前還沒有較好的方法進行求解，在已有文獻中，標準遺傳算法是一種較為常用的求解這一問題的方法．因此，我們將從計算時間和計算誤差兩個方面，把本文算法(記為HGA)的結(jié)果與標準遺傳算法(記為SGA)的結(jié)果進行比較，以說明本文算法的適用性以及優(yōu)越性．比較結(jié)果見表8，其中計算誤差的計算方法為：當整數(shù)變量個數(shù)小于20時，原問題可以通過數(shù)學(xué)軟件LP 80lvelr直接求解，此時最優(yōu)解對應(yīng)的最優(yōu)值記為OPT，計算結(jié)果記為z(x)，則計算誤差為：(z(x)一oFr)／OPT×100．當整數(shù)變量個數(shù)大于20時，由于此時無法得到原問題的最優(yōu)解，因此通過LP solver求解忽略整數(shù)約束時的線性規(guī)劃問題，得到最優(yōu)解對應(yīng)的最優(yōu)值記為LB，則計算誤差為：(z(x)—LB)，OPT×100．由于LB是原始問題最優(yōu)值的下界，因此，算法的實際誤差要低于該計算誤差。

    表8的計算結(jié)果顯示：雖然本文的算法處理規(guī)模較小的問題時，計算時間與標準遺傳算法相比不具有明顯的優(yōu)勢(這主要是因為本文的算法在求解調(diào)整略集時需要花費一定的時間)，但是在計算精度上仍然要高于標準遺傳算法。而當問題規(guī)模較大時(整數(shù)變量個數(shù)大于50)，本文的算法無論在計算精度上還是計算時間上都遠遠優(yōu)于標準遺傳算法，這說明了本文算法處理大規(guī)模混合整數(shù)規(guī)劃問題的有效性以及優(yōu)越性。

表8 不同規(guī)模的計算結(jié)果比較

6 結(jié)論

    本文針對印刷裝配板的制造過程，建立了一個基于多種需求狀態(tài)的多計劃期多種產(chǎn)品類的能力規(guī)劃模型，該模型考慮了機器的柔性、產(chǎn)品類的BOM約束以及進行生產(chǎn)能力調(diào)整的風(fēng)險。由于模型是一個大規(guī)模的混和整數(shù)規(guī)劃問題，無法用一般的數(shù)學(xué)軟件直接進行求解，本文提出了一種求解近似最優(yōu)解的方法。首先減少裝配線能力調(diào)整決策變量的搜索空間，然后應(yīng)用遺傳算法進行搜索．最后通過實例分析驗證了該方法的可行性，并將計算結(jié)果與標準遺傳算法的計算結(jié)果進行了比較。比較結(jié)果表明，相對于標準遺傳算法而言，盡管該方法在處理小規(guī)模問題時不具有顯著的優(yōu)勢，但是在處理大規(guī)模問題時，該方法在計算精度上以及計算時間上都遠遠優(yōu)于標準遺傳算法．因此，本文給出了一種處理大規(guī)模的多需求狀態(tài)下多計劃期多種產(chǎn)品類的能力規(guī)劃問題的有效方法，為企業(yè)制定相應(yīng)的能力規(guī)劃決策提供了有力的支持。

核心關(guān)注：拓步ERP系統(tǒng)平臺是覆蓋了眾多的業(yè)務(wù)領(lǐng)域、行業(yè)應(yīng)用，蘊涵了豐富的ERP管理思想，集成了ERP軟件業(yè)務(wù)管理理念，功能涉及供應(yīng)鏈、成本、制造、CRM、HR等眾多業(yè)務(wù)領(lǐng)域的管理，全面涵蓋了企業(yè)關(guān)注ERP管理系統(tǒng)的核心領(lǐng)域，是眾多中小企業(yè)信息化建設(shè)首選的ERP管理軟件信賴品牌。

轉(zhuǎn)載請注明出處：拓步ERP資訊網(wǎng)http://www.guhuozai8.cn/

本文標題：印刷裝配板行業(yè)ERP系統(tǒng)考慮BOM的FMS生產(chǎn)線能力規(guī)劃問題

本文網(wǎng)址：http://www.guhuozai8.cn/html/consultation/1082003716.html