劉 瓊，范正偉，張超勇，劉煒琪，許金輝

（華中科技大學(xué) 數(shù)字制造裝備與技術(shù)國家重點實驗室，湖北 武漢 430074）

0 引言

在混流裝配線用于平衡工作站負載的指標(biāo)中，最小化總超載時間［1］這一經(jīng)典指標(biāo)忽略了機器閑置時工人的等待成本，Tavakkoli-Moghaddam［2］在其基礎(chǔ)上進一步考慮了不同工作站內(nèi)設(shè)備資產(chǎn)價值、加工速度等對制造系統(tǒng)的影響，對不同工作站上的超載成本賦予了不同的權(quán)重。Fattahi［3］綜合考慮了正規(guī)工人的等待時間和輔助工人的工作時間對工作站負載平衡的影響，提出最小化閑置／輔助工作總成本的目標(biāo)，然而研究中分別將不同工作站上的正規(guī)工人閑置成本和各輔助工人的工作成本設(shè)置為相同，不符合不同崗位工人工資差異的實際情況。因此，實際生產(chǎn)過程中考慮不同工作站上工人閑置／超載成本差異的最小化工作站閑置／超載總成本指標(biāo)，既能平衡工作站的負載，又能優(yōu)化工人的工作成本，使其與企業(yè)的生產(chǎn)實際更加吻合。

目前，混流裝配線排序問題的求解普遍采用遺傳算法［4-8］和粒子群算法［9-10］，其中：遺傳算法同時使用多個搜索點進行搜索，具有隱含的并行性和良好的全局搜索能力，但是搜索速度較慢，易陷入局部最優(yōu)，導(dǎo)致過早收斂；粒子群算法的可調(diào)參數(shù)少、收斂速度快，但是在處理離散的優(yōu)化問題時表現(xiàn)不佳，不能很好地跳出局部最優(yōu)［11］。Shu-Chuan Chu受貓日常行為動作的啟發(fā)，于2006年提出了貓群優(yōu)化（Cat Swarm Optimization，CSO）算 法［12］。CSO 算法的最大特征表現(xiàn)為在進化過程中能夠同時進行局部搜索和全局搜索，使其擁有克服遺傳算法局部搜索能力不足和粒子群算法求解離散問題時容易陷入局部最優(yōu)點的能力，且具有很好的收斂速度［13］。貓群算法在連續(xù)函數(shù)優(yōu)化［12-16］和 圖像處理［11，14，17-18］中得到了良好的應(yīng)用，證明了它具有比遺傳算法和粒子群算法更優(yōu)異的算法性能，但是還未見到在調(diào)度領(lǐng)域中的應(yīng)用實例。把CSO 算法應(yīng)用于混流裝配線排序，需要將其離散化。本文針對目前CSO 算法在進化過程中一般采用固定的混合比率進行貓行為模式的選擇方法，不能根據(jù)進化的程度有效分配全局貓和局部貓的數(shù)目，提出一種基于線性混合比率的貓行為模式選擇方法；針對CSO 算法在搜尋過程中可能出現(xiàn)重復(fù)的候選個體，不能有效進行全局搜索，提出基于多樣化搜尋算子的改進搜尋模式，用來生成有效的、分布均勻的搜尋結(jié)構(gòu)并進行優(yōu)化。

1 多目標(biāo)混流裝配線排序問題

1.1 問題描述

本文描述的混流裝配線是一種以常速vc移動的傳輸系統(tǒng)。相似度較高的M 種產(chǎn)品以固定的投放間隔γ 投放到裝配線上，每種產(chǎn)品的生產(chǎn)量分別為D1，D2，…，DM。裝配線被分成J 個工作站，每個工作站的工位長度Lj固定，且為閉式工作站。正規(guī)工人只能在工作站的限定范圍內(nèi)工作，不能穿越它所在工作站的上游邊界和下游邊界，不能完成的工作交給輔助工人完成，以避免由工作負載引起的生產(chǎn)線的停線。工人對一個產(chǎn)品執(zhí)行裝配任務(wù)并隨傳送帶一起移動到下游，完成裝配工序或移動到工作站邊界后，工人移向上游繼續(xù)裝配下一產(chǎn)品。采用Bard在文獻［1］中提出的最小工作循環(huán)（Minimal Product Set，MPS）策略組織裝配車間的生產(chǎn)。MPS代表混流裝配線上要加工產(chǎn)品的向量，（d1，d2，…，dM）=（D1／h，D2／h，…，DM／h），其中：dm表示裝配線在一個時間周期內(nèi)生產(chǎn)m 類型產(chǎn)品的數(shù)量，Dm表示在整個計劃周期內(nèi)m 類型產(chǎn)品的裝配數(shù)量，h是D1，D2，…，DM的最大公約數(shù)。模型參數(shù)如下：

