基于蟻群算法的復(fù)合材料結(jié)構(gòu)件的返修計(jì)劃問(wèn)題*

姚智騫

(東南大學(xué)機(jī)械工程學(xué)院， 江蘇 南京 211189)

基于蟻群算法的復(fù)合材料結(jié)構(gòu)件的返修計(jì)劃問(wèn)題*

姚智騫

(東南大學(xué)機(jī)械工程學(xué)院， 江蘇 南京 211189)

為解決目前生產(chǎn)中出現(xiàn)的復(fù)合材料結(jié)構(gòu)件的質(zhì)量缺陷問(wèn)題，G公司設(shè)立了復(fù)合材料結(jié)構(gòu)件返修工序。針對(duì)結(jié)構(gòu)件返修計(jì)劃問(wèn)題，以最大化返修計(jì)劃中的結(jié)構(gòu)件數(shù)量為目標(biāo)，同時(shí)兼顧公司出貨計(jì)劃延遲和WIP成本(在制品成本)增加的情況，建立了0-1整數(shù)規(guī)劃模型，進(jìn)而以蟻群算法為基礎(chǔ)提出了2種偽隨機(jī)選擇規(guī)則。根據(jù)實(shí)際情況采用不同參數(shù)設(shè)計(jì)算例來(lái)驗(yàn)證算法的性能。結(jié)果表明在最大化返修結(jié)構(gòu)件數(shù)量方面，算法一優(yōu)于算法二，而在減小公司出貨延遲和控制WIP成本方面，算法二優(yōu)于算法一。

返修計(jì)劃; 整數(shù)規(guī)劃; 蟻群算法; 偽隨機(jī)選擇機(jī)制

引 言

G公司是一家專(zhuān)業(yè)生產(chǎn)、組裝、測(cè)試各類(lèi)航空用零部件、組裝部件、系統(tǒng)的制造企業(yè)，其中A型飛機(jī)機(jī)翼復(fù)合材料結(jié)構(gòu)件(以下簡(jiǎn)稱結(jié)構(gòu)件)是該公司剛剛推出的主要產(chǎn)品。G公司生產(chǎn)的結(jié)構(gòu)件采用碳纖維蜂窩夾層結(jié)構(gòu)，如圖1所示，這種結(jié)構(gòu)是一種特殊的復(fù)合材料(由2種或2種以上不同性質(zhì)的材料，通過(guò)物理或化學(xué)的方法，在宏觀或微觀上組成具有新性能的材料)，即在2塊強(qiáng)度和彈性模量較大的面層材料中間(稱作面板或蒙皮)夾著厚而輕的蜂窩芯材，并采用膠粘劑(熱固性樹(shù)脂)在一定溫度和壓力下復(fù)合成一個(gè)整體剛性結(jié)構(gòu)。其中蜂窩由凱夫拉纖維浸漬上樹(shù)脂，通過(guò)膠接拉伸法或波紋壓形膠接法制得[1]，面層材料采用的是碳纖維預(yù)浸料(把樹(shù)脂浸漬在碳纖維中制成片狀的疊層材料)[2]。結(jié)構(gòu)件90%由碳纖維、樹(shù)脂和蜂窩組成，其余10%由玻璃纖維、膠膜和油漆組成。因?yàn)樯a(chǎn)工藝存在缺陷，G公司每個(gè)月生產(chǎn)的結(jié)構(gòu)件中20%存在輕微質(zhì)量缺陷。經(jīng)過(guò)工藝工程師和質(zhì)量工程師的仔細(xì)檢查，查明引發(fā)缺陷的原因是在固化過(guò)程[3](碳纖維和蜂窩在一定溫度和壓力下復(fù)合的過(guò)程)中裝配區(qū)液態(tài)粘合樹(shù)脂流入蜂窩夾層[4]，從而導(dǎo)致裝配區(qū)域厚度低于公差下限0.1～0.5 mm左右。雖然力學(xué)試驗(yàn)和超聲波無(wú)損檢驗(yàn)結(jié)果表明，流入蜂窩的粘合樹(shù)脂對(duì)結(jié)構(gòu)件的力學(xué)性能和質(zhì)量沒(méi)有顯著影響，但未達(dá)標(biāo)的裝配區(qū)域厚度會(huì)導(dǎo)致裝配在結(jié)構(gòu)件上的金屬件和膠皮無(wú)法緊密連接在結(jié)構(gòu)件上，造成質(zhì)量隱患。經(jīng)過(guò)工程師和設(shè)計(jì)部門(mén)的反復(fù)溝通，確認(rèn)在現(xiàn)有工藝技術(shù)條件下粘合樹(shù)脂流入蜂窩是不可避免的情況，但是可以在不影響結(jié)構(gòu)件其他性能的前提下通過(guò)返修的方式來(lái)增加相關(guān)裝配區(qū)域的厚度。

