改進(jìn)COOT算法求解多目標(biāo)柔性車間調(diào)度問(wèn)題

凌方平，吉衛(wèi)喜

江南大學(xué) 機(jī)械工程學(xué)院，江蘇 無(wú)錫214122

柔性作業(yè)車間調(diào)度問(wèn)題（flexible jobshop scheduling problem，F(xiàn)JSP）隸屬于NP-Hard 問(wèn)題，是Bruker 等[1]在1990年建立的，它是調(diào)度問(wèn)題中新的分支。此類問(wèn)題旨在充分利用有限的生產(chǎn)資料，協(xié)調(diào)生產(chǎn)部門間的需求，同時(shí)最大化生產(chǎn)獲益?，F(xiàn)階段離散制造企業(yè)中，車間對(duì)加工工件的機(jī)器和人員配置是靈活的、多樣的，因此FJSP 相較流水車間調(diào)度和普通作業(yè)車間調(diào)度，能更好地契合該生產(chǎn)實(shí)況，探討和解決FJSP具有重要意義。

元啟發(fā)式算法通過(guò)制衡全域搜索與區(qū)域搜索能力，能出色地尋優(yōu)求解NP-Hard 問(wèn)題。單目標(biāo)FJSP 的優(yōu)化目標(biāo)單一，大多根據(jù)完工時(shí)間比較不同調(diào)度方案的優(yōu)劣。諸多元啟發(fā)式算法一定程度上能在全局進(jìn)行搜索，在短時(shí)間內(nèi)得到此類問(wèn)題的最優(yōu)解或最優(yōu)解的近似解。連裕翔等[2]以最大完工時(shí)間為優(yōu)化指標(biāo)，為Jaya算法設(shè)計(jì)了迭代候選解集和新的鄰域結(jié)構(gòu)，最后用基準(zhǔn)實(shí)例集證明了改進(jìn)Jaya算法的有效性。

然而在現(xiàn)實(shí)的生產(chǎn)作業(yè)中，車間常會(huì)有其他考慮的方向，因此多目標(biāo)FJSP 應(yīng)運(yùn)而生。求解多目標(biāo)FJSP 常見(jiàn)的手段有兩種：一種對(duì)各個(gè)目標(biāo)賦予權(quán)重后加權(quán)計(jì)算，再用類似處理單目標(biāo)FJSP 的方法進(jìn)行解決。陳浩杰等[3]針對(duì)不同的資源受限情況，分類設(shè)計(jì)了歸一化方式，并改進(jìn)了遺傳規(guī)劃算法來(lái)解決問(wèn)題；Zhang等[4]在粒子群算法的基礎(chǔ)上，結(jié)合禁忌搜索算法來(lái)接近最優(yōu)解，從而化解了大規(guī)模多目標(biāo)FJSP。還有一種是使用Pareto思想的優(yōu)化策略。由Knowles等[5]構(gòu)建的多目標(biāo)問(wèn)題演化策略PAES、由Deb等[6]提出的把遺傳算法與非支配排序結(jié)合的NSGA-II 算法，常被學(xué)者進(jìn)行改進(jìn)，并用來(lái)求解多目標(biāo)FJSP。例如肖世昌等[7]提出了多目標(biāo)混合分布估計(jì)算法，得到了兼顧調(diào)度性能和魯棒性的Pareto 解集；鞠錄巖等[8]考慮了運(yùn)輸時(shí)間的影響，使用改進(jìn)的NSGA算法求解多目標(biāo)FJSP。

COOT 算法是一種根據(jù)鳥類群體行為提出的元啟發(fā)式算法，由Naruei 等[9]在2021 年提出，初衷是解決單目標(biāo)問(wèn)題，具有收斂速度快、參數(shù)設(shè)置簡(jiǎn)單、個(gè)體更新方式多樣的優(yōu)點(diǎn)。該算法雖然剛出現(xiàn)不久，但目前已被用于求解各種優(yōu)化問(wèn)題[10-11]。然而，COOT 算法應(yīng)用在生產(chǎn)調(diào)度領(lǐng)域的文獻(xiàn)極少，且算法性能仍有改進(jìn)的空間。因此，本文將COOT 算法擴(kuò)展應(yīng)用于FJSP，并對(duì)COOT算法進(jìn)行了一系列的改進(jìn)。