（1）全局變量

i為產(chǎn)品，i∈｛1，2，…，I｝；j 為工作站，j∈｛1，2，…，J｝；m 為產(chǎn)品類型，m∈｛1，2，…，M｝。

（2）輸入?yún)?shù)

αj為第j個工作站等待的時間成本；βj 為第j個工作站超載的時間成本；I 為被排序產(chǎn)品的總數(shù)目，；M 為最小工件集中的產(chǎn)品類型數(shù)目；Lj為工作站j的長度；tmj為m（m ∈｛1，2，…，M｝）類型的產(chǎn)品在工作站，j（j∈｛1，2，…，J｝）上裝配的時間；w 為固定投放率條件下兩產(chǎn)品之間的投放距離。

（3）決策變量

xim表示若排序序列中第i 個產(chǎn)品的類型是m則為1，否則為0；Zij表示第i 個產(chǎn)品在第j 個工作站上開始裝配的位置；Iij表示第i 個產(chǎn)品在第j 個工作站上的閑置時間；Uij表示第i 個產(chǎn)品在第j 個工作站上的輔助時間。

1.2 優(yōu)化目標(biāo)

考慮實例企業(yè)平衡工作站負載，減少產(chǎn)品庫存量和降低刀具、夾具頻繁更換對工人操作技巧的要求，建立改進的最小化超載／閑置總成本、最小化產(chǎn)品變化率和最小化產(chǎn)品總切換時間的多目標(biāo)混流裝配線排序模型。

（1）最小化工作站閑置／超載總成本

傳統(tǒng)的平衡工作站負載的模型中，一般都假設(shè)不同工作站上的正規(guī)工人閑置成本和輔助工人的工作成本分別相同［3］，而實際企業(yè)中，工人的操作技巧有高有低，各工作站上工人的工作成本不完全相同。因此對不同工作站上的工人賦予不同的工作成本，得到改進的最小化工作站超載／閑置總成本指標(biāo)，在平衡工作站負載的同時優(yōu)化工人的工作成本，以貼近企業(yè)生產(chǎn)實際。本文改進了可變投放間距下的最小化閑置／輔助工人成本指標(biāo)［3］。

其中：式（2）確定混流裝配排序序列中每個位置都分配有一個確定的產(chǎn)品；式（3）滿足單個生產(chǎn)循環(huán)中每種類型產(chǎn)品的需求數(shù)量；式（4）強制要求每個循環(huán)的第一個產(chǎn)品在工作站的左邊界開始；式（5）計算工人在工作站j開始加工第（i+1）個產(chǎn)品的位置；式（6）計算在工作站j上，當(dāng)?shù)趇個產(chǎn)品不能完成時需要輔助工人工作的時間；式（7）表征排序中最后一個產(chǎn)品需要的輔助工人工作時間；式（8）給出工件沒有到達時正規(guī)工人的閑置時間。

（2）最小化總產(chǎn)品變化率

準(zhǔn)時生產(chǎn)（Just in Time，JIT）制造系統(tǒng)的一個基本要求是保證連續(xù)和穩(wěn)定的零部件供應(yīng)，它能夠避免上游生產(chǎn)線產(chǎn)量的波動和減少產(chǎn)品的庫存量。

式中Xlm表示產(chǎn)品序列中第1位～第l位產(chǎn)品m 的累積數(shù)量。

（3）最小化產(chǎn)品間總切換時間

在混流裝配線生產(chǎn)過程中，不同產(chǎn)品需要的工裝或工裝的設(shè)置不同，從一種產(chǎn)品調(diào)整到另外一種產(chǎn)品需要調(diào)整刀具和夾具，并且有些工裝的設(shè)置時間與切換順序有關(guān)。因此不同品種產(chǎn)品之間的總切換時間與生產(chǎn)排序有關(guān)。

