張 煒，王麗娟，彭精立

（廈門城市職業(yè)學(xué)院智能制造學(xué)院，福建 廈門 361008）

0 引言

工程實(shí)踐中的許多重要決策問(wèn)題往往需要在不同的約束條件下同時(shí)處理多個(gè)相互沖突的目標(biāo)。即多目標(biāo)優(yōu)化問(wèn)題（Multi-objective Optimization Problem，MOP）[1-2]。MOP 的目標(biāo)涉及相同或不同的一組決策變量，這些變量是相互約束的。由于每個(gè)目標(biāo)的工程意義和尺寸不同，導(dǎo)致解決MOP存在一定的難度。

MOP 的目的是在優(yōu)化目標(biāo)之間進(jìn)行權(quán)衡。傳統(tǒng)的解決方案是將其轉(zhuǎn)化為一個(gè)單一的目標(biāo)問(wèn)題。常見(jiàn)的方法有加權(quán)和法[3]、目標(biāo)規(guī)劃法[4]、e約束法等[5]。例如，張波等[6]提出了多規(guī)則融合算法，有效地表征了裝配工藝和有限資源等剛性約束。通過(guò)航空發(fā)動(dòng)機(jī)脈動(dòng)式裝配過(guò)程實(shí)例驗(yàn)證，證明了所提算法在隨機(jī)擾動(dòng)、反復(fù)迭代和群體計(jì)算等方面的優(yōu)勢(shì)。易建洋等[7]建立混裝線平衡和物料配送聯(lián)合優(yōu)化數(shù)學(xué)模型。提出遺傳算法在仿真軟件里的應(yīng)用仿真，并通過(guò)實(shí)例驗(yàn)證方法研究的有效性。針對(duì)訂單分配與排序時(shí)存在的分配方案不合理、交期久等問(wèn)題，以最小化最大完成時(shí)間和拖期時(shí)間為目標(biāo)函數(shù)的訂單分配和排序兩級(jí)目標(biāo)優(yōu)化模型，利用基于參考點(diǎn)的快速非支配遺傳算法優(yōu)化求解得到優(yōu)化方案[8]。針對(duì)MOP，沒(méi)有單一的解決方案可以使所有目標(biāo)同時(shí)達(dá)到最優(yōu)。各類優(yōu)化方法將不可避免地削弱一些目標(biāo)。

因此，本文首先分析了多個(gè)目標(biāo)之間的層次關(guān)系。將多目標(biāo)轉(zhuǎn)化為多個(gè)單目標(biāo)函數(shù)進(jìn)行分層優(yōu)化，使得優(yōu)化過(guò)程更符合實(shí)際情況。

MOP 可以通過(guò)雙層編程來(lái)解決。雙層規(guī)劃廣泛應(yīng)用于工程設(shè)計(jì)[9]、經(jīng)濟(jì)管理和資源分配[10-12]。例如，Calvete和Gale[13]研究了上下兩級(jí)線性分式的雙層規(guī)劃問(wèn)題，并給出了相應(yīng)的遺傳算法。針對(duì)多條異構(gòu)混裝線之間加工能力、作業(yè)時(shí)間不等效的特征，提出面向柔性定制的并行不等效生產(chǎn)計(jì)劃模型。提出一種結(jié)合Pareto 前沿解的改進(jìn)遺傳算法，采用小生境技術(shù)保證種群多樣性[14]。Charnes 和Cooper[15]將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為兩個(gè)線性規(guī)劃問(wèn)題。通過(guò)求解兩個(gè)線性問(wèn)題得到了相應(yīng)分式規(guī)劃的最優(yōu)解。不同的算法與雙層規(guī)劃方法相結(jié)合促進(jìn)了多目標(biāo)優(yōu)化問(wèn)題的不斷發(fā)展。本文以某混裝線規(guī)劃為例說(shuō)明了雙層規(guī)劃的工程應(yīng)用。針對(duì)該模型提出了一種嵌套遺傳算法。

1 混裝線平衡和排序

