姜 東，唐秋華，李梓響，吳 玲

（武漢科技大學(xué) 機(jī)械自動(dòng)化學(xué)院，湖北 武漢 430081）

1 引言

隨著市場(chǎng)競(jìng)爭(zhēng)越來(lái)越激烈以及顧客對(duì)產(chǎn)品的多樣性需求，制造企業(yè)逐漸將生產(chǎn)方式由單品種大批量想多品種小批量轉(zhuǎn)變。混流裝配線可以在不改變生產(chǎn)組織方式的前提下，在同一條裝配線上同時(shí)進(jìn)行多種不同型號(hào)、不同數(shù)量的產(chǎn)品生產(chǎn)?；炝餮b配線平衡是指在滿足工序間優(yōu)先關(guān)系約束的前提下，將每個(gè)產(chǎn)品的不同任務(wù)平均地分配到各個(gè)工作站[1]，而混流裝配線投產(chǎn)排序問(wèn)題則是根據(jù)產(chǎn)品訂單將不同類(lèi)型產(chǎn)品排成一個(gè)投產(chǎn)序列，并以這個(gè)投產(chǎn)序列來(lái)組織混流裝配線的生產(chǎn)[2]?；炝餮b配線平衡和投產(chǎn)排序的研究對(duì)于提高裝配線的生產(chǎn)效率、提高資源利用率，有著重要的作用。當(dāng)前，制造型企業(yè)對(duì)裝配線平衡和投產(chǎn)排序日益關(guān)注，眾多學(xué)者也對(duì)裝配線平衡和投產(chǎn)排序進(jìn)行了大量研究。

目前，求解裝配線平衡與排序問(wèn)題的算法主要包括進(jìn)化算法（EA）[3]、遺傳算法（GA）[4]和人工蜂群算法（ABC）[5]等。例如，文獻(xiàn)[4]采用多目標(biāo)遺傳算法優(yōu)化混流裝配線再平衡時(shí)的調(diào)整成本和生產(chǎn)效率。文獻(xiàn)[6]提出了均衡各工作站的加權(quán)平均負(fù)荷、最小化裝配線實(shí)際節(jié)拍和最小化工作站的空閑時(shí)間三個(gè)優(yōu)化目標(biāo)，并采用遺傳算法對(duì)多目標(biāo)優(yōu)化模型進(jìn)行求解。文獻(xiàn)[7]在U型裝配線的平衡排序問(wèn)題中采用工位負(fù)載，最小零件消耗率和生產(chǎn)準(zhǔn)備成本作為目標(biāo)函數(shù)，并采用加權(quán)的方式對(duì)多目標(biāo)進(jìn)行歸一化處理。文獻(xiàn)[5]提出了多目標(biāo)人工蜂群算法，引入了帕累托前沿概念來(lái)求解多目標(biāo)混流裝配線平衡與排序問(wèn)題。

為了提高裝配線的資源利用率和生產(chǎn)率，混流裝配線常包含多個(gè)優(yōu)化目標(biāo)，如最小化設(shè)計(jì)成本，最小化工作站數(shù)量，零件消耗率和工位負(fù)荷平衡等?；谝陨涎芯?，考慮開(kāi)放工位環(huán)境，以最小工位絕對(duì)負(fù)載偏差與最小工位越界距離為優(yōu)化目標(biāo)，分別建立平衡問(wèn)題和排序問(wèn)題的目標(biāo)函數(shù)。提出了多目標(biāo)模擬退火算法，引入了基于帕累托階層和擁擠距離作為多目標(biāo)適應(yīng)度評(píng)價(jià)指標(biāo)，協(xié)同求解裝配線平衡與排序問(wèn)題，以獲得帕累托前沿最優(yōu)解決方案，并通過(guò)參數(shù)校驗(yàn)和實(shí)驗(yàn)對(duì)比驗(yàn)證算法的合理性和有效性。

2 混合裝配線平衡排序數(shù)學(xué)模型