式（10）中，cimr表示工作站J 上從m 類型產(chǎn)品調(diào)整到r 類型產(chǎn)品的轉(zhuǎn)換成本，若m 類型產(chǎn)品和r類型產(chǎn)品分別分配給第i 個和第（i+1）個工作，則ximr=1，否則為0。式（11）確定混流裝配排序中每個序列有一個確定的產(chǎn)品，式（12）和式（13）保證每個生產(chǎn)節(jié)拍中產(chǎn)品的序列不發(fā)生變化。式（14）限制一個生產(chǎn)循環(huán)中某類型產(chǎn)品的總需求滿足MPS。

2 改進的多目標(biāo)貓群優(yōu)化算法

CSO 算法通過分組—混合機制進行信息的傳遞，即采用混合比率將進行搜尋模式和跟蹤模式的兩個子群貓組合在一起形成種群，在每次迭代過程中采用分組方法重新隨機選擇貓的行為模式，不同子群采取不同的模式進行更新。搜尋模式中通過對個體自身進行搜尋操作，生成一系列子代填滿搜尋記憶池，并用搜尋記憶池中的最好個體更新當(dāng)前個體，在算法中執(zhí)行全局搜索的任務(wù)；跟蹤模式類似于粒子群算法，利用全局最優(yōu)的位置來更新貓的當(dāng)前位置［14］。CSO 算法混合了進行全局搜索和局部搜索的兩個子群，使得在算法進化的每一代中能同時進行全局搜索和局部搜索，這種獨特的算法結(jié)構(gòu)保證了算法的收斂速度和Pareto解的搜索能力，能夠克服遺傳算法搜索速度慢、容易陷入局部最優(yōu)、粒子群算法求解離散問題不能跳出局部最優(yōu)點等缺陷。將求解連續(xù)問題的標(biāo)準(zhǔn)CSO 算法應(yīng)用于混流裝配線排序這類離散問題時，需將算法離散化；考慮到CSO 算法現(xiàn)有搜尋算子生成方法單一且可能產(chǎn)生冗余操作，提出了基于多樣化算子的改進搜尋模式；考慮到標(biāo)準(zhǔn)CSO 算法搜索貓和跟蹤貓固定的混合比率在進化過程中不能有效地分配全局搜索和局部搜索能力，提出了基于線性混合比率的貓行為模式選擇方法，改進的多目標(biāo)貓群（Improved Multi-Objective Cat Swarm Optimization，IMOCSO）算法如圖1所示。

2.1 離散化編碼和解碼操作

標(biāo)準(zhǔn)CSO 算法的連續(xù)編碼方式不適合求解離散化的混流裝配線排序問題，因此需要將標(biāo)準(zhǔn)CSO算法離散化，使得離散編碼序列與貓移動過程中的連續(xù)位置對應(yīng)起來。采用隨機數(shù)表示法［9］和基于工件的編碼方法將標(biāo)準(zhǔn)CSO 算法離散化，并采用降序映射規(guī)則進行解碼。離散化編碼步驟為：①為染色體的每個基因生成服從（0，1）均勻分布的隨機數(shù)，形成一個隨機數(shù)序列；②按照各維數(shù)值大小進行降序排序；③根據(jù)離散數(shù)字編碼和產(chǎn)品類型之間的對應(yīng)關(guān)系進行解碼，得到解碼序列。假設(shè)有A，B和C三種產(chǎn)品，MPS為（3，2，3），離散化編碼如圖2所示。

2.2 基于線性混合比率的貓行為模式選擇方法

CSO 算法采用分組—混合機制控制著算法的進化。在算法的每一次迭代過程中采用混合比率將種群分組，得到搜尋貓子群和跟蹤貓子群，對不同子群的貓采取對應(yīng)的行為模式進行處理；將執(zhí)行全局搜索的搜尋貓子群和執(zhí)行局部搜索的跟蹤貓子群進行混合形成種群，直到滿足算法的終止條件。由此可見，混合比率影響CSO 算法的整體性能，然而標(biāo)準(zhǔn)CSO 算法采用固定混合比率的方法進行貓行為模式選擇，即每一代種群中進行全局搜索的搜尋貓和進行局部搜索的跟蹤貓的數(shù)量比例都是一定的，不能根據(jù)算法的進化程度調(diào)整全局搜索和局部搜索的比重。在CSO 算法中，若在算法運行前期采用較大比率的跟蹤貓可提高算法的全局搜索能力，則可加快算法收斂到Pareto前沿的速度；若在算法的后期采用較大比率的搜索貓，則可提高算法的局部搜索能力，有效地搜索出非支配解，提高解的質(zhì)量，保證算法的收斂性質(zhì)。因此，本文提出一種基于線性混合比率的貓行為模式選擇方法，如圖3所示。算法開始采取較大的混合比率MR1，迭代到最大次數(shù)T0時混合比率為MR2。在算法的整個運行過程中，通過調(diào)整混合比率來調(diào)整算法進行全局搜索和局部搜索的貓的比重。