針對(duì)以上不足，本文構(gòu)建了以最小化最大完工時(shí)間、機(jī)器總負(fù)荷、耗能為優(yōu)化目的，且考慮了機(jī)器與工人柔性因素的車間調(diào)度模型。接著設(shè)計(jì)編解碼方式，確保個(gè)體位置信息與更新方式均為連續(xù)值的COOT 算法能被離散型的調(diào)度問(wèn)題使用。然后通過(guò)引入存檔集和Pareto 解的概念，使得原先只能解決單目標(biāo)問(wèn)題的COOT算法，擁有了解決多目標(biāo)問(wèn)題的能力。還改進(jìn)了算法中特定個(gè)體的更新方式以加快收斂速度，并更改其鄰域搜索方式，同時(shí)配合SA的思想，避免算法陷入局部最優(yōu)。最后通過(guò)算例進(jìn)行測(cè)試，以證明MOCOOT-SA的有效性。

本文的主要貢獻(xiàn)是：一是改進(jìn)了COOT 算法，使之能解決多目標(biāo)問(wèn)題。二是在FJSP的多目標(biāo)權(quán)重難以確定的情況下，提供了解決思路和方案。

1 問(wèn)題描述與模型建立

本文的多目標(biāo)柔性車間調(diào)度問(wèn)題描述如下：工廠現(xiàn)有l(wèi)個(gè)工人L={L1,L2,…,Ll},要在m個(gè)機(jī)器M={M1,M2,…,Mm} 上制作n個(gè)工件N={N1,N2,…,Nn}，工件的工藝路線是固定的、已知的，工件Ni有j道工序{Oi1,Oi2,…,Oij}，Mij?M和Lij?L分別是能加工工序Oij的機(jī)器和人，同一工序選擇了不同的機(jī)器或者人，導(dǎo)致它的加工時(shí)間可能不同。調(diào)度的目的是把每個(gè)工件的工序合理分配給工人，并安排工人在機(jī)器上加工，讓優(yōu)化目標(biāo)盡可能達(dá)到最優(yōu)。

建立問(wèn)題模型時(shí)，根據(jù)實(shí)際的加工情況，提出若干約束條件：

式（1）～（8）中，m為總的機(jī)器數(shù)，l為總的工人數(shù)，gi為工件i的總工序數(shù)，p為機(jī)器號(hào)，q為工人號(hào)，Sij為工序Oij的開始時(shí)間，Eij為工序Oij的結(jié)束時(shí)間，BTp為機(jī)器p的開機(jī)時(shí)間，CTp為機(jī)器p的關(guān)機(jī)時(shí)間，tijpq為工序Oij在機(jī)器p上被工人q加工所需的時(shí)間，Z為足夠大的正數(shù)。αijpq、βijrsp、γijrsq為0～1決策變量：如果工序Oij在機(jī)器p上被工人q加工，則αijpq=1，否則αijpq=0；如果工序Oij與Ors都在機(jī)器p上加工，且Oij先于Ors，則βijrsp=1，否則βijrsp=0；如果工序Oij與Ors都被工人q加工，且Oij先于Ors，則γijrsq=1，否則γijrsq=0。