2.1 混合裝配線平衡排序問(wèn)題描述

混流裝配線平衡問(wèn)題（MALBP）比單模型裝配線平衡問(wèn)題（SALBP）更加復(fù)雜和困難。中長(zhǎng)期調(diào)度的混流裝配線需要考慮不同模型在各個(gè)工位上的負(fù)載均衡，不同模型的產(chǎn)品在不同的工作站中操作時(shí)間不同，工作站中過(guò)載或空閑現(xiàn)象時(shí)常發(fā)生，不僅影響產(chǎn)品質(zhì)量而且增加了生產(chǎn)成本。除了裝配線平衡的中長(zhǎng)期調(diào)度問(wèn)題之外，還需要進(jìn)行短期的混流裝配線排序問(wèn)題調(diào)度，在生產(chǎn)計(jì)劃周期內(nèi)（一天或者一輪輪崗），給定數(shù)量的模型進(jìn)行投產(chǎn)排序?；炝餮b配線性能顯著地受不同任務(wù)分配和不同模型的投產(chǎn)順序影響。

在計(jì)劃周期T內(nèi)，生產(chǎn)M個(gè)模型的系列產(chǎn)品，M個(gè)模型的產(chǎn)品總需求量為 Dk，（k∈｛1，…，k，…，M｝），每種產(chǎn)品的作業(yè)元素的優(yōu)先序列關(guān)系預(yù)先給定，在滿足一定的優(yōu)化條件下，確定所有產(chǎn)品的投產(chǎn)順序。若不同模型總需求量的最大公約數(shù)為H，則最小化則最小化生產(chǎn)循環(huán)單元MPS，可以用向量（d1，…，dk，…，dM）表示，其中，（dk=Dk/H）表示K模型在MPS中的投產(chǎn)比例。在調(diào)度過(guò)程中，只對(duì)最小化生產(chǎn)循環(huán)單元的產(chǎn)品進(jìn)行排序，重復(fù)進(jìn)行H個(gè)流程，可以得到所有產(chǎn)品的投產(chǎn)順序。

2.2 混合裝配線平衡排序優(yōu)化目標(biāo)描述

針對(duì)裝配線平衡和排序問(wèn)題，許多文獻(xiàn)中應(yīng)用了各種優(yōu)化目標(biāo)。為了提高計(jì)劃周期內(nèi)的生產(chǎn)率、提高工人之間的公平性、增加設(shè)備的利用率?？紤]兩種優(yōu)化目標(biāo)：不同工作站間的絕對(duì)負(fù)載偏差（ADW）和越界距離（OD）。在混流裝配線平衡問(wèn)題中，文獻(xiàn)[1]將每類(lèi)產(chǎn)品的負(fù)載與理論生產(chǎn)周期比較，構(gòu)造出混流裝配線絕對(duì)負(fù)載偏差模型。這種考慮不僅有利于不同工作站之間的負(fù)載均衡，也有利于每個(gè)工作站內(nèi)的負(fù)載均衡。該目標(biāo)模型如下：

式中：Tkj—模型k工位j的總處理時(shí)間—每個(gè)工作站在MPS中的平均工作量。

越界距離指標(biāo)是受補(bǔ)償工作量和未完成單元概念啟發(fā)[2]提出。后兩個(gè)生產(chǎn)指標(biāo)常用來(lái)表示封閉工作站內(nèi)的超額工作量，不適用開(kāi)放工作站直接使用。對(duì)于開(kāi)放工作站，工人允許越過(guò)工作站邊界。

當(dāng)產(chǎn)品的裝配結(jié)束位置在工作站右邊界的右側(cè)或其起始位置在工作站左邊界的左側(cè)時(shí)，工位就會(huì)產(chǎn)生越界距離；該目標(biāo)模型如下：

3 多目標(biāo)模擬退火算法設(shè)計(jì)

3.1 解的表達(dá)