該線性混合比率的計算公式為

2.3 基于多樣化搜尋算子的改進搜尋模式

搜尋模式對應(yīng)于優(yōu)化問題的全局搜索技術(shù)，通過對當(dāng)前個體進行搜尋操作，生成填滿搜尋記憶池的一系列個體。評價搜尋記憶池中的個體，并用搜尋記憶池中的Pareto非支配解更新當(dāng)前解。圖4給出了應(yīng)用于混流裝配線排序問題的標(biāo)準(zhǔn)CSO 算法搜尋算子。其中產(chǎn)品數(shù)目為8，給定改變基因位數(shù)（Counts of Dimension to Change，CDC）的范圍為［0，8］，生成的改變基因位數(shù)的數(shù)目為4，隨機選擇2，4，6，7這4個位置，給定變化域（Seeking Range of the selected Dimension，SRD）為［0，0.15］，生成服從該變化域的4 個隨機數(shù)0.08，0.14，0.11，0.01，與隨機數(shù)編碼上對應(yīng)位置的數(shù)值相加，得到新的隨機數(shù)序列，重新按降序排序可得新的解碼序列。將標(biāo)準(zhǔn)貓群搜尋模式下搜尋記憶池中候選個體的生成方法稱為標(biāo)準(zhǔn)搜尋算子，圖4給出了標(biāo)準(zhǔn)搜尋算子的操作過程。

搜尋模式下參數(shù)（CDC，SRD）的設(shè)置對搜索性能有顯著的影響。若參數(shù)設(shè)置過大，則解的變化范圍過大，算法容易變成簡單的隨機搜索，不利于算法的收斂；若參數(shù)設(shè)置過小，則解的變化范圍小，算法的搜索能力較弱，容易陷于局部最優(yōu)［11］。尤其在離散問題的求解過程中，算法設(shè)置過小，可能得不到有效的候選個體。以圖4為例，假設(shè)只在第一個基因0.37上發(fā)生變異，變異的大小為0.02，按照降序排列的映射規(guī)則解碼，變異后個體上的基因位置保持不變，該操作即為冗余操作。為了降低算法參數(shù)設(shè)置對搜尋模式性能的影響和得到分布均勻與多樣化的候選個體，提高算法的收斂速度，標(biāo)準(zhǔn)搜尋算子聯(lián)合遺傳算法的三種變異算子組成多樣化的搜尋算子，對搜尋模式進行了改進。多樣化算子中各算子對應(yīng)的概率在算法的開始之前設(shè)定。

（1）成對交換搜尋算子 隨機選擇兩個任意的產(chǎn)品，其位置分別為i和j（i≠j），交換對應(yīng)基因上的產(chǎn)品和編碼數(shù)字，如圖5所示。

（2）插入搜尋算子 移動位置i上的產(chǎn)品插入到位置j 后（i≠j），生成新個體，如圖6所示。

（3）倒序搜尋算子 隨機選擇個體的一部分，并將其執(zhí)行倒序操作，如圖7所示。

2.4 跟蹤模式

跟蹤模式對應(yīng)于搜索問題的局部搜索技術(shù)，采用速度—位移模型，類似于粒子群算法。定義第i只貓在D 維空間中的位置和速度分別為Xi=（Xi1，Xi2，…，XiD）和Vi=（Vi1，Vi2，…，ViD），其中d（1≤d≤D）代表維數(shù)。貓群全局最優(yōu)位置表示為Xg=（Xg1，Xg2，…，XgD）。跟蹤模式分以下五步進行工作：

（1）根據(jù)式（16）計算第i只貓的新的速度。

式中：w為慣性權(quán)重，c為加速度常數(shù)，r為服從［0，1］均勻分布的隨機數(shù)。全局最優(yōu)Xg從Pareto外部存檔解集中隨機選取。

（2）根據(jù)式（17）計算下一單位時間第i只貓的新位置。

（3）如果第i只貓的新位置中任一維的位置超出了搜索空間，則將該值作為相應(yīng)的邊界值，對應(yīng)維數(shù)的速度乘以-1，從反方向繼續(xù)搜索。

