萬曉琴，嚴(yán)洪森

（1.東南大學(xué) 自動(dòng)化學(xué)院，江蘇 南京 210096；2.東南大學(xué)復(fù)雜工程系統(tǒng)測(cè)量與控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210096）

0 引言

知識(shí)化制造系統(tǒng)（Knowledgeable Manufacturing System，KMS）是于2000年提出的一種帶有“六自”特征的新的制造理念［1］，致力于解決現(xiàn)有制造模式中存在的模式單一、缺乏靈活性、不能滿足制造企業(yè)需求多樣性及重復(fù)研發(fā)等問題。自重構(gòu)是KMS重要的特征之一，也是現(xiàn)代制造系統(tǒng)中迫切需要的功能，其自重構(gòu)包括KMS管理與控制軟件的自重構(gòu)［2］、硬件的重構(gòu)兩方面內(nèi)容。

對(duì)制造系統(tǒng)的硬件進(jìn)行重構(gòu)已引起研究者越來越多的關(guān)注，其目的在于以低成本的重構(gòu)方式快速改變系統(tǒng)的構(gòu)形［3］。梁福軍等［4］對(duì)可重構(gòu)制造系統(tǒng)（Reconfigurable Manufacturing System，RMS）的結(jié)構(gòu)、組成、類別及理論體系進(jìn)行了研究。KATZR［5］研究了可重構(gòu)機(jī)床（Reconfigurable Machine Tool，RMT）的設(shè)計(jì)原則，通過調(diào)整RMT的組成模塊，快速實(shí)現(xiàn)機(jī)床結(jié)構(gòu)的變化，達(dá)到轉(zhuǎn)變加工任務(wù)的目的。文獻(xiàn)［6－9］針對(duì)可重構(gòu)零件族進(jìn)行了深入研究，采用改變?cè)O(shè)備物理位置、增減設(shè)備的數(shù)量及更換設(shè)備上的加工模塊等方法實(shí)現(xiàn)制造單元內(nèi)硬件的物理重構(gòu)，解決生產(chǎn)線零件族中各零件在確定或隨機(jī)需求情況下的構(gòu)形優(yōu)化問題。文獻(xiàn)［10］針對(duì)單件小批量生產(chǎn)提出面向多工序加工系統(tǒng)的分層可重構(gòu)工藝規(guī)劃體系構(gòu)架，以非加工時(shí)間和相對(duì)時(shí)間偏差為目標(biāo)，建立了可重構(gòu)工藝規(guī)劃的數(shù)學(xué)模型。文獻(xiàn)［11］提出一種從加工序列、機(jī)床、刀具和切削參數(shù)等多個(gè)因素，對(duì)復(fù)雜零件工藝方案進(jìn)行全局多層并行優(yōu)化的方法。目前，對(duì)硬件重構(gòu)的研究主要集中在制造系統(tǒng)的物理重構(gòu)上，然而現(xiàn)有制造系統(tǒng)設(shè)備的位置大多被固定，想要移動(dòng)設(shè)備并非易事。對(duì)于工藝規(guī)劃可重構(gòu)的研究大多針對(duì)當(dāng)前產(chǎn)品特征及設(shè)備能力進(jìn)行重構(gòu)，是對(duì)制造系統(tǒng)進(jìn)行首次構(gòu)建，目前關(guān)于充分利用原生產(chǎn)線已有制造系統(tǒng)資源的重構(gòu)研究還較少。

針對(duì)以上不足，本文對(duì)KMS多產(chǎn)品工藝路線邏輯重構(gòu)問題進(jìn)行數(shù)學(xué)建模。當(dāng)產(chǎn)品數(shù)量和混合比發(fā)生變化時(shí)，在充分利用原生產(chǎn)線已有資源的基礎(chǔ)上，適當(dāng)調(diào)整產(chǎn)品的工藝加工路線，快速響應(yīng)當(dāng)前的生產(chǎn)需求。提出一種改進(jìn)的混沌非支配排序遺傳算法（Nondominated Sorting Genetic Algorithm，NSGA）優(yōu)化各產(chǎn)品工藝加工路線，在對(duì)目標(biāo)函數(shù)無偏好的情況下，為決策者提供多種可選工藝路徑重構(gòu)方案。

1 問題描述與模型建立

1.1 問題描述