式（1）表示每個(gè)工序的加工過(guò)程不會(huì)中斷，工序的完工時(shí)間等于開工時(shí)間加上加工所需時(shí)間；式（2）表示每個(gè)工序僅加工一次，且只能選一個(gè)工人和機(jī)器；式（3）表示只有在上道工序完成后，該工件才能開始下道工序的操作；式（4）表示所有機(jī)器在0時(shí)刻都已開動(dòng)，且可以被使用；式（5）表示每個(gè)機(jī)器在任何時(shí)間點(diǎn)只能加工一個(gè)工序；式（6）表示每個(gè)工人在任何時(shí)間點(diǎn)只能加工一個(gè)工序；式（7）表示所有工序的開工時(shí)間、完工時(shí)間和加工時(shí)長(zhǎng)都是非負(fù)數(shù)；式（8）表示任何一個(gè)機(jī)器，只有在完成了所有分配給它的任務(wù)后，才能關(guān)機(jī)。

調(diào)度的優(yōu)化目標(biāo)有三項(xiàng)：最大完工時(shí)間f1，機(jī)器總負(fù)荷f2，總耗能f3。以此建立數(shù)學(xué)模型，目標(biāo)函數(shù)為：

式（9）～（11）中，n為工件的總數(shù)，Di為工件i的完工時(shí)間，PYp為機(jī)器p的負(fù)載功率，PNp為機(jī)器p的空載功率。

2 編碼與解碼

2.1 編碼

標(biāo)準(zhǔn)COOT算法的初衷是解決連續(xù)性問(wèn)題，而調(diào)度問(wèn)題中機(jī)器、工序、人員的選擇都是離散的，因此直接用標(biāo)準(zhǔn)COOT算法來(lái)解決FJSP是無(wú)法實(shí)現(xiàn)的。編碼的方式在一定程度上影響算法的性能，本文選擇了基于工序的編碼方式。算法中的種群個(gè)體由位置向量表示，向量的長(zhǎng)度為，其中每個(gè)值的取值范圍為0至1間的隨機(jī)數(shù)，它與工序的對(duì)應(yīng)關(guān)系如圖1 所示。例子中共有3工件7工序，先將位置向量與有順序的工序編碼進(jìn)行映射，再將原向量升序排序，工序編碼隨之移動(dòng)，得到的[2 2 3 1 3 2 1]中，以工件2 為例，出現(xiàn)第幾次2 就代表是工件2的第幾道工序。如此，就得到一個(gè)有效的工件序列，記作List。

圖1 編碼樣例圖Fig.1 Coding sample map

這種編碼方式簡(jiǎn)潔明了，還確保了所有個(gè)體的位置信息都能轉(zhuǎn)化成合法的調(diào)度方案。

2.2 解碼

本文考慮了機(jī)器與工人的約束，采用了插入式貪婪的解碼方式。效仿文獻(xiàn)[12]提出的中繼衛(wèi)星調(diào)度任務(wù)構(gòu)成的時(shí)間窗口概念，把FJSP 中每個(gè)機(jī)器或者工人空閑的時(shí)間段稱為時(shí)間窗口集。時(shí)間窗口集是若干個(gè)不重疊的時(shí)間窗口[ ]t1,t2的并集，并給出如下定義：時(shí)間窗口集a與時(shí)間窗口集b相重合的時(shí)間段c，記作c=a∩b。

解碼方式如下：

（1）以集合Rn記錄各工件最后一道已完成工序的完工時(shí)間，Rm、Rl分別記錄各機(jī)器、工人的時(shí)間窗口集，從List中選擇加工優(yōu)先度最高的工序Oij。

（2）獲取可加工Oij的設(shè)備集合Mij，設(shè)其中有x1個(gè)機(jī)器；獲取可加工Oij的工人集合Lij，設(shè)其中有x2個(gè)工人，則對(duì)于兩者的選擇共有x1x2種組合。對(duì)于每種組合，可知工件在該組合的情況下所需的加工時(shí)長(zhǎng)t。從Rm中取對(duì)應(yīng)機(jī)器的時(shí)間窗口集Um，從Rl中取對(duì)應(yīng)工人的時(shí)間窗口集Ul，求得交集U=Um∩Ul，再?gòu)腞n里得到此工件的上道工序完成時(shí)間Ei(j-1)（若Oij是工件i的頭道工序，該值取0）。從U中按時(shí)間先后順序，找到其中第一個(gè)符合Ei(j-1)時(shí)刻且長(zhǎng)度不小于t的時(shí)間窗口。一旦找到這種時(shí)間窗口[t1,t2]，即可得知在此種機(jī)器、工人組合下，Oij的加工時(shí)間為[t1,t2+t]。同理，分別計(jì)算其他組合情況所對(duì)應(yīng)的加工時(shí)間。