（4）用基于Pareto分層—小生境技術(shù)評價貓的適應(yīng)度值。

（5）用非支配解的貓的位置更新外部的Pareto存檔。

2.5 基于Pareto分層—小生境技術(shù)的選擇操作

采用Pareto分層—小生境技術(shù)進行多目標(biāo)處理，即在種群進化過程中，采用Pareto分層—小生境評價個體多目標(biāo)函數(shù)值并進行選擇，小生境維持種群的多樣性。在算法中，設(shè)置一個Pareto存檔存放每一代運行得到的Pareto解，并用搜尋模式和跟蹤模式下得到的當(dāng)前Pareto 最優(yōu)解更新Pareto存檔。

（1）非支配解排序

對種群各個體進行Pareto非支配解排序，確定各個體Pareto層次。

Pareto支配關(guān)系為當(dāng)且僅當(dāng)?j∈｛1，2，…，n｝，fj（x1）≤fj（x2）且?k∈｛1，2，…，n｝，fk（x）＜fk（x），解x1支配解x2，表示為x1?x2。

圖8所示為兩個目標(biāo)最小化優(yōu)化問題的Pareto分層示意圖，處于第一層即實心標(biāo)識的點為Pareto最優(yōu)點，實心點構(gòu)成的集合為Pareto最優(yōu)解集，實心點在解空間中的表現(xiàn)形式即為Pareto前沿。分層步驟為：①在當(dāng)前種群中找出階層最高的Pareto非支配解集S1，令S1的Pareto層次rank=1；②在余下的個體中找出非支配解集S2；③重復(fù)①～②，直至找出階層最低的非支配解集Slowest才結(jié)束。在選擇的過程中，階層高的個體優(yōu)于階層低的個體，S1?S2?…?Slowest。

（2）小生境距離計算

采用小生境距離保證非支配解的分布性和多樣性，進一步降低算法的早熟收斂，從而增強算法搜索Pareto最優(yōu)解的能力。假設(shè)一個n 目標(biāo)的問題，MAXlt和MINlt分別為第t 代個體的第l 個目標(biāo)值的最大值和最小值，popSize 為種群大小。用式（18）計算第l個目標(biāo)的小生境大小：

當(dāng)每一個小生境立方體大小相同時，解的擁擠度用立方體中解的個數(shù)衡量，個數(shù)越多，擁擠度越大。擁擠度小的解賦予較大的概率進化到下一代。

（3）基于Pareto分層—小生境技術(shù)的選擇機制

種群記為P（t）=｛p1，p2，…，ppopSize｝，排序?qū)哟螢関的個體記為p（v），當(dāng)前種群記為Pu，如第一代種群表示為P1。具體步驟為：①初始化參數(shù)，Pu=P（t），u=1，因尚未對種群進行Pareto排序，此時所有個體的排序?qū)哟蝪=0；②計算當(dāng)前種群P（t）內(nèi)個體的小生境距離；③對種群進行Pareto排序，尋找第u 個Pareto分層PSu，PSu=｛（pi，bi）｝，其中pi為種群Pu的非支配解，bi為pi的小生境距離；④按照bi升序的方式排序PSu中的個體，將rank（v+s）分配給第s個個體，其中，如果Pu≠?，則返回③，否則進入⑥；⑥通過式prob（p（v））=q（1-q）v-1，v=1，2，…，popSize，確定每一Pareto分層中個體選擇到下一代中的概率，式中q 為選擇概率參數(shù)。

3 算法測試及實例求解

3.1 算法測試

為驗證算法性能，采用Mansouri［4］提出的混流裝配線排序的小規(guī)模和大規(guī)模測試集，分別如表1和表2所示。裝配線上的操作時間tmj、工作站長度Lj、切換時間cimr分別服從均勻分布U（4，9）、U（12，15）和U（1，3）。將IMOCSO 與第二代非支配排序遺傳算法［19］（Non-dominated Sorting Genetic Algorithm-Ⅱ，NSGA-Ⅱ）、多目標(biāo)粒子群算法［20］（Multi-Objective Particle Swarm Optimization，MOPSO）、第二代強度Pareto進化算法［21］（Streptococcal Pyogenic Exotoxin 2，SPEA2）進行了對比。所有算法的運行環(huán)境為2.0GHz Pentium CPU，1G RAM，Windows XP，采用VC++6.0編程，并使用以下指標(biāo)對各算法進行綜合比較：