KMS產(chǎn)品工藝路線重構(gòu)問題可以描述為：知識(shí)化制造單元內(nèi)有m臺(tái)機(jī)器，所有緩沖區(qū)容量為無限大；可加工n種工件，各工件包含由多道工序組成的工序集，每道工序可在多臺(tái)性能不同的機(jī)器上加工，工序的加工時(shí)間因機(jī)器性能不同而不同；受市場(chǎng)需求變化的影響，待加工的工件種類及數(shù)量發(fā)生變化，當(dāng)原有生產(chǎn)線的生產(chǎn)能力已經(jīng)不能滿足現(xiàn)在市場(chǎng)需求時(shí)，對(duì)生產(chǎn)線進(jìn)行邏輯重構(gòu)，在充分利用已有資源的基礎(chǔ)上，優(yōu)化各產(chǎn)品工藝路線，使其滿足生產(chǎn)需求且重構(gòu)成本最低。

制造單元內(nèi)需要加工多種工件，每種工件有多條可選工藝路線。現(xiàn)做如下假設(shè)：

（1）機(jī)器故障率為0。

（2）工件加工遵守先到先服務(wù)的調(diào)度規(guī)則。

（3）工件可在同一臺(tái)機(jī)器上加工不同工序。

（4）每道工序可在多臺(tái)性能不同的機(jī)器上加工。

（5）每一時(shí)刻每臺(tái)機(jī)器只能加工一個(gè)工件。

（6）一個(gè)工件在同一時(shí)刻只能在一臺(tái)機(jī)器上加工。

（7）工序的準(zhǔn)備時(shí)間與順序無關(guān)，包含在加工時(shí)間內(nèi)。

（8）各工件的到達(dá)過程為泊松過程，服務(wù)時(shí)間服從負(fù)指數(shù)分布。

（9）原生產(chǎn)線包含了待加工工件的所有工序加工能力。

1.2 模型建立

1.2.1 輸入信息

m為車間內(nèi)的設(shè)備總數(shù)，設(shè)備編號(hào)為1，2，…，m，h＝1，2，…，m；

n為制造單元內(nèi)待加工的工件種類總數(shù)，工件種類依次編號(hào)為1，2，…，n，p＝1，2，…，n；

k為知識(shí)化制造單元內(nèi)可加工的所有工序的總數(shù)，所有可加工工序依次編號(hào)為1，2，…，k，x，y＝1，2，…，k；

J［1，…，n］為各工件包含的工序數(shù)目矩陣，J（p）即第p 類工件包含的工序數(shù)目，i，j＝1，…，J（p）；

Op［1，…，J（p）］為第p類工件包含的工序集；

Gp［1，…，J（p）］［1，…，J（p）］為第p類工件工序優(yōu)先級(jí)矩陣；

由1.1節(jié)假設(shè)（7）可知：對(duì)于某類工件p，相繼到達(dá)的兩個(gè)第p類型工件之間的時(shí)間間隔為獨(dú)立同分布的，服從參數(shù)為λp的負(fù)指數(shù)分布。第p類工件的第i道工序Op（i）若能在機(jī)器m上加工，則加工時(shí)間服從參數(shù)為τp，i，h的負(fù)指數(shù)分布。

1.2.2 原生產(chǎn)線描述

n0為原生產(chǎn)線加工的工件種類數(shù)，p0＝1，2，…，n0；

P0p0［1，…，J（p0）］為原生產(chǎn)線加工第p0類工件的工序序列，工序的加工先后順序?yàn)镻0p0（1），P0p0（2），…，P0p0（J（p0））；

M0p0［1，…，J（p0）］為原生產(chǎn)線第p0類工件工序加工對(duì)應(yīng)的機(jī)器序列。

Pp［1，…，J（p）］為第p類工件工藝路線重構(gòu)后的工序序列；

Mp［1，…，J（p）］為第p類工件工藝路線重構(gòu)后工序加工對(duì)應(yīng)的機(jī)器序列；

同上，可以得到第p類工件工藝路線重構(gòu)后的工序在各機(jī)器上的分配方案矩陣：

Ap［1，…，k］［1，…，m］，

該目標(biāo)函數(shù)是最小化平均在制品水平，本文假設(shè)各緩沖區(qū)的容量為無限大，生產(chǎn)線達(dá)到穩(wěn)定情況下，產(chǎn)品的到達(dá)率等于生產(chǎn)率。在給定工件生產(chǎn)率的前提下，優(yōu)化工件工藝路線，使各工件逗留時(shí)間ST（工件從進(jìn)入制造系統(tǒng)到完成生產(chǎn)離開該系統(tǒng)所需要的時(shí)間）最短。本文利用文獻(xiàn)［12－13］提出的排隊(duì)網(wǎng)絡(luò)分析方法，計(jì)算出工件在機(jī)器上的加工時(shí)間和等待時(shí)間，再加上工件在加工路線上的運(yùn)輸時(shí)間（假設(shè)運(yùn)輸時(shí)間與機(jī)器之間的距離成正比），最后計(jì)算出第p類工件的ST（p）由工件的加工時(shí)間、等待時(shí)間及運(yùn)輸時(shí)間三部分組成。由Little公式可知，生產(chǎn)線的平均在制品水平等于工件的逗留時(shí)間乘以到達(dá)率，其物理意義是最小化平均在制品數(shù)量。