（3）以最早完工的原則，取得該工序所有組合情況中的min(t2+t)，它對(duì)應(yīng)的機(jī)器與工人就是此工序最后確定使用的。

（4）更新Rn、Rm、Rl，從List中選擇下道工序，循環(huán)步驟（1）～（3），直至遍歷全部工序后，按式（9）～（11）計(jì)算f1至f3。

3 基于MOCOOT-SA算法的模型求解

3.1 標(biāo)準(zhǔn)單目標(biāo)COOT算法

COOT算法的原理為：用搜索空間中分布的散點(diǎn)模擬自然界中白骨頂鳥個(gè)體，將搜索過(guò)程模擬成白骨頂鳥在水面上集體運(yùn)動(dòng)的過(guò)程，把問(wèn)題的目標(biāo)函數(shù)模擬成白骨頂鳥所在位置的優(yōu)劣。

該算法主體思想如下：

（1）初始化種群，隨機(jī)選取其中NL個(gè)成為leader，剩余的NC個(gè)為coot，比例常取1∶10，把所有coot 平均分配給每個(gè)leader 形成一組，共NL組，并根據(jù)適應(yīng)值確定全局最優(yōu)。

（2）每個(gè)coot 有三種運(yùn)動(dòng)方式，按其中一種更新位置。

（3）每個(gè)coot 更新后的適應(yīng)值優(yōu)于所在組的leader時(shí)，交換兩者。

（4）每個(gè)leader 向全局最優(yōu)的鄰域移動(dòng)。

（5）每個(gè)leader 更新后的適應(yīng)值優(yōu)于全局最優(yōu)時(shí)，交換兩者。

（6）重復(fù)（2）至（5）直到滿足結(jié)束條件。

該算法主要仿生了如下的移動(dòng)方式：

（1）coot 根據(jù)所在組的leader 調(diào)整位置

式中：CootPos(i)為某個(gè)coot 的位置；LeaderPos(k)為該coot 服從的leader 位置；R和R1是隨機(jī)值。

（2）coot 跟隨前一個(gè)coot 鏈條移動(dòng)

（3）coot 隨意移動(dòng)

式中：A=1-L/Iter,L為當(dāng)前迭代次數(shù)，Iter為最大迭代次數(shù)；R2是隨機(jī)值；Q是全局隨機(jī)一點(diǎn)。

（4）leader 向全局最優(yōu)的鄰域移動(dòng)

式中：LeaderPos(i)為某個(gè)leader 的位置；gBest是全局最優(yōu)位置；B=2-L/Iter；R和R3是隨機(jī)值。

3.2 結(jié)合SA的多目標(biāo)COOT算法

3.2.1 存檔集的引入

在單目標(biāo)COOT算法中，易通過(guò)比較得到全局最優(yōu)值。然而在多目標(biāo)問(wèn)題中，除了一個(gè)解的各目標(biāo)值均劣于另一個(gè)解的情況外，不能嚴(yán)格地區(qū)分兩個(gè)解的優(yōu)劣。為此，在多目標(biāo)COOT 算法中，引入存檔集的概念，當(dāng)leader 要向全局最優(yōu)的鄰域移動(dòng)時(shí)，改為向存檔集中隨機(jī)一個(gè)鄰域移動(dòng)。設(shè)存檔集的大小為C，存檔集的建立步驟如下：