平衡問(wèn)題的編碼是一個(gè)長(zhǎng)度為L(zhǎng)的字符串，每個(gè)元素的位置表示不同的任務(wù)，每個(gè)元素的值表示該任務(wù)被分配的工作站。每個(gè)編碼恰好可以被解碼成一組任務(wù)分配方案。對(duì)于排序問(wèn)題，模型投產(chǎn)序列采用置換的表達(dá)方式。相應(yīng)地，排序問(wèn)題編碼是長(zhǎng)度為M的字符串，字符串中每個(gè)元素序列表示產(chǎn)品在MPS中的投產(chǎn)順序，每個(gè)元素中的字母表示生產(chǎn)循環(huán)中的產(chǎn)品模型種類(lèi)。

圖1顯示了平衡排序示例的編碼、解碼過(guò)程?？梢钥闯?，MALB/S個(gè)體包含兩個(gè)編碼片段。前一段由數(shù)字組成的編碼表示裝配任務(wù)在所有工作站中的分配情況，而后一段以大寫(xiě)字母組成的編碼表示MPS中產(chǎn)品的投產(chǎn)序列。如圖中上色部分表示任務(wù)1、2和4被分配給工作站1并以生產(chǎn)序列（A C A B A C）組織產(chǎn)品生產(chǎn)。

圖1 平衡與排序問(wèn)題編碼、解碼Fig.1 Encoding and Decoding Scheme of Balancing and Sequencing Problems

3.2 初始化帕累托解集

任務(wù)分配工位考慮兩個(gè)方面的因素：任務(wù)在MPS中的總處理時(shí)間t?i和任務(wù)所有后繼任務(wù)的總處理時(shí)間?？煞峙淙蝿?wù)集合中權(quán)重較高的任務(wù)被優(yōu)先分配，這將釋放更多的可分配任務(wù)以供當(dāng)前工位選擇。

每個(gè)可分配任務(wù)的權(quán)重可以利用下式計(jì)算。式中：i和i′—可分配任務(wù)；

US—任務(wù)i的后續(xù)任務(wù)集合。

對(duì)于排序個(gè)體初始化，根據(jù)MPS不同產(chǎn)品生產(chǎn)需求，隨機(jī)生產(chǎn)一個(gè)排序染色體，從而保證帕累托解集的多樣性。

3.3 多目標(biāo)適應(yīng)度評(píng)價(jià)

MALB/S模型包含多個(gè)相互沖突的目標(biāo)，需要同時(shí)優(yōu)化這些目標(biāo)。引用帕累托階層的概念對(duì)所有帕累托解集分層[5]，根據(jù)個(gè)體之間的支配關(guān)系將個(gè)體劃分為不同的層級(jí)，每個(gè)解所處的層數(shù)越低，解的質(zhì)量越高，相同層級(jí)的解之間不存在支配關(guān)系，第一層級(jí)個(gè)體不被任何個(gè)體支配，即帕累托前沿解集；第二層的候選個(gè)體僅僅只被第一層級(jí)個(gè)體支配，被賦第二層級(jí)，依此類(lèi)推。

除了利用層級(jí)來(lái)劃分個(gè)體收斂性的優(yōu)劣，算法利用多樣性指標(biāo)擁擠距離[5]來(lái)確定具有相同層級(jí)個(gè)體的優(yōu)劣。擁擠距離是由相鄰個(gè)體的幾何距離確定的度量。算法通過(guò)ADW和OD形成的二維目標(biāo)空間，確定相鄰個(gè)體距離。剔除候選個(gè)體中的被支配個(gè)體和重復(fù)個(gè)體，大大提高了解集分層的效率。

3.4 鄰域搜索

為了保證解的可行性，平衡問(wèn)題的編碼部分由變異概率Pc生成需要變異元素的位置，通過(guò)搜索變異元素在任務(wù)優(yōu)先關(guān)系矩陣中的行列，從可分配工位集合中選擇一個(gè)工位，更新平衡編碼。排序編碼序列采用兩種鄰域搜索方式。