該目標(biāo)是計(jì)算重構(gòu)后的生產(chǎn)線與原生產(chǎn)線相比，機(jī)器加工與原來不同種類工序的總數(shù)目。三個(gè)符號(hào)∪，∩和～分別表示兩矩陣對(duì)應(yīng)位置元素間進(jìn)行與、或、非邏輯運(yùn)算。其物理意義是制造單元內(nèi)重構(gòu)前后相同機(jī)器加工不同工序時(shí)由工人熟練程度和更換刀具等帶來的生產(chǎn)成本。

命題1 Dif為重構(gòu)后的生產(chǎn)線與原生產(chǎn)線相比，相同機(jī)器加工與原來不同種類工序的數(shù)目總和。

證明 由1.2.2節(jié)和1.2.3節(jié)可知，A0p0，Ap均為k×m維0／1矩陣，當(dāng)A0p0（x，h），Ap（x，h）值為1時(shí)，分別表示第p和p0類產(chǎn)品的編號(hào)為x的工序在編號(hào)為h的機(jī)器上進(jìn)行加工，值為0時(shí)表示第p和p0類產(chǎn)品不包括編號(hào)為x的工序，或者編號(hào)為x的工序不在編號(hào)為h的機(jī)器上進(jìn)行加工。令（A0p0），表示原生產(chǎn)線加工n0種工件時(shí)k種工序在m 種機(jī)器上的加工分配情況表示重構(gòu)后生產(chǎn)線加工n種工件時(shí)k道工序在m臺(tái)機(jī)器上的加工分配情況。A3＝｛～A1∩A2｝。

（1）A1（x，h）＝1，A2（x，h）＝1，表示原生產(chǎn)線和重構(gòu)后的生產(chǎn)線，工序編號(hào)為x的工序均在機(jī)器編號(hào)為h的機(jī)器上加工，此時(shí)A3（x，h）＝0。

（2）A1（x，h）＝1，A2（x，h）＝0，表示原生產(chǎn)線編號(hào)為x的工序在編號(hào)為h的機(jī)器上加工，重構(gòu)后編號(hào)為x的工序不在編號(hào)為h的機(jī)器上加工，此時(shí)A3（x，h）＝0。

（3）A1（x，h）＝0，A2（x，h）＝1，表示原生產(chǎn)線編號(hào)為x的工序不在編號(hào)為h的機(jī)器上加工，重構(gòu)后編號(hào)為x的工序在編號(hào)為h的機(jī)器上加工，此時(shí)A3（x，h）＝1。

（4）A1（x，h）＝0，A2（x，h）＝0，表示原生產(chǎn)線和重構(gòu)后的生產(chǎn)線，工序編號(hào)為x的工序均不在機(jī)器編號(hào)為h的機(jī)器上加工，此時(shí)A3（x，h）＝0。

對(duì)于上述四種情況，僅在情況（3）中，對(duì)于機(jī)器h，重構(gòu)前不加工編號(hào)為x的工序，而重構(gòu)后需對(duì)編號(hào)為x的工序進(jìn)行加工，這種重構(gòu)前后〈機(jī)器，工序〉的分配變化會(huì)增加生產(chǎn)成本（由工人熟練程度和更換刀具等帶來的成本）。情況（2）中，對(duì)于重構(gòu)后的生產(chǎn)線而言，機(jī)器h并未增添新的工序，不會(huì)增加成本，故不計(jì)入〈機(jī)器，工序〉的變動(dòng)數(shù)目中。此目標(biāo)等價(jià)于 min Dif ＝ ∑x，h｛A3（x，h）＝1｝，即重構(gòu)前后〈機(jī)器，工序〉的分配變化數(shù)目的總和。證畢。

1.2.5 數(shù)學(xué)模型

其中：式（3）為加工完整性約束，該約束保證每個(gè)工件的每道工序都能分配到某臺(tái)機(jī)器上進(jìn)行加工；式（4）是機(jī)器加工可行性約束，該約束保證各工序分配到的機(jī)器能進(jìn)行此工序的加工；式（5）是工序優(yōu)先約束，該約束保證工件的加工順序滿足工序優(yōu)先約束，SOp（i），SOp（j）是工序Op（i），Op（j）在加工方案中的加工次序；式（6）是逗留時(shí)間約束，當(dāng)生產(chǎn)率接近制造系統(tǒng)容量時(shí)，逗留時(shí)間會(huì)趨于無限大［14］，使生產(chǎn)線在制品水平劇增，因此將逗留時(shí)間約束在一定范圍內(nèi)，ST0（p）為第p類產(chǎn)品的最大逗留時(shí)間。