圖1 碳纖維蜂窩夾層結(jié)構(gòu)

G公司目前積攢了200多件有質(zhì)量缺陷的結(jié)構(gòu)件，同時(shí)隨著生產(chǎn)的進(jìn)行，數(shù)量還在不斷增加。大量積壓的結(jié)構(gòu)件次品意味著公司需要付出不菲的交貨計(jì)劃推遲(違約)成本，同時(shí)公司的WIP成本(在制品成本)也隨之不斷增加。另外，結(jié)構(gòu)件次品需要占用大量的存儲(chǔ)空間，如不及時(shí)妥善處理和保管可能會(huì)影響正常生產(chǎn)，也可能造成這些次品受損甚至報(bào)廢。因此，為盡快完成積壓結(jié)構(gòu)件次品的返修任務(wù)，需要制訂科學(xué)合理的返修生產(chǎn)計(jì)劃。本文研究重點(diǎn)是結(jié)構(gòu)件次品的返修生產(chǎn)計(jì)劃問(wèn)題，首先對(duì)該問(wèn)題進(jìn)行了詳細(xì)描述，接著給出了該問(wèn)題的數(shù)學(xué)模型，然后設(shè)計(jì)了2個(gè)蟻群算法來(lái)求解該問(wèn)題，并采用算例驗(yàn)證所提算法的性能。

1 問(wèn)題定義和數(shù)學(xué)模型

結(jié)構(gòu)件次品的返修生產(chǎn)計(jì)劃問(wèn)題可以概括為：已知共有n個(gè)結(jié)構(gòu)件次品和m個(gè)返修時(shí)段，尋找一個(gè)最優(yōu)返修生產(chǎn)計(jì)劃，使得在所有返修時(shí)段內(nèi)安排的結(jié)構(gòu)件數(shù)量最大。

問(wèn)題假設(shè)如下：

1)結(jié)構(gòu)件的一次返修成功率為100%，這樣無(wú)需為同一結(jié)構(gòu)件次品安排二次返修。

2)結(jié)構(gòu)件一個(gè)返修區(qū)域的返修時(shí)間固定為t0，因此每個(gè)結(jié)構(gòu)件的返修時(shí)間與其返修區(qū)域的數(shù)量成正比。

表1 參數(shù)和變量

對(duì)于返修計(jì)劃建立如下模型：

(1)

(2)

Ej≥Ej+1j=1,2,…,m-1

(3)

式(1)為目標(biāo)函數(shù)，表示在m個(gè)返修時(shí)段內(nèi)，最大化返修結(jié)構(gòu)件的數(shù)量。式(2)表示在第j個(gè)返修時(shí)段內(nèi)，所有計(jì)劃返修結(jié)構(gòu)件的預(yù)計(jì)返修時(shí)間總和不能超過(guò)一個(gè)返修時(shí)段的時(shí)長(zhǎng)T。式(3)表示第j個(gè)返修時(shí)段的返修緊急程度指數(shù)應(yīng)大于第j+1個(gè)返修時(shí)段的返修緊急程度指數(shù)。