（1）將上一代的存檔集與當(dāng)代種群合并，篩選出目標(biāo)函數(shù)值不重復(fù)的個(gè)體（若為初代，則改為對(duì)初代種群執(zhí)行此操作）。對(duì)合并的種群進(jìn)行非支配比較，篩選出Pareto最優(yōu)解集。

（2）若Pareto 解集中解的個(gè)數(shù)不大于C，則該解集成為新的存檔集。

若個(gè)數(shù)大于C，則先令解集中所有個(gè)體的初始擁擠度I為0。再把這些解按每個(gè)優(yōu)化目標(biāo)函數(shù)值的大小排序。特別的，邊界上解的I為無(wú)窮大，然后按下面式子計(jì)算解集中其余每個(gè)解的擁擠度I：

式中：x是要優(yōu)化目標(biāo)的個(gè)數(shù)；分別為第i個(gè)解的前一個(gè)與后一個(gè)解的第d個(gè)目標(biāo)函數(shù)值；為第i個(gè)解在第d個(gè)目標(biāo)函數(shù)的最大值與最小值。I越大，說(shuō)明該解附近的解就越少，與其他解的相似程度越低，對(duì)種群的多樣性能作出更大的貢獻(xiàn)。

最后按擁擠度排序，依次從解集中刪除擁擠度最小的解，直至解集的個(gè)數(shù)為C，令此解集成為新的存檔集。

3.2.2 邊界變異

在COOT算法迭代尋優(yōu)的過(guò)程中，種群中個(gè)體的位置隨著變異操作，會(huì)有越出搜索域的可能，這樣的個(gè)體稱為無(wú)效個(gè)體。原COOT算法中的處理方法如下：若個(gè)體的某個(gè)維度在變異后超過(guò)了該維度所定義的上（下）限，則令該維度的值修正為上（下）限。這種做法會(huì)讓個(gè)體在搜索域的邊界上聚集，個(gè)體的隨機(jī)性變低，算法的局部搜索能力下降，為此采用如下式子處理個(gè)體在某個(gè)維度上的越界：

式中：ub和lb為搜索區(qū)域在維度d的上限和下限；m通常取0.01至0.1；xd為越界修正后在維度d的值。

3.2.3 自適應(yīng)選擇系數(shù)

COOT 算法中，已知當(dāng)前迭代次數(shù)為i，選擇概率p1、p2均為固定值0.5，coot 個(gè)體選擇的更新方式及其概率如圖2所示。

圖2 coot個(gè)體選擇的更新方式及概率Fig.2 Update method and probability of coot selection

基于群體的元啟發(fā)式算法的搜索權(quán)重往往是動(dòng)態(tài)變化的[13-14]，以利于算法跳出局部，尤其在算法運(yùn)行的后期很重要。因此，本文對(duì)p2進(jìn)行了自適應(yīng)調(diào)整修改。為此，定義了兩個(gè)參數(shù)：聚集度因子ω和進(jìn)化速率因子φ。

聚集度因子ω定義為：

式中：d為優(yōu)化目標(biāo)的個(gè)數(shù)；分別為第i次迭代中，存檔集的所有解與種群的所有解在某個(gè)優(yōu)化目標(biāo)上適應(yīng)度的均值；ω體現(xiàn)了當(dāng)前種群所有個(gè)體的聚集程度，0＜ω≤1。

進(jìn)化速率因子φ定義為：

式中：d為優(yōu)化目標(biāo)的個(gè)數(shù)；分別為第i次與第i-1 次迭代中，存檔集的所有解在某個(gè)優(yōu)化目標(biāo)上適應(yīng)度的均值；φ體現(xiàn)了種群的進(jìn)化速率，0＜φ≤1。

當(dāng)ω變大時(shí)，體現(xiàn)了種群的聚集程度變高，有進(jìn)入局部最優(yōu)的風(fēng)險(xiǎn)，此時(shí)要使p2增大，提升coot 個(gè)體移動(dòng)的隨機(jī)性，擴(kuò)大其搜索區(qū)域，以強(qiáng)化算法的全局搜索能力；當(dāng)φ變大時(shí)，體現(xiàn)了種群的進(jìn)化速度逐漸變小，此時(shí)需要減小p2，使得coot 個(gè)體在更小的區(qū)域內(nèi)搜索，進(jìn)而充分搜索局部找到最優(yōu)解。