2 改進(jìn)混沌非支配排序遺傳算法

NSGA具有可對(duì)多個(gè)目標(biāo)并行優(yōu)化、能夠同時(shí)獲得多個(gè)Pareto最優(yōu)解等特點(diǎn)，在多目標(biāo)優(yōu)化問題求解中得到越來越廣泛的應(yīng)用［15－16］。將混沌理論與NSGA相結(jié)合，利用混沌搜索技術(shù)較好的遍歷性特點(diǎn)，有助于提高NSGA的局部搜索能力。目前混沌NSGA中的混沌映射主要基于Logistic映射和Tent映射。文獻(xiàn)［17］在算法中加入混沌算子，用Logistic映射的混沌序列產(chǎn)生子代種群，文獻(xiàn)［18－19］在NSGA的交叉變異算子的參數(shù)中引用Logistic映射，但由于Logistic映射遍歷不均勻的特性會(huì)影響尋優(yōu)的速度與結(jié)果。文獻(xiàn)［20］在多目標(biāo)遺傳算法（Genetic Algorithm，GA）中引入改進(jìn)Tent映射的自適應(yīng)變尺度混沌優(yōu)化方法，為了避免出現(xiàn)Tent映射迭代中陷入的小周期點(diǎn)和不動(dòng)點(diǎn)，需要在每次映射迭代過程中循環(huán)檢測(cè)小周期點(diǎn)和不動(dòng)點(diǎn)。為此，本文采用Skew Tent映射［21］，提出一種改進(jìn)混沌NSGA，使之具有較好的遍歷均勻性，而且避免了計(jì)算機(jī)進(jìn)行多次迭代后陷入小周期點(diǎn)和不動(dòng)點(diǎn)。

2.1 編碼與解碼

本文采用一種基于工序和機(jī)器的編碼方式，染色體長度為所有待加工工件工序數(shù)目之和的兩倍。前半段染色體采用基于工序優(yōu)先權(quán)的編碼方式［8，15］。染色體中基因的位置表示工件的各道工序，基因的值代表工序的優(yōu)先權(quán)，優(yōu)先權(quán)的任何改變通常導(dǎo)致不同的拓?fù)渑判?，這種編碼方式本質(zhì)上能夠表示給定工序優(yōu)先圖的所有可行工序加工排序。染色體后半段（如圖1中b）每個(gè)基因的值是在［1，m］之間的任意一個(gè)隨機(jī)整數(shù)，其中m為車間的設(shè)備總數(shù)。在此編碼的基礎(chǔ)上，提出一種基于工序優(yōu)先約束矩陣Gp和候選機(jī)器集的解碼方法，以獲得可行的產(chǎn)品加工工序序列及加工機(jī)器。下面以圖2中的工件C為例說明染色體的編碼與解碼。

工件C包含19道工序，工序優(yōu)先圖如圖2c所示，則染色體的前半段（如圖1中a）每個(gè)基因的值是一個(gè)［1，19］之間唯一的整數(shù)值，構(gòu)成了一個(gè)19個(gè)數(shù)的排列，數(shù)值越大表示相應(yīng)基因位置代表的工序的優(yōu)先權(quán)越高。

關(guān)于第p類工件工序加工序列解碼如下：

根據(jù)1.2.1節(jié)中工件的Gp矩陣及染色體信息，可解碼為一個(gè)可行的工件加工序列，算法如下：

步驟1 找出Gp矩陣中元素全為0的列i，…，j所對(duì)應(yīng)工序Op（i），…，Op（j）在染色體中的優(yōu)先權(quán)值。

步驟2 找出染色體優(yōu)先權(quán)值中的最大值對(duì)應(yīng)的工序列Op（l）并輸出（l∈i，…，j），將染色體中此最大優(yōu)先權(quán)值置0。

步驟3 將Gp矩陣的第l行置0。

步驟4 重復(fù)步驟1～ 步驟3共J（p）－1次，即可得到符合工序優(yōu)先約束的工件加工工序序列。

第p類工件的工序?qū)?yīng)的加工機(jī)器解碼方法如下：令染色體后半段編碼中OPi對(duì)應(yīng)的基因的值為gi，候選機(jī)器總數(shù)為~ni，則

式中b的取值保證0＜~ki≤~ni即可，即選擇候選機(jī)器的第~ki臺(tái)機(jī)器加工工序OPi。