出貨延遲程度指數(shù)pi是按照結(jié)構(gòu)件i的出貨延遲日期來(lái)確定的延遲等級(jí)，分為3個(gè)等級(jí)，分別是正常出貨(0.1)，延遲出貨3個(gè)月以內(nèi)(0.3)，延遲出貨3個(gè)月以上(0.6)，每個(gè)等級(jí)的出貨延遲程度指數(shù)是根據(jù)對(duì)應(yīng)等級(jí)結(jié)構(gòu)件次品在結(jié)構(gòu)件次品總體中的比例確定的。ci是結(jié)構(gòu)件i在所有待返修結(jié)構(gòu)件中的相對(duì)WIP成本，由式(4)計(jì)算而得：

(4)

返修緊急程度指數(shù)ki是由結(jié)構(gòu)件i的出貨延遲程度指數(shù)pi和相對(duì)WIP成本ci加權(quán)平均得到的新指標(biāo)，體現(xiàn)了結(jié)構(gòu)件的返修綜合緊急程度，pi和ci的權(quán)重分別為w1和w2，ki由式(5)計(jì)算而得：

ki=w1pi+w2cii=1,2,…,n

(5)

返修緊急程度指數(shù)Ej是第j個(gè)時(shí)段內(nèi)所有結(jié)構(gòu)件返修緊急程度ki的總和，表示第j個(gè)返修時(shí)段的返修緊急程度指數(shù)，由式(6)計(jì)算而得：

(6)

2 蟻群優(yōu)化算法

蟻群優(yōu)化算法(AntColonyOptimization，ACO)，是一種用來(lái)尋找優(yōu)化路徑的概率型算法。它由意大利學(xué)者M(jìn)arcoDorigo等[5-6]于1991年提出，其靈感源于螞蟻在尋找食物過(guò)程中發(fā)現(xiàn)路徑的行為。蟻群算法是一種模擬進(jìn)化算法，初步研究表明該算法具有許多優(yōu)良的性質(zhì)。Dorigo等[7]在1997年又提出了一種具有全新機(jī)制的ACO算法——蟻群系統(tǒng)(AntColonySystem)，進(jìn)一步提高了ACO的性能。新蟻群算法的不同之處主要體現(xiàn)在3個(gè)方面：1)使用一種偽隨機(jī)比例機(jī)制選擇下一個(gè)節(jié)點(diǎn)，以尋求開(kāi)發(fā)當(dāng)前路徑與探索新路徑之間的平衡；2)信息素全局更新過(guò)程中只在屬于至今最優(yōu)路徑的邊上釋放信息素；3)新增信息素局部更新過(guò)程，即螞蟻每次經(jīng)過(guò)空間內(nèi)的某條邊時(shí)都會(huì)除去邊上一定量的信息素，以增加后續(xù)螞蟻探索其余路徑的可能性。

本章結(jié)構(gòu)件的返修生產(chǎn)計(jì)劃問(wèn)題是一個(gè)NP-hard問(wèn)題，這意味著當(dāng)問(wèn)題規(guī)模較大時(shí)，很難在可接受時(shí)間范圍內(nèi)求得精確解。因此，結(jié)合所研究的返修計(jì)劃問(wèn)題，提出了一個(gè)蟻群優(yōu)化算法，以在較短時(shí)間內(nèi)求得較優(yōu)的近似解。蟻群算法所涉及的參數(shù)符號(hào)及說(shuō)明如表2所示。

表2 蟻群算法參數(shù)說(shuō)明