結(jié)合上述討論，將固定值p2更改為自適應(yīng)選擇系數(shù),應(yīng)為ω與φ的函數(shù)，表示為：

式中：當(dāng)ω取0.10～0.25，φ取0.40～0.60 時(shí)，算法的性能較好。

3.2.4 改進(jìn)leader的更新方式

在COOT算法中，種群中兩類個(gè)體的更新方式有較大差異。coot 的更新方式有三種，且個(gè)數(shù)相較leader 眾多，有較強(qiáng)的全局搜索能力。

對(duì)比之下，leader 的更新方式有三個(gè)缺點(diǎn)：（1）只有式（15）一種更新方式，局部搜索能力一般，且更新后的位置如果劣于原leader，則不會(huì)被接受，進(jìn)一步降低了搜索能力，使得陷入局部最優(yōu)的可能性增大。（2）leader是通過(guò)向已知的全局最優(yōu)移動(dòng)，全局最優(yōu)再向真實(shí)的Pareto前沿移動(dòng)的方式來(lái)更新的，一定程度上降低了算法的收斂速度，如圖3 所示。（3）COOT 算法適用于解決連續(xù)的實(shí)數(shù)問(wèn)題，式（15）是在笛卡爾空間中對(duì)leader 的鄰域進(jìn)行搜索，解碼后映射到離散的調(diào)度方案時(shí)，不能保證解碼后是有意義的鄰域。因此，本文改進(jìn)了leader的更新方式。

圖3 leader更新示意圖Fig.3 Leader update diagram

首先，每個(gè)leader 更新時(shí)仍按式（15）搜索gBest 的鄰域生成一個(gè)臨時(shí)解tem,若tem 支配leader,則tem 替代對(duì)應(yīng)的leader，否則從存檔集中隨機(jī)選取一個(gè)取代該leader。這個(gè)操作雖然加快了收斂速度，且保證了新的leader 是已知解里面的最優(yōu)解之一，但增加了陷入局部最優(yōu)的風(fēng)險(xiǎn)。作為代償，引入了SA 對(duì)leader 進(jìn)行鄰域搜索，并對(duì)leader 的鄰域定義進(jìn)行調(diào)整。leader 鄰域的新定義是調(diào)換向量leader 上任意兩個(gè)位置上的值，對(duì)應(yīng)到工序序列的變換就是調(diào)整任意兩個(gè)工序的位置，如圖4所示。對(duì)新的工序序列進(jìn)行插入式貪婪解碼，就得到了新的調(diào)度方案。

圖4 個(gè)體leader的某個(gè)鄰域圖Fig.4 Neighborhood graph of leader

SA 算法具有局部搜索能力強(qiáng)的優(yōu)點(diǎn)[15]，在初始溫度足夠高、結(jié)束溫度足夠低、退火速率足夠慢的情況下，理論上能獲取全局最優(yōu)解，缺點(diǎn)是迭代次數(shù)過(guò)多導(dǎo)致的算法運(yùn)行時(shí)間長(zhǎng)，因此不能直接使用。

在使用SA 對(duì)leader 鄰域搜索時(shí)，也會(huì)出現(xiàn)兩個(gè)解互不支配的現(xiàn)象，進(jìn)而引發(fā)難以比較優(yōu)劣的問(wèn)題。常見(jiàn)的方法是賦予權(quán)重后進(jìn)行比較，或者在出現(xiàn)互不支配的情況時(shí)，隨機(jī)選取一個(gè)[16]。本文參考SUMAN[17]對(duì)SA算法提出的Pareto支配適應(yīng)度值的改進(jìn)接受準(zhǔn)則，按如下計(jì)算的概率接受新解：