假設(shè)M系列產(chǎn)品需要在一個(gè)生產(chǎn)計(jì)劃周期T內(nèi)生產(chǎn)。每個(gè)型號(hào)的總產(chǎn)品需求為DM，m∈{1,2,…,m,…,M}。每個(gè)產(chǎn)品的每個(gè)任務(wù)的優(yōu)先級(jí)關(guān)系是預(yù)定義的。在一定的優(yōu)化條件下，需要確定所有產(chǎn)品的生產(chǎn)順序。如果不同產(chǎn)品的總需求的最大公約數(shù)是g；最小生產(chǎn)周期單位為dm，可以表示為向量（d1，d2，…，dm，…，dM）。在計(jì)劃周期時(shí)間內(nèi)，只訂購(gòu)具有最小生產(chǎn)周期單元的產(chǎn)品，并重復(fù)g個(gè)過(guò)程。該規(guī)劃包含兩個(gè)問(wèn)題：平衡和排序。

大多數(shù)關(guān)于混裝線平衡的研究都是基于綜合作業(yè)優(yōu)先圖，它將多個(gè)產(chǎn)品的負(fù)載平衡轉(zhuǎn)化為單個(gè)產(chǎn)品的裝配線平衡問(wèn)題[16-17]。例如，吳永明等[18]針對(duì)產(chǎn)品需求多樣化、工藝及設(shè)備動(dòng)態(tài)變化，裝配線平衡方案需不斷調(diào)整，提出裝配線演進(jìn)平衡方法，通過(guò)改進(jìn)粒子群優(yōu)化算法進(jìn)行優(yōu)化，所提算法增加粒子的多樣性和搜索能力，加快算法的搜索速度。以一個(gè)生產(chǎn)實(shí)例驗(yàn)證了該方法的有效性和可行性。

對(duì)于混裝線排序問(wèn)題，傳統(tǒng)的策略是使用遺傳算法[19]、蟻群算法[20]等。例如，江新利等[21]研究具備有限緩沖特征的兩階段排序問(wèn)題，考慮生產(chǎn)系統(tǒng)的發(fā)泡設(shè)備約束，分別對(duì)預(yù)裝線與發(fā)泡線模具排序進(jìn)行研究，使二者盡量匹配，減少在制品庫(kù)存數(shù)量。

混裝線平衡是混裝線排序的基礎(chǔ)，排序的結(jié)果用于評(píng)估平衡的好壞。姜東等[22]針對(duì)混流裝配線平衡排序優(yōu)化問(wèn)題，提出了一種多目標(biāo)模擬退火算法。提出的模擬退火算法在初始化中將啟發(fā)式任務(wù)分配規(guī)則融入平衡問(wèn)題，根據(jù)產(chǎn)品投產(chǎn)需求隨機(jī)生成產(chǎn)品序列；通過(guò)測(cè)試標(biāo)準(zhǔn)問(wèn)題實(shí)驗(yàn)，對(duì)所提出的算法進(jìn)行參數(shù)校驗(yàn)。

2 多目標(biāo)雙層優(yōu)化模型

平衡與排序的優(yōu)化設(shè)計(jì)問(wèn)題本質(zhì)上是一個(gè)雙層規(guī)劃問(wèn)題[23]?；陔p層規(guī)劃模型的理論框架，可以建立問(wèn)題的決策機(jī)制。

2.1 上層優(yōu)化問(wèn)題

模型的上層需要對(duì)產(chǎn)品族的任務(wù)分配做出決策，即在滿足作業(yè)優(yōu)先順序的前提下，將產(chǎn)品族任務(wù)分配給工作站。評(píng)估的基本標(biāo)準(zhǔn)是工作站內(nèi)部工作負(fù)載平衡、工作站之間工作負(fù)載平衡和動(dòng)態(tài)平衡的綜合利益。

混裝線平衡。在混裝線中，不同產(chǎn)品的類似任務(wù)可能具有不同的操作時(shí)間。產(chǎn)品的每個(gè)任務(wù)也可以有不同的操作時(shí)間。因此，當(dāng)這些任務(wù)中的一些被分配給工作站時(shí)，工作站的工作負(fù)載時(shí)間可能達(dá)到給定的循環(huán)時(shí)間。因此，需要考慮每個(gè)工作站上不同產(chǎn)品的工作負(fù)載的平衡，以及不同工作站之間的工作負(fù)載平衡。所提出的工作站內(nèi)部工作負(fù)載平衡和工作站之間工作負(fù)載平衡的目標(biāo)分別用式（1）和式（2）表示。