蟻群算法的基本思路是：首先對(duì)信息素矩陣進(jìn)行初始化，然后通過(guò)多次迭代尋找最優(yōu)解。在每次迭代中，首先讓每只螞蟻隨機(jī)選擇第一個(gè)結(jié)構(gòu)件，然后按照狀態(tài)轉(zhuǎn)移規(guī)則選擇后續(xù)結(jié)構(gòu)件，并且每當(dāng)一只螞蟻k選擇一個(gè)結(jié)構(gòu)件i后，馬上進(jìn)行信息素的局部更新。當(dāng)所有螞蟻都構(gòu)建完自己的返修計(jì)劃后，選出本次迭代的最優(yōu)返修計(jì)劃Plan+，然后與存儲(chǔ)的至今最優(yōu)返修計(jì)劃Planmax比較，若Plan+優(yōu)于Planmax，則用Plan+替代Planmax，反之則保持Planmax不變，然后進(jìn)行信息素的全局更新，最后重復(fù)迭代操作直至最大迭代次數(shù)tmax。在蟻群搜索結(jié)束后，根據(jù)式(3)對(duì)最優(yōu)返修計(jì)劃Planmax按照返修緊急程度指數(shù)Ej從大到小排序。蟻群算法的關(guān)鍵在于信息素設(shè)置、返修計(jì)劃構(gòu)建方法、返修計(jì)劃評(píng)估以及信息素的更新，下面分別介紹這幾個(gè)關(guān)鍵環(huán)節(jié)。

2.1 信息素設(shè)置

信息素定義在任意一對(duì)結(jié)構(gòu)件i和j之間，表示在結(jié)構(gòu)件i后選擇結(jié)構(gòu)件j的傾向程度，對(duì)應(yīng)的信息素濃度為τij。設(shè)立一個(gè)n×n信息素矩陣，存儲(chǔ)所有信息素信息。初始化信息素矩陣時(shí)，將信息素矩陣中的值賦為一個(gè)較小的正值τ0。

2.2 構(gòu)建返修計(jì)劃

返修計(jì)劃構(gòu)建采用串行方式進(jìn)行，即在一次迭代過(guò)程中，每只螞蟻依次構(gòu)建一個(gè)完整的返修計(jì)劃，這樣每次迭代共產(chǎn)生ants個(gè)返修計(jì)劃。首先螞蟻k隨機(jī)選擇第一個(gè)結(jié)構(gòu)件i，然后螞蟻k根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則確定下一個(gè)要選擇的結(jié)構(gòu)件j，選擇的過(guò)程依賴信息素和啟發(fā)式信息的共同作用，每只螞蟻都按照這種方式選擇結(jié)構(gòu)件，直到所有螞蟻都構(gòu)建完成結(jié)構(gòu)件返修計(jì)劃。在第2.1節(jié)中已對(duì)信息素做了說(shuō)明，下面將對(duì)啟發(fā)式信息進(jìn)行定義和使用。在選擇結(jié)構(gòu)件時(shí)，啟發(fā)式信息將引導(dǎo)螞蟻優(yōu)先選擇符合模型目標(biāo)的結(jié)構(gòu)件。定義在第t次迭代中在結(jié)構(gòu)件i后選擇結(jié)構(gòu)件j的啟發(fā)式信息為ηij(t)：

(7)

(8)

(9)

相比于機(jī)制一，機(jī)制二考慮了另外一個(gè)啟發(fā)式信息，即考慮了結(jié)構(gòu)件的返修緊急程度priorityj(t)，目的是優(yōu)先安排更為緊急的待返修結(jié)構(gòu)件。機(jī)制二如下：

(10)

(11)

在第t次迭代中螞蟻k選擇結(jié)構(gòu)件j后，計(jì)算返修時(shí)段m已用時(shí)間，確保已用時(shí)間小于返修時(shí)段固定時(shí)長(zhǎng)。

2.3 返修計(jì)劃評(píng)估

返修計(jì)劃優(yōu)劣的評(píng)價(jià)指標(biāo)為結(jié)構(gòu)件總數(shù)numberk(t)。每次迭代完成后，比較每只螞蟻所構(gòu)建的返修計(jì)劃優(yōu)劣，得到本次迭代的最優(yōu)返修計(jì)劃Plan+，與存儲(chǔ)的至今最優(yōu)返修計(jì)劃Planmax進(jìn)行比較，若Plan+優(yōu)于Planmax，則用Plan+替代Planmax，反之則保持Planmax不變。

2.4 信息素更新

2.4.1 信息素局部更新