式中：T為當(dāng)前退火溫度；Sold、Snew分別是舊解和新解的適應(yīng)度值，適應(yīng)度值等于檔案集中支配該解的個(gè)數(shù)。

在式（21）中，分子的大小與檔案集的規(guī)模有關(guān)，因此初始溫度不宜過(guò)高，取檔案集大小的1/2 左右既能避免陷入局部最優(yōu)，又能一定程度上縮減迭代次數(shù)，減少SA算法運(yùn)行時(shí)間過(guò)長(zhǎng)帶來(lái)的弊病。

3.2.5 算法流程

結(jié)合上述改進(jìn)，構(gòu)建MOCOOT-SA算法。其中的參數(shù)設(shè)置：種群規(guī)模N（其中l(wèi)eader 類個(gè)體有NL個(gè)，coot類個(gè)體有NC個(gè)），初始選擇系數(shù)p1、，最大迭代次數(shù)Iter,檔案集最大容量Nr，模擬退火初溫Ts，終溫Te，降溫系數(shù)δ，馬爾可夫鏈長(zhǎng)度lm。MOCOOT-SA 算法的流程圖如圖5所示。

圖5 MOCOOT-SA算法流程圖Fig.5 MOCOOT-SA algorithm flow chart

4 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證MOCOOT-SA算法的有效性與可行性，本文在MK01基準(zhǔn)算例（10工件6機(jī)器）的基礎(chǔ)上，結(jié)合實(shí)際，給出了機(jī)器與工人的信息，數(shù)據(jù)如表1～表2 所示。表1 是5 個(gè)工人與6 個(gè)機(jī)器的關(guān)系，符號(hào)○代表當(dāng)前工人能操作該機(jī)器。表2 是6 個(gè)機(jī)器的耗電情況，機(jī)器在負(fù)載與空載的情況下耗能不同。

表1 各工人能加工的機(jī)器信息Table 1 Machine information that each worker can process

表2 機(jī)器的耗能信息Table 2 Machine energy consumption information

對(duì)MOCOOT-SA 算法運(yùn)行上述例子，參數(shù)設(shè)置如下：種群規(guī)模N=100（其中l(wèi)eader 類個(gè)體有10個(gè)，coot類個(gè)體有90 個(gè)），選擇系數(shù)p1=0.5，自適應(yīng)選擇系數(shù)0.5+0.1h-0.4g，檔案集最大容量Nr=30，最大迭代次數(shù)Iter=150，模擬退火初溫Ts=15，終溫Te=0.3，降溫系數(shù)δ=0.85，馬爾可夫鏈長(zhǎng)度lm=100。

多目標(biāo)粒子群算法（MOPSO）、NSGA-Ⅱ算法分別是在成熟的粒子群算法和遺傳算法上進(jìn)一步改進(jìn)得到的，兩者突出的尋優(yōu)能力使它們常被應(yīng)用到調(diào)度問(wèn)題中[8，14]。為了比較新算法的性能公平起見(jiàn)，盡量使得三種算法的種群個(gè)數(shù)和迭代次數(shù)等保持一致。MOPSO的有關(guān)參數(shù)如下：最大迭代次數(shù)為200，種群規(guī)模為100，檔案庫(kù)大小為50，初始慣性權(quán)重系數(shù)為0.9，慣性權(quán)重衰減為0.99，個(gè)體學(xué)習(xí)因子為1.7，全局學(xué)習(xí)因子為1.8；NSGA-Ⅱ的有關(guān)參數(shù)如下：最大迭代次數(shù)為200，種群規(guī)模為100，交叉概率為0.9，變異概率為0.03。實(shí)驗(yàn)結(jié)果如表3所示。

表3 三種算法結(jié)果Table 3 Three algorithm results