式中：J1為工作站內(nèi)部工作負(fù)載平衡；J2為工作站之間工作負(fù)載平衡；M為產(chǎn)品族混裝線上生產(chǎn)的產(chǎn)品種類；m為產(chǎn)品族混裝線上生產(chǎn)的第m種產(chǎn)品；i為產(chǎn)品族的第i個(gè)任務(wù)；S為產(chǎn)品族混裝線的站點(diǎn)數(shù)量；j、k分別為產(chǎn)品族混裝線上的第j、k個(gè)站點(diǎn)；Tmj、Tmk為第m種產(chǎn)品分配到j(luò)、k工作站的總工作時(shí)間；qm為第種產(chǎn)品需求百分比；tim為第m產(chǎn)品第i個(gè)任務(wù)的作業(yè)時(shí)間；Qim為加權(quán)系數(shù)；為分配到j(luò)站內(nèi)的所有任務(wù)的加權(quán)平均作業(yè)時(shí)間。

2.2 下層優(yōu)化問(wèn)題

混裝線排序。由于不同產(chǎn)品的類似任務(wù)的操作時(shí)間并不總是相同的，當(dāng)這些任務(wù)分配到一個(gè)工作站時(shí)，不同的排產(chǎn)順序會(huì)導(dǎo)致不同的等待時(shí)間。假設(shè)混裝線上的工作站的工作時(shí)間是z工作站中最大的，則其他工作站必須等待工作站完成工作，然后才能整體移動(dòng)。因此，在每個(gè)工作站中，每個(gè)工作站的工作時(shí)間與該狀態(tài)下工作站的最大工作時(shí)間之間的平衡是需要考慮的目標(biāo)函數(shù)。目標(biāo)函數(shù)設(shè)置如式（3）所示。

式中：J3為每個(gè)工作站的工作時(shí)間與該狀態(tài)下工作站的最大工作時(shí)間之間的平衡；tzk為z狀態(tài)下k工作站分配到的任務(wù)的作業(yè)時(shí)間；maxtzk為z狀態(tài)下的所有工作站分配到的任務(wù)的作業(yè)時(shí)間的最大值；d為產(chǎn)品族各產(chǎn)品需求最小比例集之和。

上層目標(biāo)函數(shù)考慮了混裝線的平衡和排序問(wèn)題。本文以工作站內(nèi)部工作負(fù)載平衡、工作站間工作負(fù)載平衡和動(dòng)態(tài)平衡之間的最小乘積為上層目標(biāo)函數(shù)，如式（4）所示。

模型的下層是混裝線的投產(chǎn)排序決策。排序決定了每個(gè)工作站的負(fù)荷水平和材料需求的進(jìn)度，這些都與成本有關(guān)。目標(biāo)函數(shù)可以用式（3）來(lái)表示。

2.3 雙層優(yōu)化

基于以上對(duì)上下層目標(biāo)需求的分析，可以建立混裝線平衡和排序的兩級(jí)優(yōu)化模型：

3 嵌套遺傳算法

問(wèn)題的變量可以分為兩部分：平衡決策變量和排序決策變量。每組平衡決策變量對(duì)應(yīng)于一組最優(yōu)排序決策變量。兩組變量處于不同的層級(jí)。如果使用經(jīng)典的遺傳算法來(lái)求解，收斂速度會(huì)很慢，并且可能很難收斂到全局最優(yōu)解。為了克服經(jīng)典遺傳算法的缺點(diǎn)，加快收斂速度，將染色體分為兩段，分層次進(jìn)行嵌套搜索。

3.1 平衡遺傳算子設(shè)計(jì)

平衡遺傳算子的設(shè)計(jì)主要包含以下4步。

（1）為了解決每個(gè)工作站中每個(gè)產(chǎn)品的任務(wù)分配，即求解變量Xijm以實(shí)現(xiàn)混裝線平衡，本文采用了基于操作序列的表達(dá)式，并使用浮點(diǎn)編碼方法。對(duì)于給定的產(chǎn)品m，任務(wù)i被分配給工作站j。所有任務(wù)形成一個(gè)任務(wù)序列，完成任務(wù)序列的工作站數(shù)量就是解決的問(wèn)題代碼，如圖1所示。

圖1 編碼和解碼

（2）初始化種群，即生成一系列符合條件的個(gè)體。由于混裝線上同時(shí)生產(chǎn)m種不同的產(chǎn)品，因此需要將每種產(chǎn)品的所有操作任務(wù)分別分配到所有工作站。