為增加后續(xù)螞蟻探索其他路徑的可能性，在返修時(shí)段計(jì)劃的構(gòu)建中，對(duì)于每只螞蟻，每當(dāng)選擇一個(gè)結(jié)構(gòu)件j后(前一個(gè)結(jié)構(gòu)件為i)，將立刻對(duì)結(jié)構(gòu)件i和結(jié)構(gòu)件j之間的信息素τij(t)進(jìn)行局部更新。如式(12)所示：

τij(t)=(1-ρ1)τij(t)+ρ1τ0

(12)

式中，ρ1是一個(gè)[0, 1]區(qū)間內(nèi)的參數(shù)。

2.4.2 信息素全局更新

在每次迭代后，按照優(yōu)化目標(biāo)對(duì)所有螞蟻構(gòu)建的返修時(shí)段計(jì)劃進(jìn)行評(píng)估，然后進(jìn)行信息素的全局更新。在信息素全局更新時(shí)，只對(duì)至今最優(yōu)返修時(shí)段計(jì)劃進(jìn)行信息素的釋放。如式(13)和(14)所示：

τij(t+1)=(1-ρ2)τij(t)+ρ2Δτij(t)

(13)

(14)

式中：ρ2是一個(gè)[0, 1]區(qū)間內(nèi)的參數(shù)；number(Planmax)為搜索得到的至今最優(yōu)返修計(jì)劃序列的結(jié)構(gòu)件總數(shù)。

蟻群算法執(zhí)行流程如下：

3 算例驗(yàn)證與結(jié)果分析

3.1 算例設(shè)計(jì)

通過(guò)設(shè)計(jì)算例來(lái)驗(yàn)證文中所提蟻群算法的性能。算例設(shè)計(jì)所用參數(shù)根據(jù)G公司實(shí)際生產(chǎn)情況設(shè)定，如表3所示。

表3 算例參數(shù)

待返修結(jié)構(gòu)件總數(shù)設(shè)為100或200個(gè)。G公司結(jié)構(gòu)件共有14個(gè)型號(hào)。型號(hào)比例采用D1和D2兩種，D1為平均比例，即每種型號(hào)的比例相同，表示在一段較短時(shí)間內(nèi)，每種型號(hào)出現(xiàn)質(zhì)量缺陷的比例相同；D2為累積比例，即每種型號(hào)的比例根據(jù)實(shí)際累積情況產(chǎn)生，表示在一段較長(zhǎng)時(shí)間內(nèi)，G公司累積了大量的質(zhì)量缺陷結(jié)構(gòu)件，不同型號(hào)之間的比例不盡相同。返修生產(chǎn)計(jì)劃期包括3周和6周(每周為一個(gè)返修時(shí)段)兩種，對(duì)應(yīng)于100和200個(gè)待返修結(jié)構(gòu)件。另外待返修結(jié)構(gòu)件預(yù)計(jì)返修時(shí)間有4種，預(yù)計(jì)返修時(shí)間根據(jù)返修區(qū)域的數(shù)量確定。預(yù)計(jì)返修時(shí)間比例為d1和d2，d1為固定返修時(shí)間比例，表示通常情況下，每種型號(hào)的返修區(qū)域數(shù)量確定，所以返修時(shí)間也就隨之確定。d2為累積返修時(shí)間比例，即根據(jù)實(shí)際累積結(jié)構(gòu)件返修區(qū)域數(shù)量確定的返修時(shí)間比例，表示在一段較長(zhǎng)時(shí)間內(nèi)，經(jīng)過(guò)累積，每種型號(hào)的返修區(qū)域數(shù)量不固定，因此返修時(shí)間也就隨之變化。

結(jié)構(gòu)件型號(hào)和返修時(shí)間比例如表4所示。在累積返修時(shí)間比例d2中，以PANEL10為例，40(75%) 80(25%)表示返修時(shí)間為40min的PANEL10占比75%，返修時(shí)間為80min的PANEL10占比25%，后面所有型號(hào)依此類(lèi)推。

表4 型號(hào)和返修時(shí)間比例