如圖1b所示，工序OP1對(duì)應(yīng)編碼基因的值為6，機(jī)器與工序加工關(guān)系如表1所示，則工序OP1可由兩種候選機(jī)器｛M3，M6｝進(jìn)行加工。由~ki＝6－2×2＝2，OP1在兩臺(tái)候選機(jī)器中的第2臺(tái)機(jī)器，即M6機(jī)器上加工，加工時(shí)間為8s。此方法解碼得到的工序分配方案必定滿足機(jī)器加工可行性約束。

表1 各道工序在機(jī)器上的加工時(shí)間s

續(xù)表1

圖1解碼后，工件C的工序加工順序及所選機(jī)器如圖3所示。

圖3中第一行為工序的加工順序序列，第二行為對(duì)應(yīng)于第一行的工序所選的加工機(jī)器序列。即工件C首先在機(jī)器M6上加工工序OP1，然后在機(jī)器M4上加工工序OP2，后面的工序及機(jī)器以此類推。

2.2 選擇、交叉、變異算子及混沌擾動(dòng)

（1）選擇算子 輪盤賭選擇方式，即根據(jù)每個(gè)染色體適應(yīng)值的比例來確定該個(gè)體的選擇概率。

（2）交叉算子 前半段染色體采用次序雜交（order crossover）的方式［15］，雜交過程如圖4所示。后半段染色體采用經(jīng)典的部分匹配交叉，即交換父代交叉點(diǎn)之間的子串內(nèi)容。

（3）變異算子 前半段和后半段染色體均采用交換變異，隨機(jī)選擇兩個(gè)基因位置，然后交換它們的基因值。

（4）混沌擾動(dòng)算子 斜帳篷映射［21］（Skew Tent）結(jié)構(gòu)簡單，具有較好的遍歷均勻性。其數(shù)學(xué)表達(dá)式為

當(dāng)as＝0.5時(shí)即為Tent映射。計(jì)算機(jī)在進(jìn)行Tent映射時(shí)，實(shí)際上是將小數(shù)部分的二進(jìn)制數(shù)進(jìn)行無符號(hào)左移，又因?yàn)橛?jì)算機(jī)字長有限，小數(shù)部分經(jīng)過一定次數(shù)的左移運(yùn)算將趨于0［22］，影響搜索結(jié)果。在改進(jìn)的混沌擾動(dòng)算子中取as∈ （0，0.5）∪ （0.5，1）。為避免染色體不同位置基因具有相同初值tks時(shí)，Skew Tent映射產(chǎn)生相同的搜索序列，在改進(jìn)的混沌擾動(dòng)算子中針對(duì)每一基因，對(duì)as賦以（0，0.5）∪ （0.5，1）區(qū)間內(nèi)的隨機(jī)值，再利用具有不同as參數(shù)的Skew Tent映射對(duì)染色體后半段進(jìn)行局部擾動(dòng)，即在工序加工順序一定的情況下，對(duì)工序所屬的機(jī)器進(jìn)行重新搜索尋優(yōu)。

改進(jìn)的混沌擾動(dòng)算子步驟如下：

步驟1 設(shè)置最大迭代次數(shù)K＊，記錄個(gè)體的目標(biāo)值WIP＊和Dif＊。令迭代步數(shù)初值k＊＝1，隨機(jī)產(chǎn)生向量a＝［a1，…，as，…，aq］，as∈（0，0.5）∪（0.5，1）。

步驟5 k＊＋1→k＊，若k＊≤K＊，則轉(zhuǎn)步驟2，否則算法結(jié)束。

2.3 適應(yīng)值分配機(jī)制及Pareto解集過濾器

采用群體排序技術(shù)尋找Pareto最優(yōu)解。根據(jù)遺傳算法中個(gè)體的相互支配關(guān)系對(duì)個(gè)體進(jìn)行分級(jí)，每一代的非支配解作為第1級(jí)點(diǎn)，剩下的個(gè)體所分配的級(jí)數(shù)等于支配該個(gè)體的數(shù)量加1。

定義1 群體分級(jí)后每個(gè)個(gè)體的適應(yīng)度為

式中：fi為第i個(gè)個(gè)體的適應(yīng)度，ci為群體中第i個(gè)個(gè)體的級(jí)數(shù)，pop為群體規(guī)模。由上式可以看出，相同等級(jí)的個(gè)體都具有相同的適應(yīng)度，這樣算法就不會(huì)只收斂到一點(diǎn)，而是收斂到一個(gè)非劣解集合。

Pareto解集過濾器存儲(chǔ)每代產(chǎn)生的非劣解。在每一代中，過濾器中的解集通過加入新產(chǎn)生的Pareto解和刪除所有支配解來更新。

規(guī)則1 當(dāng)產(chǎn)品工藝路線重構(gòu)后，該產(chǎn)品逗留時(shí)間大于最大逗留時(shí)間，即不滿足式（6）時(shí)，適應(yīng)值置0。