（3）在選擇操作中，使用最優(yōu)保存策略和輪盤賭。最優(yōu)保存策略將幾個(gè)具有高度適應(yīng)性的個(gè)體直接復(fù)制到下一代，而其他個(gè)體則使用輪盤選擇。在輪盤賭方法中，每個(gè)個(gè)體進(jìn)入下一代的概率等于其適應(yīng)度值與該個(gè)體在整個(gè)種群中的適應(yīng)度值之和的比率。本文使用目標(biāo)函數(shù)F（Y，X）的倒數(shù)作為適應(yīng)度函數(shù)。

（4）交叉和變異如圖2 所示。采用兩點(diǎn)交叉法，從選擇操作產(chǎn)生的個(gè)體中選擇兩條染色體（如圖2（a）所示），并在染色體上任意確定兩個(gè)交叉點(diǎn)。兩條染色體在交叉處被分成3 部分。父代1 染色體的中間染色體（3，6，2）按父代2 染色體（2，6，3）的順序排列，形成新的子代1。類似地，父代2染色體的中間基因（7，4，6）按照父代1 染色體（4，6，7）的順序排列，形成新的子代2。為了避免過(guò)早收斂和陷入局部最優(yōu)，在滿足優(yōu)先級(jí)約束關(guān)系的前提下，采用了交叉變異方法。從種群中任意選擇個(gè)體的任何染色體（任務(wù)）進(jìn)行變異，在交換之后，它不會(huì)違反任務(wù)之間的關(guān)系（圖2（b））。

圖2 交叉和變異

3.2 排序遺傳算子設(shè)計(jì)

排序遺傳算子設(shè)計(jì)如下。

（1）在最小生產(chǎn)周期單元中，生產(chǎn)序列的編碼采用浮點(diǎn)編碼方式，如圖3所示。

圖3 排序的編碼

（2）在種群初始化過(guò)程中，隨機(jī)產(chǎn)生了一個(gè)具有個(gè)體數(shù)量P的排序種群。目標(biāo)函數(shù)是適應(yīng)度函數(shù)J3。本文仍然使用輪盤賭來(lái)選擇和留住最優(yōu)秀的個(gè)體。

（3）至于交叉，使用基于切割點(diǎn)隨機(jī)交叉的方法從隨機(jī)生成的排序群體中隨機(jī)選擇兩個(gè)父代個(gè)體。選擇一個(gè)染色體位置作為這兩個(gè)個(gè)體的切割點(diǎn)，并將它們切割成前一部分和后一部分，如圖4（a）所示。從父代2 中逐個(gè)搜索滿足父代1 后端序列的染色體，并將其作為子代1 的后端。父代2 的剩余染色體被保留為子代1的早期染色體。

圖4 排序群體的交叉和變異

關(guān)于突變，本文使用反轉(zhuǎn)突變方法（圖4（b）），在父代染色體上隨機(jī)產(chǎn)生兩個(gè)突變點(diǎn)，并反轉(zhuǎn)中間部分的基因序列，以獲得新一代染色體。

3.3 用于雙層規(guī)劃的嵌套遺傳算法

針對(duì)上述雙層優(yōu)化解的直接求解方法，提出了一種嵌套遺傳算法用以生成X和Y。該算法分為上層和下層，分別設(shè)計(jì)用于平衡和排序。具體流程如圖5所示。

圖5 嵌套遺傳算法流程

步驟1：初始化種群，并根據(jù)上層變量大小隨機(jī)生成種群個(gè)數(shù)N。

步驟2：確定種群是否滿足上層約束條件，如果是，則將參數(shù)代入下層；如果沒(méi)有，則將適應(yīng)度設(shè)置為零，轉(zhuǎn)移到步驟3。

步驟3：確定是否達(dá)到最大迭代次數(shù)，如果達(dá)到，記錄最佳值，然后進(jìn)入步驟4；如果沒(méi)有，則進(jìn)入排序、選擇、交叉和突變的過(guò)程，然后轉(zhuǎn)入步驟2；將上層可行個(gè)體引入下層，并初始化下層群體Y（X）。

步驟4：驗(yàn)證基礎(chǔ)種群的可行性，如果可行，進(jìn)行適應(yīng)性評(píng)估；如果不可行，請(qǐng)將適應(yīng)度設(shè)置為0。