出貨延遲程度指數(shù)比例為P1和P2，如表5所示。P1為平均比例，即3個(gè)等級(jí)的出貨延遲程度比例相同，如100件待返修結(jié)構(gòu)件中，3個(gè)等級(jí)的結(jié)構(gòu)件各占33.3%。P2為累積比例，即3個(gè)等級(jí)的出貨延遲程度比例不同，具體比例由實(shí)際累積結(jié)構(gòu)件中情況確定。同時(shí)P1和d1，P2和d2之間互相對(duì)應(yīng)。其中P1和d1均為平均比例，表示在較短時(shí)間內(nèi)返修時(shí)間和出貨延遲程度的比例，而P2和d2均為累積比例，表示在較長(zhǎng)時(shí)間內(nèi)兩個(gè)指標(biāo)的比例。

表5 出貨延遲程度指數(shù)比例

根據(jù)以上參數(shù)通過(guò)C++程序隨機(jī)產(chǎn)生算例，結(jié)構(gòu)件數(shù)量、返修時(shí)間分布和出貨延遲程度分布經(jīng)排列組合產(chǎn)生8個(gè)算例，如表6所示。

表6 算例組合

3.2 算法性能驗(yàn)證與分析

本文設(shè)計(jì)的兩種算法均采用微軟公司的VisualStudio2012C++編譯，實(shí)驗(yàn)環(huán)境為IntelCorei5CPU@ 2.5GHz, 3GBRAM，Windows7系統(tǒng)。蟻群算法參數(shù)設(shè)置如下：

機(jī)制一：

ants = 10，tmax= 200，τ0= 0.005，ρ1= 0.01，ρ2= 0.01，α = 1，β = 3，q0= 0.9，w1= 10，w2= 100，T = 2 400min。

機(jī)制二：

ants = 10，tmax= 200，τ0= 0.005，ρ1= 0.01，ρ2= 0.01，α = 1，β = 3，ε = 3，w1= 10，w2= 100，q0= 0.9， T = 2 400min。

采用算法一和算法二基于以上參數(shù)設(shè)置運(yùn)行算例，每個(gè)算例運(yùn)行3次，取平均值作為該算例的運(yùn)行值。兩種算法的結(jié)果如表7、表8、圖2～圖6所示。

表7 算法一運(yùn)行結(jié)果

表8 算法二運(yùn)行結(jié)果

圖2 平均返修結(jié)構(gòu)件數(shù)量

從圖2可以看出，無(wú)論是100個(gè)結(jié)構(gòu)件，還是200個(gè)結(jié)構(gòu)件，算法一的平均返修數(shù)量均高于算法二。進(jìn)一步分析，在100個(gè)結(jié)構(gòu)件情況下，對(duì)于4個(gè)算例組合，算法一比算法二分別高2.75%，6.69%，4.98%，11.65%；在200個(gè)結(jié)構(gòu)件情況下，算法一比算法二分別高4.36%，6.64%，2.93%，6.60%。從上述數(shù)據(jù)中可以發(fā)現(xiàn)算法一和算法二最大差距為11.65%，最小差距也有2.75%。從算法一和算法二的偽隨機(jī)選擇機(jī)制來(lái)分析，造成這種差距的原因是算法二在啟發(fā)式信息中增加了結(jié)構(gòu)件返修緊急程度指數(shù)，螞蟻會(huì)優(yōu)先選擇緊急程度指數(shù)大的結(jié)構(gòu)件。而通常情況下，緊急程度指數(shù)大的結(jié)構(gòu)件其返修時(shí)間也較長(zhǎng)，所以算法二的平均返修數(shù)量低于算法一。

圖3 返修時(shí)間平均利用率

從圖3可以看出，在100個(gè)結(jié)構(gòu)件，D2d2P2算例組合情況下，算法一的時(shí)間利用率高于算法二0.55%，其余情況下，算法二的時(shí)間利用率均高于算法一。算法一和算法二全部算例的平均返修時(shí)間利用率分別為98.27%和99.10%，均大于98%，兩者之間相差不大。

圖4 返修WIP成本和返修WIP成本占比