3 應(yīng)用實(shí)例

某沖壓車間內(nèi)有19臺(tái)機(jī)器，原生產(chǎn)線加工E和D兩種工件，生產(chǎn)率分別為65件／h和22件／h。由于市場(chǎng)需求變化，現(xiàn)要求生產(chǎn)D和C兩種工件，生產(chǎn)率要求分別為65件／h和25件／h。要求對(duì)產(chǎn)品工藝路線進(jìn)行規(guī)劃，使其滿足生產(chǎn)率要求且重構(gòu)成本最小。機(jī)器間的距離矩陣如表2所示，設(shè)備加工各工序的時(shí)間如表1所示。各工件的工序優(yōu)先圖如圖2所示。原生產(chǎn)線信息如下：

工件E工序加工順序?yàn)镻E＝｛7，1，2，5，11，3，4，6，14，8，19，16，9，10，17，18｝；

工件D工序加工順序?yàn)镻D＝｛1，7，8，16，2，3，5，6，14，4，12，9，10，17，18，13｝；

工件E工序加工對(duì)應(yīng)的機(jī)器為ME＝｛5，6，3，12，13，6，2，10，8，9，11，1，4，6，10，7｝；

工件D工序加工對(duì)應(yīng)的機(jī)器為MD＝｛6，5，9，1，3，6，12，10，8，2，9，4，6，10，7，9｝。

表2 制造單元內(nèi)設(shè)備間距離矩陣m

所有程序在MATLAB平臺(tái)上仿真運(yùn)行，具體算法參數(shù)設(shè)置為：種群規(guī)模pop＝80，進(jìn)化代數(shù)genmax＝500，交叉率pc＝0.9，變異率pm＝0.3，混沌迭代次數(shù)K＊＝300。在不同生產(chǎn)率需求條件下，針對(duì)工件D的工藝路線重構(gòu)和不重構(gòu)兩種情況，對(duì)制造系統(tǒng)的性能進(jìn)行比較分析。采用C－NSGA解決多目標(biāo)優(yōu)化問題，經(jīng)過多次獨(dú)立運(yùn)行，得到Pareto最優(yōu)解分布圖如圖5所示。圖中WIP（單位：個(gè)）為生產(chǎn)線中的平均在制品數(shù)量，為優(yōu)化目標(biāo)中的第一個(gè)目標(biāo)值；Dif（單位：個(gè)）為重構(gòu)后的生產(chǎn)線與原生產(chǎn)線相比，相同機(jī)器加工與原來不同種類工序的數(shù)目總和，為第二個(gè)優(yōu)化目標(biāo)值。在生產(chǎn)率需求較小的情況下（如圖5a），當(dāng)Dif值相同時(shí)，重構(gòu)后生產(chǎn)線的平均在制品數(shù)量略少，此時(shí)生產(chǎn)線可以不進(jìn)行邏輯重構(gòu)。當(dāng)生產(chǎn)率需求增加時(shí)，工件D的工藝路線重構(gòu)和不重構(gòu)兩種情況下，生產(chǎn)系統(tǒng)WIP數(shù)量差別越來越大，如圖5b所示。當(dāng)工件D和C的需求率分別為68件／h和29件／h時(shí)，若D工件工藝路線不重構(gòu)，則生產(chǎn)線的WIP數(shù)量達(dá)到50，如圖5c所示。這兩種情況可認(rèn)為生產(chǎn)線已不滿足需求，必須進(jìn)行邏輯重構(gòu)。表3列出了圖5b中工藝路線重構(gòu)的7種方案，各方案對(duì)應(yīng)的產(chǎn)品工藝加工路線如表4所示。

表3 重構(gòu)方案

表4 重構(gòu)后的產(chǎn)品加工工藝路線

續(xù)表4

NSGA－Ⅱ［23］是求解多目標(biāo)問題的一種比較成熟的算法。下面比較C－NSGA和NSGA－Ⅱ在Pareto解的取值和解的個(gè)數(shù)兩方面的性能。在λB＝65件／h和λC＝25件／h情況下，獨(dú)立運(yùn)行C－NSGA和NSGA－Ⅱ程序各30次。

比較分析結(jié)果如下：

從表5和圖6可以看出，與NSGA－Ⅱ相比，CNSGA在解的多樣性上表現(xiàn)較優(yōu)，一般能得到5或6個(gè)非支配解。在Dif值相同時(shí)，C－NSGA能得到更小的WIP值，且最大值與最小值的差距較小，解的穩(wěn)定性更好。

表5 C－NSGA和NSGA－Ⅱ運(yùn)行情況對(duì)照表