由表3的信息得知，通過(guò)MOCOOT-SA得到的Pareto解總體上不劣于其他兩個(gè)算法：與NSGA-Ⅱ比較Pareto解的均值，最大完工時(shí)間優(yōu)化了3.5 個(gè)單位，優(yōu)化比為0.065，機(jī)器總負(fù)荷優(yōu)化了3.2個(gè)單位，優(yōu)化比為0.020，總耗能優(yōu)化了6.4個(gè)單位，優(yōu)化比為0.016；與MOPSO比較Pareto解的均值，最大完工時(shí)間優(yōu)化了2.3個(gè)單位，優(yōu)化比為0.044，機(jī)器總負(fù)荷優(yōu)化了5.4個(gè)單位，優(yōu)化比為0.033，總耗能優(yōu)化了22.3個(gè)單位，優(yōu)化比為0.057。同理，比較MOCOOT-SA與NSGA-Ⅱ算法在各目標(biāo)上的最優(yōu)值，均有提升，優(yōu)化比為0.023、0.025、0.021；比較MOCOOT-SA與NSGA-Ⅱ算法在各目標(biāo)上的最優(yōu)值，優(yōu)化比為0.045、0.019、0.016。同時(shí)，在同等種群規(guī)模的前提下，通過(guò)MOCOOT-SA 得到的Pareto 解的數(shù)量要比另外兩個(gè)算法多，能給予工廠更豐富的選擇，可見(jiàn)MOCOOT-SA 算法有解決FJSP問(wèn)題的能力。

用MOCOOT-SA 算法仿真后得到的存檔集的解共有23組，如表4所示。決策者可根據(jù)表4中的解和各自的偏好，選取一個(gè)作為最終的調(diào)度方案。

表4 最后一代時(shí)存檔集的解Table 4 Solution for archive set in last generation

MOCOOT-SA算法求解該問(wèn)題迭代至最后一代時(shí)，種群的解與存檔集的解的分布如圖6所示，證明了使用SA對(duì)leader 進(jìn)行鄰域搜索的有效性。

圖6 種群與存檔集的個(gè)體分布圖Fig.6 Individual distribution graph of populations and archive sets

存檔集中各目標(biāo)適應(yīng)值的迭代過(guò)程如圖7所示，體現(xiàn)了存檔集中所有解的最值與均值隨迭代次數(shù)變化的情況。

圖7 存檔集的解的變化圖Fig.7 Variation graph of solution for archive set

圖8 是表4 中第一個(gè)解的調(diào)度方案。以M6 的第一個(gè)工序上注明的10/1 5為例，表示工件10的第1道工序由工人5在第6個(gè)機(jī)器加工。按這種方式可依次獲得所有工序的加工安排。

圖8 調(diào)度甘特圖Fig.8 Scheduling Gantt chart

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

本文考慮了機(jī)器與工人的約束，以最小化最大完工時(shí)間、機(jī)器總負(fù)荷、能耗三個(gè)優(yōu)化目標(biāo)，對(duì)多目標(biāo)柔性調(diào)度車間問(wèn)題建立了數(shù)學(xué)模型，并使用了簡(jiǎn)潔的編碼方式，在解碼過(guò)程中采用了時(shí)間窗口的概念，使得離散問(wèn)題能在連續(xù)性算法上適用。同時(shí)，對(duì)單目標(biāo)COOT算法進(jìn)行了多方面的改進(jìn)，以適應(yīng)求解多目標(biāo)問(wèn)題和FJSP問(wèn)題，得到了性能更好的MOCOOT-SA 算法。最后，通過(guò)算例測(cè)試，對(duì)MOCOOT-SA與NSGA-Ⅱ算法、MOPSO算法的方案進(jìn)行比較，其各目標(biāo)上的平均值的優(yōu)化比為0.013～0.047，各目標(biāo)上的最優(yōu)值的優(yōu)化比為0.016～0.045，證明了新算法的有效性。

在下階段的研究進(jìn)程中，可以考慮更多的約束條件，例如工裝與刀具，并探索MOCOOT-SA 解決擾動(dòng)環(huán)境下車間調(diào)度問(wèn)題的能力。