從圖4可以看出，通常情況下，算法二的返修WIP成本都比算法一小，只有在100個(gè)結(jié)構(gòu)件，D2d1P1算例組合的情況下，算法二的返修WIP成本才略大于算法一。從返修WIP成本占總WIP成本比例來(lái)看，100個(gè)結(jié)構(gòu)件的情況，算法一的均值為80.45%，算法二為78.09%，算法一同比增加2.36%；200個(gè)結(jié)構(gòu)件的情況，算法一的均值為82.08%，算法二為76.79%，算法一同比增加5.29%。因此在返修WIP成本方面，算法一要優(yōu)于算法二。另外，算法一平均運(yùn)行時(shí)間為3.46s(100)和13.70s(200)，算法二為64.42s(100)和505.93s(200)。二者之間差異較大，其中運(yùn)行時(shí)間最大值為505.93s，對(duì)于在返修時(shí)間段只進(jìn)行一次的返修計(jì)劃來(lái)說(shuō)，2個(gè)算法都是可以接受的。

如圖5所示，結(jié)構(gòu)件數(shù)量為100時(shí)，2個(gè)算法的3種出貨延遲等級(jí)的結(jié)構(gòu)件返修率有一個(gè)明顯的趨勢(shì)，即算法一的正常出貨結(jié)構(gòu)件返修率均大于算法二的相應(yīng)返修率；在圖5(b)中，算法一和算法二互有輸贏，沒(méi)有明顯的優(yōu)劣趨勢(shì)；在圖5(c)中，算法一延遲出貨3個(gè)月以上的結(jié)構(gòu)件返修率都小于算法二的相應(yīng)返修率。在圖6中，結(jié)構(gòu)件數(shù)量為200時(shí)，也有同樣的趨勢(shì)。

圖5 結(jié)構(gòu)件數(shù)量為100時(shí)3個(gè)出貨延遲等級(jí)結(jié)構(gòu)件返修率

從具體的數(shù)值來(lái)看，算法二延遲出貨3個(gè)月以上結(jié)構(gòu)件的平均返修率為98.19%(100)和100%(200)，而算法一只有72.5%(100)和68.32%(200)。至于延遲出貨3個(gè)月以內(nèi)結(jié)構(gòu)件的平均返修率，算法一為76.98%(100)和83.19%(200)，算法二為84.1%(100)和83.92%(200)。因此可以得出結(jié)論，算法二計(jì)劃返修更多的出貨緊急的結(jié)構(gòu)件。

4 結(jié)束語(yǔ)

本文研究了返修工序的計(jì)劃問(wèn)題，通過(guò)綜合考慮返修時(shí)間、返修時(shí)段、WIP成本和出貨延遲程度等相關(guān)約束，確定了在給定返修時(shí)段內(nèi)最大化返修結(jié)構(gòu)件數(shù)量的目標(biāo)。在確定了目標(biāo)的基礎(chǔ)上，對(duì)返修工序的計(jì)劃問(wèn)題進(jìn)行了數(shù)學(xué)建模，給出了一個(gè)0-1整數(shù)規(guī)劃模型，并采用蟻群算法對(duì)該模型進(jìn)行求解，在蟻群算法中設(shè)計(jì)了兩種不同的偽隨機(jī)選擇規(guī)則，按照實(shí)際累積結(jié)構(gòu)件的情況設(shè)計(jì)了相關(guān)算例，并針對(duì)兩個(gè)蟻群算法，計(jì)算并驗(yàn)證了上述算法。通過(guò)算例分析，得出如下結(jié)論：

1)在最大化返修結(jié)構(gòu)件數(shù)量方面，算法一的表現(xiàn)優(yōu)于算法二。

2)在返修時(shí)間利用率方面，2個(gè)蟻群算法并無(wú)顯著差異。

3)在減少公司W(wǎng)IP成本方面，算法一的表現(xiàn)優(yōu)于算法二。