（1）隨機(jī)選擇排序編碼兩點(diǎn)進(jìn)行交換操作，改變不同類(lèi)型產(chǎn)品的投產(chǎn)序列，更新排序編碼；

（2）隨機(jī)產(chǎn)生兩個(gè)插入點(diǎn)w和v，如果，則插入點(diǎn)w向前插入v點(diǎn)位置，插入點(diǎn)w和v之間編碼整體向后移動(dòng)；如果，則插入點(diǎn)w向后插入v點(diǎn)位置，插入點(diǎn)w和v之間編碼整體向前移動(dòng)。

3.5 接受策略

通過(guò)鄰域搜索產(chǎn)生一個(gè)新的個(gè)體，依次與帕累托前沿解集中的個(gè)體比較。如果新產(chǎn)生的個(gè)體可以支配前沿解集中的個(gè)體，將新個(gè)體加入帕累托前沿解集中，同時(shí)，將被支配的個(gè)體從帕累托前沿解集中剔除。

帕累托前沿解集更新后，將新產(chǎn)生的個(gè)體作為當(dāng)前個(gè)體，即S←S′。如果新產(chǎn)生的個(gè)體不是非支配前沿解，每個(gè)目標(biāo)函數(shù)被選擇的概率為0.5，f表示被選擇目標(biāo)函數(shù)，Δ表示目標(biāo)函數(shù)變化值Δ＝f（S′）-f（S），若Δ≤0，則接受新產(chǎn)生的個(gè)體作為當(dāng)前個(gè)體，若exp（-Δ/TI）＞rand時(shí)，也接受新產(chǎn)生的個(gè)體。采用重啟機(jī)制避免帕累托前沿解集避免早熟。迭代次數(shù)d達(dá)到終止條件d＞d，從帕累托前沿解集隨機(jī)選擇一個(gè)前沿解作為當(dāng)前個(gè)體。

3.6 多目標(biāo)模擬退火算法流程

求解混流裝配線平衡與排序問(wèn)題的多目標(biāo)模擬退火算法的流程，如圖2所示。初始化帕累托解集，對(duì)帕累托解集進(jìn)行多目標(biāo)適應(yīng)度指標(biāo)評(píng)價(jià)。帕累托解集中選擇個(gè)體進(jìn)行領(lǐng)域搜索，產(chǎn)生新的個(gè)體。采用新的接受策略，更新帕累托前沿解集。滿足終止條件后，輸出帕累托前沿解集。

4 實(shí)例分析

選擇了2個(gè)具有代表性的MALBP標(biāo)桿案例，其中包括文獻(xiàn)[3]中的111任務(wù)5模型案例，文獻(xiàn)[5]中的148任務(wù)4模型案例。每個(gè)案例給定了三種不同的工位數(shù)量，根據(jù)每個(gè)案例的模型數(shù)量隨機(jī)產(chǎn)生三種不同規(guī)模的投產(chǎn)比例。實(shí)驗(yàn)計(jì)算機(jī)配置：i5處理器，主頻3.1GHz，內(nèi)存8.0G，windows64位操作系統(tǒng)，在MATLAB R016a上編寫(xiě)、調(diào)試和運(yùn)行。針對(duì)所研究的平衡排序問(wèn)題，算法性能受參數(shù)影響較大，為保證算法性能，首先對(duì)算法中所用參數(shù)進(jìn)行校核共考慮5個(gè)因數(shù)4水平，不同參數(shù)及其水平值，如表1所示。利用MATLAB進(jìn)行5個(gè)參數(shù)4個(gè)水平的正交實(shí)驗(yàn)方法。

圖2 多目標(biāo)模擬退火算法流程圖Fig.2 Procedure of Multi-Objective Simulated Annealing Algorithm

表1 不同參數(shù)及水平值Tab.1 Different Parameters and Level Values