從圖5可以看出，優(yōu)化的兩個(gè)目標(biāo)之間存在矛盾，當(dāng)WIP數(shù)目減少時(shí)，Dif的數(shù)目增加，反之亦然。在不同生產(chǎn)率需求下，重構(gòu)后生產(chǎn)線的性能更優(yōu)；生產(chǎn)率越高，重構(gòu)的優(yōu)勢(shì)越能體現(xiàn)。Pareto解集列出了兩目標(biāo)函數(shù)解空間內(nèi)可能的最優(yōu)解，從而增加了決策者可選擇的空間，最終兩個(gè)目標(biāo)函數(shù)間如何平衡，由決策者根據(jù)經(jīng)驗(yàn)確定。表4給出了各種重構(gòu)方案對(duì)應(yīng)的產(chǎn)品加工工藝路線，在決策者根據(jù)各個(gè)目標(biāo)函數(shù)的相對(duì)重要性確定了目標(biāo)函數(shù)值后，就可以從表4中找到與其對(duì)應(yīng)的產(chǎn)品重構(gòu)后的工藝路線。

4 結(jié)束語

本文對(duì)知識(shí)化制造環(huán)境下的多產(chǎn)品工藝路徑規(guī)劃問題進(jìn)行了研究，在不考慮各目標(biāo)函數(shù)間權(quán)重分配的情況下，對(duì)兩個(gè)相互沖突的目標(biāo)函數(shù)進(jìn)行并行優(yōu)化，得到一組Pareto可行解。決策者可以根據(jù)不同企業(yè)對(duì)目標(biāo)的不同偏好，從候選解集中選出最符合要求的重構(gòu)方案。當(dāng)工件的種類和需求數(shù)量發(fā)生變化時(shí)，在充分利用原有資源的基礎(chǔ)上，KMS能夠做出快速響應(yīng)，很快形成一條新的生產(chǎn)線。需要指出的是，文本目前只考慮了工藝路線的邏輯重構(gòu)，在實(shí)際生產(chǎn)中，有些情況下的工藝由生產(chǎn)線上的機(jī)器決定，例如，在新加入的零件工藝中，當(dāng)含有原系統(tǒng)不能完成的工序，或者相關(guān)工序的可用機(jī)器集內(nèi)的機(jī)器指派調(diào)整受限，或者產(chǎn)品需求大大超過生產(chǎn)線最大生產(chǎn)能力時(shí)，僅進(jìn)行工藝路線的重構(gòu)無法滿足生產(chǎn)能力的提升，需要對(duì)機(jī)器種類和數(shù)量進(jìn)行更換，同時(shí)考慮工藝路線重構(gòu)和機(jī)器重構(gòu)（即物理重構(gòu)）將作為進(jìn)一步研究的內(nèi)容。

［1］ YAN Hongsen，LIU Fei.Knowledgeable manufacturing system—a new kind of advanced manufacturing system［J］.Computer Integrated Manufacturing Systems，2001，7（8）：7－11（in Chinese）.［嚴(yán)洪森，劉 飛.知識(shí)化制造系統(tǒng)——新一代先進(jìn)制造系統(tǒng)［J］.計(jì)算機(jī)集成制造系統(tǒng)，2001，7（8）：7－11.］

［2］ XUE Chaogai.Research into the self－reconfiguration of knowledgeable manufacturing system［D］.Nanjing：Southeast Uni－versity，2005（in Chinese）.［薛朝改.知識(shí)化制造系統(tǒng)的自重構(gòu)研究［D］.南京：東南大學(xué)，2005.］

［3］ KOREN Y，HEISEL U，JOVANE F，et a1.Reconfigurable manufacturing system［J］.CIRP Annals，1999，48（2）：527－540.

［4］ LIANG Fujun，NING Ruxin.Theoretical research of reconfigurable manufacturing system［J］.Chinese Journal of Mechanical Engineering，2003，39（6）：36－43（in Chinese）.［梁福軍，寧汝新.可重構(gòu)制造系統(tǒng)理論研究［J］.機(jī)械工程學(xué)報(bào)，2003，39（6）：36－43.］

［5］ KATZ R.Design principles of reconfigurable machines［J］.International Journal of Advanced Manufacturing Technology，2007，34（5）：430－439.

［6］ SON 段 .Design principles and methodologies for reconfigurable machining systems［D］.Ann Arbor，Mich.，USA：University of Michigan，2000.

［7］ YOUSSEF 段 A，EIMARAGHYH A.Availability consideration in the optimal selection of multiple－aspect RMS configurations［J］.International Journal of Production Research，2008，46（21）：5849－5882.