表1 小規(guī)模問題集

表2 大規(guī)模問題集

（1）解集覆蓋度指標(biāo)（Set Coverage Metric，SCM）測量已經(jīng)得到的非支配解集和Pareto最優(yōu)解集之間的解的相對分布。

（2）世代距離（Generational Distance，GD）計算在Pareto解集中找到的非支配解的平均距離。世代距離越小，表明越收斂于Pareto前沿。

（3）Pareto 前沿最大誤差（Maximum Paretooptimal Front Error，MFE）度量di中的最大值。di為第i個解與Pareto解集中距離此解最近的解的歐幾里得距離。

（4）分布度指標(biāo)（Spacing Metric，SM）計算得到的非支配前凸面內(nèi)連續(xù)解的相對距離，用來評價解集在目標(biāo)空間中的分布情況。分布度指標(biāo)越小，表明解的分布越均勻。

（5）非支配解的數(shù)目（the Number of Non-Dominated solutions，NNDS）算法搜索Pareto前凸面的能力，數(shù)目越大說明越易于搜索出Pareto解，即搜索Pareto前沿的能力越強。

為便于各算法的比較，算法參數(shù)設(shè)置盡可能相同并采用相同的種群規(guī)模和迭代次數(shù)。CSO 算法相關(guān)參數(shù)設(shè)置為：①小規(guī)模問題中，貓的數(shù)目為150，SMP=20，MR1=0.6，MR2=0.4，運行100代。②大規(guī)模問題中，貓的數(shù)目為450，SMP=35，MR1=0.7，MR2=0.3，運行600 代。各算法取20次運行結(jié)果的平均值進行各指標(biāo)的對比，如表3所示，圖9～圖13 圖示化地比較了IMOCSO，NSGA2，SPEA2，MOPSO 的各性能指標(biāo)。

由圖9可知，IMOCSO 的解集覆蓋度指標(biāo)小于其他算法，且在大規(guī)模問題中該指標(biāo)增加緩慢，表明IMOCSO 得到的非支配解能更好地收斂到Pareto最優(yōu)解集，其收斂性優(yōu)于其他算法。由圖10可知，IMOCSO 的世代距離指標(biāo)整體優(yōu)于其他算法，且大規(guī)模問題中的結(jié)果在減小，表明在各算法設(shè)置的相同的迭代次數(shù)中，IMOCSO 比其他算法擁有更快的收斂速度。由圖11 可知，IMOCSO 算法的誤差率小于其他算法，表明該算法能更好地收斂于Pareto前沿。由圖12 可知，IMOCSO 算法的分布度指標(biāo)明顯小于其他算法，表明該算法有更好的分布性。由圖13可知，IMOCSO 搜索到的非支配解的數(shù)目均比其他算法多，表明該算法更容易得到Pareto最優(yōu)解，算法具有良好的全局搜索能力和局部搜索能力。

表3 各算法性能指標(biāo)的平均值比較

續(xù)表3

綜上所述，IMOCSO 算法在除運行時間之外的指標(biāo)上都有良好的表現(xiàn)，優(yōu)于NSGA2，MOPSO 和SPEA2，在大規(guī)模問題中表現(xiàn)尤為明顯，表明MOCSO 算法能夠有效地求解混流裝配線排序問題。

3.2 實例驗證

為進一步驗證IMOCSO 算法的實用性，以及應(yīng)用提出的改進的多目標(biāo)混流裝配線的數(shù)學(xué)優(yōu)化模型，用該算法求解某空調(diào)企業(yè)的中央空調(diào)混流裝配線的排序問題。裝配線上產(chǎn)品的投放間距W=775 mm，裝配線的移動速度為Vc=10 mm／s。需要裝配6種四出風(fēng)室內(nèi)機產(chǎn)品，日計劃產(chǎn)量分別為A 產(chǎn)品45臺、B產(chǎn)品90臺、C 產(chǎn)品75臺、D 產(chǎn)品60臺、E產(chǎn)品60臺、F 產(chǎn)品90臺，最小生產(chǎn)循環(huán)MPS為（3，6，5，4，4，6）。經(jīng)過簡單的作業(yè)規(guī)劃合并后，該混流裝配線包括裝電機、裝風(fēng)輪、裝電控、裝蒸發(fā)器、裝送風(fēng)部件、主打包（貼標(biāo)簽、裝附件）6個主要工位。各機型在每個工位上的加工時間經(jīng)過多次測量求平均值，以確保數(shù)據(jù)的準(zhǔn)確度、減小誤差，處理后的數(shù)據(jù)如表4所示，各工位的長度為產(chǎn)品間的切換時間（如表5），由混流裝配車間提供裝配線設(shè)計數(shù)據(jù)得到。算法的相關(guān)參數(shù)設(shè)置為：貓的數(shù)目為120，SMP=20，MR1=0.6，MR2=0.35，運行100代。算法運行得到53個非支配解，表6所示為部分結(jié)果。