將非支配率（NR）作為不同類(lèi)型的多目標(biāo)問(wèn)題的評(píng)價(jià)標(biāo)準(zhǔn)。非支配率表示一組多目標(biāo)解對(duì)另一組解的覆蓋情況[5]。每個(gè)標(biāo)桿實(shí)例下，對(duì)算法需要重復(fù)運(yùn)行5次，每次運(yùn)行分別配置表1中的參數(shù)，每次配置需要計(jì)算獲得的帕累托前沿的非支配率（NR）。為了確定各參數(shù)的最佳水平，我們將所有參數(shù)在不同水平下的平均表現(xiàn)進(jìn)行了統(tǒng)計(jì)。

每個(gè)參數(shù)中具有最大NR值的水平值為最優(yōu)水平值。因此，參數(shù)TI TF q Iter和Pc在MOSA中分別設(shè)置為40，0.01，0.98，150和0.3，如圖3所示。

圖3 不同參數(shù)水平下算法求解非支配率的總體平均值Fig.3 Mean of NR in Different Levels of Parameters

為了驗(yàn)證算法的性能，分別使用MOSA和快速非支配遺傳算法[9]（NSGA-II）對(duì)每個(gè)標(biāo)桿問(wèn)題進(jìn)行求解。從兩個(gè)方面考慮多目標(biāo)算法性能，一方面算法收斂性性能指標(biāo)[8]（GD）衡量了算法所得到的帕累托前沿和帕累托真實(shí)前沿之間的距離；另一方面算法多樣性性能指標(biāo)：獲得的帕累托最優(yōu)解數(shù)量（NP）[5]。NP表示每個(gè)算法從帕累托真實(shí)前沿中找到的帕累托最優(yōu)解的數(shù)量。上述性能指標(biāo)可用于綜合比較不同算法得到的帕累托前沿，并可顯示出不同算法所獲得的帕累托前沿之間的支配關(guān)系。對(duì)于2個(gè)標(biāo)桿案例，每種算法獨(dú)立重復(fù)運(yùn)行5次，每次運(yùn)行結(jié)束后計(jì)算上述2個(gè)多目標(biāo)性能指標(biāo)值。兩種算法求解中大規(guī)模案例Arcus問(wèn)題的五次重復(fù)實(shí)驗(yàn)所得帕累托前沿，如圖4所示。由圖可知，所提出的MOSA算法獲得前沿解支配了NSGA-II獲得前沿解，即所提出的MOSA算法優(yōu)于NSGA-II。

圖4 MOSA算法和NSGA-II算法求解的前沿解Fig.4 Pareto Frontier Solutions Comparisons Between MOSA and NSGA-II

表2 算法性能分析與對(duì)比Tab.2 Algorithm Performance Analysis and Comparison

所提出MOSA獲得的平均GD值為3.72顯著小于NSGA-II算法的353.79，這表明MOSA算法所得Pareto前沿解在收斂性方面的質(zhì)量?jī)?yōu)于NSGA-II算法，如表2所示。所提出MOSA獲得的平均NP值為4.46顯著大于NSGA-II算法的2.03，這表明MOSA算法能獲得更多的前沿解。

綜上所述，所提出的MOSA算法在收斂性和多樣性方面優(yōu)于NSGA-II算法。

5 總結(jié)

針對(duì)混流裝配線平衡排序多目標(biāo)問(wèn)題，提出多目標(biāo)模擬退火算法進(jìn)行求解。所提出的模擬退火算法在初始化中將啟發(fā)式任務(wù)分配規(guī)則融入平衡問(wèn)題，以保證初始解的質(zhì)量。引入多目標(biāo)適應(yīng)度指標(biāo)評(píng)價(jià)帕累托解集。改進(jìn)領(lǐng)域搜索方式，增加全局尋優(yōu)能力。采用一種新的接受策略，提高了算法尋優(yōu)能力。所提出的算法與快速非支配遺傳算法進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果表明多目標(biāo)模擬退算法優(yōu)于對(duì)比的算法。在未來(lái)的研究中，可以考慮求解混流機(jī)器人裝配線平衡排序多目標(biāo)問(wèn)題。