步驟5：確定較低層次的種群是否達(dá)到最大迭代次數(shù)，如果達(dá)到，則記錄最低個(gè)體和最優(yōu)值；如果沒(méi)有，則返回步驟4并重復(fù)，直到達(dá)到最大迭代次數(shù)。

步驟6：將下層的最優(yōu)個(gè)體和最優(yōu)值J3轉(zhuǎn)移到上層，評(píng)估適合度值。

步驟7：確定種群是否達(dá)到了最大迭代次數(shù)，如果達(dá)到，則記錄最優(yōu)解和最優(yōu)值；如果沒(méi)有，則重復(fù)步驟3，直到達(dá)到最大迭代次數(shù)。

4 應(yīng)用分析

以某客車焊接車間混焊接生產(chǎn)線生產(chǎn)的一系列A、B、C型客車為研究對(duì)象，客車產(chǎn)品族的綜合作業(yè)優(yōu)先圖如圖6所示。在生產(chǎn)計(jì)劃周期內(nèi)，3種產(chǎn)品的計(jì)劃產(chǎn)量分別為DA=8、DB=12、DC=8。因此，在最小生產(chǎn)周期內(nèi)，每種產(chǎn)品的需求分別為dA=DA/4=2，dB=DA/4=3，dC=DA/4=2。每個(gè)產(chǎn)品的任務(wù)時(shí)間如表1所示。

表1 產(chǎn)品族工序作業(yè)時(shí)間

圖6 裝配作業(yè)優(yōu)先圖

為了證明嵌套遺傳算法的有效性，選擇了傳統(tǒng)的遺傳算法和粒子群算法來(lái)解決上述問(wèn)題。傳統(tǒng)的遺傳算法使用順序優(yōu)化方法來(lái)解決這個(gè)問(wèn)題。首先，求解平衡的最優(yōu)值。其次，在平衡的基礎(chǔ)上，求解排序的最優(yōu)值。另外，使用粒子群算法的“歸一化”方法同時(shí)求解了J1J2J3。與嵌套遺傳算法不同，在求解過(guò)程中沒(méi)有交互過(guò)程，即平衡方案只對(duì)應(yīng)于一個(gè)排序情況。

各種方法的混裝線規(guī)劃優(yōu)化結(jié)果如表2 所示。從表中可以看出，除了目標(biāo)函數(shù)J2之外，本文所提方法在每個(gè)指標(biāo)上都優(yōu)于其他算法。盡管順序優(yōu)化的求解方法在求解平衡時(shí)獲得了更好的結(jié)果。然而，在排序問(wèn)題的優(yōu)化過(guò)程中，由于解域的限制，只能得到次優(yōu)解。對(duì)于“歸一化”的并行解決方案，即同時(shí)解決平衡和排序問(wèn)題，這將導(dǎo)致優(yōu)化結(jié)果的隨機(jī)性。一般來(lái)說(shuō)，嵌套遺傳算法那的整體優(yōu)化效果可以比其他3 種方法獲得更好的結(jié)果。

表2 各算法優(yōu)化結(jié)果對(duì)比

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

工程多目標(biāo)優(yōu)化問(wèn)題屬于NP難題，很難找到全局最優(yōu)解。針對(duì)一般的多目標(biāo)決策問(wèn)題，本文分析總結(jié)了兩級(jí)決策方法和歸一化方法求解過(guò)程存在的缺陷，提出了一種嵌套遺傳算法。將該方法和算法應(yīng)用于混裝線的平衡和排序。通過(guò)分別對(duì)裝配任務(wù)和產(chǎn)品進(jìn)行編碼，使用嵌套遺傳算法對(duì)平衡和排序進(jìn)行優(yōu)化。

以一個(gè)混合模型焊裝生產(chǎn)線的平衡和排序問(wèn)題為例，將所提算法和傳統(tǒng)歸一化方法、順序優(yōu)化方法進(jìn)行對(duì)比，對(duì)比的結(jié)果表明，該算法可以獲得令人滿意的結(jié)果。多目標(biāo)優(yōu)化仍然是一個(gè)NP難題。如何找到一個(gè)更客觀、更現(xiàn)實(shí)的優(yōu)化目標(biāo)，如何對(duì)其進(jìn)行更合理的評(píng)估，并提出更有效的算法，還有待進(jìn)一步探索。