表4 模型數(shù)據(jù)表格

表5 產(chǎn)品間切換平均時間 s

表6 Pareto最優(yōu)解集

續(xù)表6

車間采用生產(chǎn)比倒數(shù)法得到的排序為BFCDEABFCDEBFCABFDECBFBFCDEA，目標(biāo)值分別為137，8.6，405。表6中的結(jié)果采用CSO 算法求解得Pareto解集。可以明顯看出，表6中的結(jié)果支配生產(chǎn)比倒數(shù)法得到的結(jié)果，這是因為生產(chǎn)比倒數(shù)法是側(cè)重于優(yōu)化產(chǎn)品變化率的啟發(fā)式規(guī)則，不能優(yōu)化工作站負載和產(chǎn)品切換成本。表6為車間決策提供了多樣化的選擇，當(dāng)車間對產(chǎn)品之間的切換有較高限制時，可以選擇2，51，52，53號排序序列作為裝配線的生產(chǎn)方案；當(dāng)車間更側(cè)重于平衡工作站負載時，可以選擇1，3～8號解；當(dāng)車間需要低庫存、更快響應(yīng)客戶訂單時，可以選擇較小產(chǎn)品變化率的解，如1，4，6號解。無論以哪種目標(biāo)為主進行選擇，表6 中的解在其他兩個目標(biāo)值上都不會太差。本文所提算法已應(yīng)用于求解該中央空調(diào)的混流裝配線排序問題。

4 結(jié)束語

本文提出了考慮不同工作站上超載／閑置成本差異的最小化超載／閑置總成本目標(biāo)，建立了改進的最小化超載／閑置總成本、產(chǎn)品變化率和產(chǎn)品總切換時間的混流裝配線排序的多目標(biāo)數(shù)學(xué)優(yōu)化模型，并設(shè)計IMOCSO 算法進行求解。將標(biāo)準(zhǔn)CSO 算法離散化應(yīng)用于混流裝配線排序問題；為了提高算法前期的全局搜索能力和后期的局部尋優(yōu)能力，提出基于線性混合比率的貓行為模式選擇方法；為了解決算法應(yīng)用于混流裝配線排序問題中出現(xiàn)的冗余操作的問題，提出一種多樣化的搜尋算子。采用五個常用的多目標(biāo)評價指標(biāo)對基準(zhǔn)案例中的小規(guī)模、大規(guī)模問題集分別進行測試，并與三種傳統(tǒng)的算法MOPSO，NSGA2，SPEA2進行比較，以測試算法的性能。結(jié)果表明，本文提出的IMOCSO 算法在求解混流裝配線排序問題中具有良好的性能，尤其在處理大規(guī)模問題時算法的收斂速度明顯。在實例驗證部分，將該IMOCSO 算法應(yīng)用于某空調(diào)企業(yè)的混流裝配線排序問題。

本文為探索和解決CSO 算法在混流裝配線排序問題中的應(yīng)用進行了嘗試，并為解決其他調(diào)度問題，如作業(yè)車間調(diào)度、流水車間調(diào)度應(yīng)用中的問題提供了借鑒和幫助，具有重要的理論意義。下一步工作將研究建立更加符合生產(chǎn)實際的混流裝配線模型，如隨機型混流裝配線排序模型，以減小原始數(shù)據(jù)誤差對優(yōu)化結(jié)果的影響，即得到魯棒性較高的排序方案；測試貓群算法在更大規(guī)模問題中的求解性能，以用于更大規(guī)模實際問題的求解，如產(chǎn)品類型更多、工作站數(shù)目更大的排序問題。

［1］BARD J F，DAR-ELJ E，SHTUB A.An analytic framework for sequencing mixed model assembly lines［J］.International Journal of Production Research，1992，30（1）：35-48.

［2］TAVAKKOLI-MOGHADDAM R，RAHIMI-VAHED A.Multi-criteria sequencing problem for a mixed-model assembly line in a JIT production system［J］.Applied Mathematics and Computation，2006，181（2）：1471-1481.