4)在正常出貨結(jié)構(gòu)件返修率方面，算法一計(jì)算結(jié)果優(yōu)于算法二，但在權(quán)重較大的延遲出貨3個(gè)月以內(nèi)和以上結(jié)構(gòu)件返修率方面，結(jié)果相反，算法二計(jì)算結(jié)果更佳。從總體上來(lái)講，算法二計(jì)劃了更多的出貨緊急的結(jié)構(gòu)件，而算法一計(jì)劃了更多正常出貨的結(jié)構(gòu)件，因此算法二的計(jì)算結(jié)果更好。

綜上所述，考慮到目前G公司的實(shí)際情況，即累積了大量的待返修結(jié)構(gòu)件，已經(jīng)沒(méi)有足夠空間來(lái)安全存儲(chǔ)新的待返修結(jié)構(gòu)件，同時(shí)大量的待返修結(jié)構(gòu)件帶來(lái)了嚴(yán)重的WIP成本和出貨壓力。目前的重點(diǎn)是盡可能多地返修結(jié)構(gòu)件，以避免發(fā)生結(jié)構(gòu)件無(wú)處存放導(dǎo)致受損或正常生產(chǎn)結(jié)構(gòu)件的存放受影響的情況。因此將返修計(jì)劃分為兩個(gè)階段，第一階段采用算法一進(jìn)行返修計(jì)劃，在解決存放空間不足的問(wèn)題后，第二階段采用算法二進(jìn)行返修計(jì)劃，以達(dá)到減少WIP成本和出貨延遲情況的目標(biāo)。

[1] 馬曉坤, 楊曉峰, 姜婧, 等. 熱固性碳纖維預(yù)浸料用環(huán)氧類(lèi)基體樹(shù)脂[J]. 彈性體, 2013(3): 83-88.

[2] 唐桂云, 王云飛, 王寶瑞. 碳纖維復(fù)合材料蜂窩夾層結(jié)構(gòu)的無(wú)損檢測(cè)方法研究[J]. 纖維復(fù)合材料, 2011(1): 30-32.

[3]KATNAMKB,DASILVALFM,YOUNGTM.Bondedrepairofcompositeaircraftstructures:Areviewofscientificchallengesandopportunities[J].ProgressinAerospaceSciences, 2013, 61: 26-42.

[4] RICCIO A, DI FELICE G, SCARAMUZZINO F, et al. A practical tool for the preliminary design of bonded composite repairs[J]. Applied Composite Materials, 2014, 21(3): 495-509.

[5] COLORNI A, DORIGO M, MANIEZZO V. Distributed optimization by ant colonies[C]//Proceedings of The First European Conference on Artificial Life, 1991, 142: 134-142.

[6] DORIGO M, MANIEZZO V, COLORNI A. The ant system: an autocatalytic optimizing process[R]. Technical Report, 1991.

[7] DORIGO M, STüTZLE T. Ant colony optimization[M]. London: The MIT Press, 2004.

[8] 崔海坡, 溫衛(wèi)東, 崔海濤. 復(fù)合材料層合板沖擊損傷及剩余強(qiáng)度研究進(jìn)展[J]. 材料科學(xué)與工程學(xué)報(bào), 2005, 23(3): 465-472.

姚智騫(1992-)，男，碩士研究生在讀，主要研究方向?yàn)樯a(chǎn)計(jì)劃調(diào)度。

Repair Scheduling for Composite Structural Parts Based on Ant Colony Algorithm

YAO Zhi-qian

(SchoolofMechanicalEngineering,SoutheastUniversity,Nanjing211189,China)

In order to solve the quality defects problem of composite structural parts in manufacturing, G Company sets up a repair process. For the scheduling problem in the repair process, a 0-1 integer programming model is developed with the objective of maximizing the number of repair parts. The shipping delay and high WIP cost are considered at the same time. Two pseudo-random selection mechanism are proposed based on ant colony algorithm. Problem instances with different parameter combinations are used to test the performance of the proposed algorithms. Computation results show that algorithm one is better in aspect of repair parts number, but algorithm two outperforms algorithm one in terms of reducing shipping delay and WIP cost.

repair scheduling; integer programming; ant colony algorithm; pseudo-random selection mechanism

2016-11-18

TH166；TH18

A

1008-5300(2017)02-0048-08