［8］ DOU Jianping，DAI Xianzhong，LI Jun.Optimization for multi－part flow－line configurations of reconfigurable manufacturing systems based on genetic algorithm［J］.Computer Integrated Manufacturing Systems，2010，16（7）：1390－1400（in Chinese）.［竇建平，戴先中，李 俊.基于遺傳算法的可重構(gòu)制造系統(tǒng)多零件流水線構(gòu)形優(yōu)化［J］.計(jì)算機(jī)集成制造系統(tǒng)，2010，16（7）：1390－1400.］

［9］ LOU Hongliang，YANG Jiangxin，LIN Yafu，et al.Reconfigurating policy of reconfigurable manufacturing systems based on graph theory［J］.Chinese Journal of Mechanical Engineering，2006，42（3）：22－29（in Chinese）.［樓洪梁，楊將新，林亞福，等.基于圖論的可重構(gòu)制造系統(tǒng)重構(gòu)策略［J］.機(jī)械工程學(xué)報(bào)，2006，42（3）：22－29.］

［10］ DUAN Jianguo，LI Aiping，XIE Nan，et al.Reconfigurable process planning for multi－stage machining systems［J］.Computer Integrated Manufacturing Systems，2011，17（6）：1215－1223（in Chinese）.［段建國，李愛平，謝 楠，等.面向多工序加工系統(tǒng)的可重構(gòu)工藝規(guī)劃［J］.計(jì)算機(jī)集成制造系統(tǒng)，2011，17（6）：1215－1223.］

［11］ CAI Ligang，ZHANG Jianshe，ZHANG Zhengyi，et al.Global multilayer and parallel process optimization of complex components［J］.Chinese Journal of Mechanical Engineering，2008，44（9）：6－12（in Chinese）.［蔡立剛，張建設(shè)，張正義，等.復(fù)雜零件工藝方案全局多層并行優(yōu)化［J］.機(jī)械工程學(xué)報(bào)，2008，44（9）：6－12.］

［12］ SEGAL M，WHITT W.A queueing network analyzer for manufacturing［C］／／Proceedings of the 12th International Teletraffic Conference.Amsterdam，the Netherlands：Elsevier，1989，2：1146－1152.

［13］ WHITT W.The queueing network analyzer［J］.Bell System Technology Journal，1983，62（9）：2779－2815.

［14］ WEIN 段 .On the relationship between yield and cycle time in semiconductor wafer fabrication［J］.IEEE Transaction on Semiconductor Manufacturing，1992，5（2）：156－158.

［15］ GEN M，CHENGR W.Genetic algorithms and engineering optimization［M］.New York，N.Y.，USA：John Wiley ＆Sons，2000.

［16］ CHENG 段 ，DAN Li.Multiobjective optimization design with Pareto genetic algorithm ［J］.Journal of Structural Engineering，1997，123（9）：1252－1261.

［17］ WANG Junping，HUANG Jun，HAN Renmin，et al.Chaotic－NSGA－Ⅱ：an effective algorithm to solve multi－objective optimization problems［C］／／Proceedings of the International Conference on Intelligent Computing and Integrated Systems.Washington，D.C.，USA：IEEE，2010：20－23.

［18］ LU Hui，NIU Ruiyao，LIU Jing，et al.Multicriteria decision mechanism CNSGA－AHP for the automatic test task scheduling problem［J］.Information Technology Journal，2012，11（10）：1449－1455.

［19］ PAN I，DAS A.Chaotic multi－objective optimization based design of fractional order PIλDμcontroller in AVR system［J］.Electrical Power and Energy Systems，2012，43（1）：393－407.

［20］ WANG Ruiqi，ZHANG Chenghui，LI Ke.Multi－objective genetic algorithm based on improved chaotic optimization［J］.Control and Decision，2011，26（9）：1391－1397（in Chinese）.［王瑞琪，張承慧，李 珂.基于改進(jìn)混沌優(yōu)化的多目標(biāo)遺傳算法［J］.控制與決策，2011，26（9）：1391－1397.］

［21］ HASLER M，MAISTRENKO 段 .An introduction to the synchronization of chaotic systems：coupled skew tent maps［J］.IEEE Transactions on Circuits and SystemsⅠ：Fundamental Theory and Applications，1997，44（10）：856－866.

［22］ SHAN Liang，QIANG Hao，LI Jun，et al.Chaotic optimization algorithm based on Tent map［J］.Control and Decision，2012，20（2）：179－182（in Chinese）.［單 梁，強(qiáng) 浩，李軍，等.基于Tent映射的混沌優(yōu)化算法［J］.控制與決策，2012，20（2）：179－182.］

［23］ DEB K，PRATAP A，AGARWAL S，et al.A fast and elitist multiobjective genetic algorithm：NSGA－Ⅱ［J］.IEEE Transactions on Evolutionary Computation，2002，6（2）：182－197.