［3］FATTAHI P，SALEHI M.Sequencing the mixed-model assembly line to minimize the total utility and idle costs with variable launching interval［J］.The International Journal of Advanced Manufacturing Technology，2009，45（9）：987-998.

［4］MANSOURI S A.A multi-objective genetic algorithm for mixed-model sequencing on JIT assembly lines［J］.European Journal of Operational Research，2005，167（3）：696-716.

［5］AKGüNDüZ O S，TUNALI S.An adaptive genetic algorithm approach for the mixed-model assembly line sequencing problem［J］.International Journal of Production Research，2010，48（17）：5157-5179.

［6］HYUN C J，KIM Y，KIM Y K.A genetic algorithm for multiple objective sequencing problems in mixed model assembly lines［J］.Computers &Operations Research，1998，25（7／8）：675-690.

［7］LEU Y Y，MATHESON L A，REES L P.Sequencing mixedmodel assembly lines with genetic algorithms［J］.Computers&Industrial Engineering，1996，30（4）：1027-1036.

［8］MORADI H，ZANDIEH M，MAHDAVI I.Non-dominated ranked genetic algorithm for a multi-objective mixed-model assembly line sequencing problem［J］.International Journal of Production Research，2011，49（12）：3479-3499.

［9］DONG Qiaoying，KAN Shulin，GUI Yuankun，et al.Mixed model assembly line multi-objective sequencing based on modified discrete particle swarm optimization algorithm［J］.Journal of System Simulation，2009，21（22）：7103-7108（in Chinese）.［董巧英，闞樹林，桂元坤，等.基于改進離散微粒群優(yōu)化算法的混流裝配線多目標(biāo)排序［J］.系統(tǒng)仿真學(xué)報，2009，21（22）：7103-7108.］

［10］RAHIMI-VAHED A，MIRZAEI A H.A hybrid multi-objective shuffled frog-leaping algorithm for a mixed-model assembly line sequencing problem［J］.Computers &Industrial Engineering，2007，53（4）：642-666.

［11］WANG Guangbiao，YANG Shuying，F(xiàn)ENG Fan，et al.Research of image classification based on cat swarm optimization［J］.Journal of Tianjin University of Technology，2012，27（5）：35-39（in Chinese）.［王光彪，楊淑瑩，馮 帆，等.基于貓群算法的圖像分類研究［J］.天津理工大學(xué)學(xué)報，2012，27（5）：35-39.］

［12］CHU S C，TSAI P W，PAN J S.Cat swarm optimization［J］.Lecture Notes in Computer Science，2006，4099：854-858.

［13］CHU S C，TSAI P W.Computational intelligence based on the behavior of cats［J］.International Journal of Innovative Computing，Information and Control，2007，3（1）：163-173.

［14］PRADHAN P M，PANDA G.Solving multiobjective problems using cat swarm optimization［J］.Expert Systems with Applications，2012，39（3）：2956-2964.

［15］OROUSKHANI M，MANSOURI M，TESHNEHLAB M.Average-inertia weighted cat swarm optimization［J］.Lecture Notes in Computer Science，2011，6728：321-328.

［16］TSAI P W，PAN J S，CHEN S M，et al.Parallel cat swarm optimization［M］.Washington，D.C.，USA：IEEE，2008：3328-3333.

［17］KALAISELVAN G，LAVANYA A，NATRAJAN V.Enhancing the performance of watermarking based on cat swarm optimization method［C］／／Proceedings of 2011International Conference on Recent Trends in Information Technology.Washington，D.C.，USA：IEEE，2011：1081-1086.

［18］LIN K C，CHIEN H Y.CSO-based feature selection and parameter optimization for support vector machine［M］.Washington，D.C.，USA：IEEE，2009：783-788.

［19］DEB K，AGRAWAL S，PRATAP A，et al.A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization：NSGA-II［J］.Lecture Notes in Computer Science，2000，1917：849-858.

［20］COELLO COELLO C A，LECHUGA M S.MOPSO：aproposal for multiple objective particle swarm optimization［M］.Washington，D.C.，USA：IEEE，2002：1051-1056.

［21］ZITZLER E，THIELE L.Multiobjective evolutionary algorithms：a comparative case study and the strength pareto approach［J］.IEEE Transactions on Evolutionary Computation，1999，3（4）：257-271.