吳定會，孔飛，朱紹文，紀志成

江南大學輕工過程先進控制教育部重點實驗室，江蘇無錫214122

生物地理學算法求解柔性車間作業(yè)調(diào)度問題

吳定會，孔飛，朱紹文，紀志成

江南大學輕工過程先進控制教育部重點實驗室，江蘇無錫214122

針對加工設備和操作工人雙資源約束的柔性作業(yè)車間調(diào)度問題，建立以生產(chǎn)時間和生產(chǎn)成本為目標函數(shù)的柔性作業(yè)車間調(diào)度模型，提出基于模糊Pareto支配的生物地理學算法，采用模糊Pareto支配的方法計算解之間的支配關系并對Pareto解集排序，進行全局最優(yōu)值的更新，并采用余弦遷移模型來改善生物地理學算法的收斂速度。將該方法應用于某模具車間的柔性作業(yè)車間調(diào)度中，仿真結果驗證了該方法的可行性和有效性。

柔性作業(yè)車間調(diào)度；模糊Pareto支配；生物地理學算法；余弦遷移模型；雙資源約束

1　引言

車間作業(yè)調(diào)度是影響車間生產(chǎn)效率的關鍵因素，它采用有效的調(diào)度優(yōu)化技術，在一定的約束條件下，合理地分配現(xiàn)有的人力和物力資源，完成給定的任務，滿足生產(chǎn)過程中經(jīng)濟上或性能上的目標［1］。其中柔性作業(yè)車間調(diào)度問題（Flexible Job Shop Scheduling Problem，F(xiàn)JSP）突破了傳統(tǒng)作業(yè)調(diào)度資源唯一性的限制，更符合生產(chǎn)實際，因此研究FJSP具有重要的理論意義和實際價值。

在實際生產(chǎn)中，車間調(diào)度問題通常是同時對多個目標進行優(yōu)化。目前求解柔性作業(yè)車間多目標調(diào)度方法可分為兩類：（1）單目標優(yōu)化法。通過賦予每個目標不同的權重系數(shù)將多目標問題轉(zhuǎn)換為單目標問題。文獻［2］提出基于蟻群與鄰域搜索算法的混合算法，以生產(chǎn)周期、設備總負荷和關鍵設備負荷為目標，對柔性作業(yè)調(diào)度問題進行了研究。文獻［3］提出多智能體免疫算法，以生產(chǎn)周期和客戶滿意度為目標，對存在批量可變性、機器并行性、加工時間和交貨期模糊性的生產(chǎn)問題進行了研究。這類方法的缺點在于過分依賴權重參數(shù)，難以收斂到Pareto最優(yōu)沿面的非凸區(qū)域。（2）Pareto優(yōu)化策略。采用Pareto最優(yōu)的概念評價解的優(yōu)劣，將優(yōu)化目標轉(zhuǎn)化為尋找一組符合評價標準的Pareto解。文獻［4］提出了一種基于Pareto支配的混合粒子群優(yōu)化算法，引入了基于Baldwinian學習策略和模擬退火技術相結合的多目標局部搜索策略，增強了算法的探索性，達到最小化完工時間、設備總負荷和單臺設備總負荷最小化的目標。文獻［5］提出改進的非支配排序遺傳算法，在考慮設備、操作人員資源約束下，求以加工成本、客戶滿意度及生產(chǎn)總流程時間為目標的柔性車間模糊調(diào)度。文獻［6］結合免疫遺傳算法和約束理論提出了一種基于瓶頸工序的多資源多目標車間調(diào)度算法，克服了多目標遺傳算法早熟及Pareto解集多樣性不足等缺陷。

目前，柔性作業(yè)車間調(diào)度問題求解主要集中在運用遺傳算法［7-8］、粒子群算法［9-10］和蟻群算法［11-12］等，通過迭代實現(xiàn)柔性作業(yè)車間調(diào)度方案優(yōu)化。Dan Simon在2008年提出一種新的啟發(fā)式算法-生物地理學BBO（Biogeography-Based Optimization）算法［13］，它通過模擬自然界不同棲息地種群數(shù)量的變化過程尋找優(yōu)化問題的最優(yōu)解。與蟻群優(yōu)化算法、遺傳算法和粒子群算法優(yōu)化相比，生物地理分布優(yōu)化算法的主要優(yōu)點是參數(shù)少、實現(xiàn)簡單、收斂速度快、搜索精度高，可以有效地解決全局優(yōu)化問題。目前，BBO算法已經(jīng)用于解決衛(wèi)星圖像分類問題［14］、離散優(yōu)化問題［15］、電力系統(tǒng)多目標發(fā)電調(diào)度問題［16］等。Rahmati等提出將生物地理學的優(yōu)化方法應用于柔性車間調(diào)度［17］，并與GA、EGA、KEGA優(yōu)化算法進行對比，結果表明BBO算法具有更好的穩(wěn)定性及收斂性，但是僅考慮設備單一資源約束的作業(yè)調(diào)度問題。

本文針對設備和工人雙資源約束的柔性車間作業(yè)調(diào)度問題，提出了基于Pareto支配的生物地理學調(diào)度算法（ParetoDominance-CombinedBiogeography-Based Optimization Scheduling Algorithm，F(xiàn)PDCBBO），使用模糊Pareto支配的方法計算解之間的支配關系并對解集排序，促進Pareto最優(yōu)前沿向理想Pareto前沿逼近，然后采用余弦遷移模型改善算法的收斂速度，最后運用該算法解決某模具公司的柔性作業(yè)調(diào)度問題。

2　柔性作業(yè)車間調(diào)度模型

2.1問題描述

本文用產(chǎn)品零件集N，工序集J，工序加工時間集T，設備集M、工人集P、工序與設備關系集J_M、設備與工人關系集M_P和調(diào)度目標F來描述離散制造車間作業(yè)調(diào)度數(shù)學模型。

（2）工序集O，每個零件有若干個具有先后約束的工序，工序集包括工序序列集O和工序?qū)傩约疧G。，其中O為調(diào)度任務的總工序數(shù)，Oi表示零件i總工序數(shù)，Oij表示第i零件的第j道工序。定義工序Oij的工序?qū)傩詤?shù)組集，第j個加工屬性參數(shù)組，G1為工序需要配備的設備，G2為所需的操作人員。

（3）資源集包括設備集M和操作人員集P。具體如下：M=｛mi|1≤i≤M｝，其中M為車間可用的設備總數(shù)，其負載量和狀態(tài)用Ci和Si描述。狀態(tài)Si=0和1分別表示設備處于空閑和忙碌狀態(tài)。P=｛Pi|1≤i≤P｝，P為車間內(nèi)操作人員總數(shù)，Pi為第i操作人員的工號，工作時間為Ti，狀態(tài)Si=0和1時分別表示操作人員處于空閑和忙碌狀態(tài)。

（4）工序與設備的關系集O_M，O_M=｛OMijk|1≤i≤N，1≤j≤Oi，1≤k≤M｝，其中OMijk=0或1，分別表示工序Oij是否可以在設備Mk上加工。設備與操作人員的關系集M_P。M_P=｛MPij|1≤i≤M，1≤j≤P｝，其中MPij=0或1，分別表示操作人員Pi是否可以操作設備Mj。

（5）工序加工時間集，即工序在不同設備上的加工時間，T=｛Tijm|1≤i≤N，1≤j≤Oi，1≤m≤M｝，其中Tijm表示零件i的第j道工序在設備m上的加工所需時間。

2.2數(shù)學模型

本文在滿足工藝約束前提下，給出了以下目標：完工時間F1最小化；總生產(chǎn)成本F2最小化。其中F2包括設備加工成本和工人成本。車間作業(yè)調(diào)度的數(shù)學模型如下。

首先定義如下的參數(shù)和變量：Ci為零件i的完工時間，Cij為零件i的j道工序的完工時間，Cijm為零件i的第j道工序在設備m上的完工時間，Sij為零件i的工序j可以開始加工的時間，Tij為零件i的工序j加工時間，Tijm為零件i的第j道工序在設備m上的加工時間，Em為設備m的單位加工時間動力燃料費用，Zm為設備m的折舊費用，Sp為工人p單位時間的人員成本，Xijmp為零件i的第j道工序在設備m上加工，并且設備m由工人p操作時為1，否則為0，F(xiàn)ihkp為零件i的第h道工序在設備k由工人p加工的完成時間，Tijmp為零件i的第j道工序在設備m由工人p加工的時間，Sihkp為零件i的第h道工序在設備k由工人p加工的開始時間，Rijabm為設備m上加工工序j和b的判別條件，i和b都在設備m上加工時，如果零件i的第j道工序先于零件a的第b道工序，則Rijabm=1，否則Rijabm=0。

目標函數(shù)：

約束條件：

式（3）保證了一個零件只能在加工完成前一道工序后才可以加工后一道工序；式（4）保證了設備m不能同時加工兩個不同的工序；式（5）保證一個工人不能同時操作兩臺設備；式（6）保證任何一道工序的完工時間不能小于其加工時間。

3　多目標預備知識

3.1模糊Pareto支配

He Z等人提出的模糊Pareto進化方法［18］求解Pareto解之間的支配關系，更接近支配的原始概念，在處理多目標優(yōu)化問題時具有較好的實用性。首先給出3個定義。

定義1（模糊集）對于研究范圍X中的任一元素x，都有一個數(shù)A（x）∈［0，1］與之對應，則稱A是X上的模糊集，A（x）稱為x對模糊集A的隸屬度。隸屬度A（x）接近1，表示x屬于A的程度越高，反之，越接近0，x屬于A的程度越低。當x在X中變動時，A（x）就是一個函數(shù)，稱為A的隸屬函數(shù)。FG（x）的計算公式如式（7）所示：

其變化范圍是0到1，c=-1，σ=0.5，x的計算公式如式（8）所示：

xu和xv為目標函數(shù)f上的兩個解向量。對于最小化問題，如果f（xu）＜f（xv），則x≈-1，F(xiàn)G（x）≈1對應于Pareto支配關系，可以說明xu支配xv。反之，f（xu）＞f（xv），則x≈1，F(xiàn)G（x）≈0對應于Pareto支配關系，可以說明xu被xv支配。

定義2（模糊Pareto支配）對于Nobj個最小化問題，給定兩個解向量xu和xv，存在u=f（xu）=（u1，u2，…，uM）和v=f（xv）=（v1，v2，…，vM），定義p（u）=u-v，p（v）=v-u，利用高斯型隸屬度函數(shù)使FG（p（u））→［0，1］和FG（p（v））→［0，1］，即和φ（v）=FG（p（v））=。則向量u的模糊值為，向量v的模糊值為若，則稱x模糊支配x即xx。uvuv

定義3（模糊適宜度值）存在n個解向量，利用高斯型隸屬度函數(shù)分別計算出每個解向量與其他n-1個解向量的模糊值，然后通過公式（9）分別計算兩個解向量之間的模糊支配度，將n-1個模糊支配度相加后除以n-1得到的值，作為每個解向量的模糊適宜度值FFM。

3.2解的擁擠距離

在解空間上，某個體周圍個體的分布密度越小，擁擠距離越大，表示個體的分布密度越大，這些個體會以更大的概率進入到下一次優(yōu)化迭代中，有利于維持解集的多樣性。本文用每個目標函數(shù)上與其相鄰的兩個解距離差之和來計算個體xv的擁擠距離I（xv）：

其中xv-1和xv+1為將解集按照第i個目標函數(shù)值升序排列后與xv相鄰的兩個解，對應排序在邊緣上的個體x1和xk，賦予一個極大值，m表示目標函數(shù)的個數(shù)，fi表示第i個子目標。每一個體的擁擠度距離計算時間復雜度為O（mn），其中n為種群的規(guī)模。采用公式（10）的擁擠度距離計算公式，計算時間復雜度明顯降低，使得到的解均勻分布在Pareto前言，增加了解集的多樣性。

3.3非支配排序

對于待優(yōu)化問題中的解，為了保持非支配解分布的均勻性和解的多樣性，采用綜合模糊適宜值FFM和擁擠距離的策略進行排序，具體步驟如下：

（1）對于每個棲息地，根據(jù)目標函數(shù)F1和F2，計算其對應的模糊適宜值FFM，F(xiàn)FM大的棲息地排在前面。

（2）如果FFM相同，則擁擠距離大的棲息地排在前面。

4　生物地理學算法

生物地理學優(yōu)化算法（BBO）的基本思想是通過群體中相鄰個體的遷移和特別個體的突變來尋找全局最優(yōu)解。在BBO中，每個個體被認為是一個棲息地（habitat），如果某個棲息地非常適合生物居住，則該棲息地具有較高的適宜度指數(shù)（habitat suitability index，HSI），與HSI相關的影響因子被定義為適宜度指數(shù)變量（suitability index variables，SIV）。在車間作業(yè)調(diào)度問題中，選用待調(diào)度的設備、工人和未加工的任務作為決策變量，每個決策變量為各棲息地的SIV，由決策變量得到的目標函數(shù)為適宜度指數(shù)HSI。

4.1棲息地編碼

根據(jù)離散制造車間作業(yè)調(diào)度的特點，將決策變量（待調(diào)度的設備、工人和未加工的任務）表示成適合BBO求解的碼串形式。在實際作業(yè)調(diào)度中，不僅要確定工序的加工順序，還需為每道工序選擇一臺合適的設備，并且為每個設備選擇合適的工人，因此，其相應的編碼由三部分組成。本文采用的編碼方式如式（11）所示。

第一層編碼J表示工序的編碼，用相同的符號表示同一個零件的所有工序，根據(jù)這些符號在數(shù)組J中出現(xiàn)的次數(shù)確定是第幾道工序。第二層編碼M是該零件相應工序所使用的設備分配編碼，可在該工序的可用設備集中選擇。第三層編碼P是可以操作該設備的工人編碼，可在操作該設備的工人集中選擇。這種編碼方式的優(yōu)點是可以滿足工藝路線柔性化、設備和人員選擇柔性化。將三層編碼對應起來，可得到車間作業(yè)調(diào)度的一個可行解。表1表示一個編碼示例，表中零件2的第一道工序在可用設備3上加工，由工人1操作該設備。該編碼方式能夠滿足加工路線柔性化和加工資源不唯一的約束條件。

表1　CHPSO棲息地編碼圖

4.2棲息地初始化

在BBO算法中，設存在n個棲息地，每個棲息地表示車間調(diào)度的一個可行的調(diào)度方案。具體的初始化步驟是：

（1）令循環(huán)次數(shù)k=1。

（2）將第H（k）個棲息地編碼的第一行置0。

（3）根據(jù)各零件i的工序數(shù)Ji，在棲息編碼的第一行隨機尋找Ji個未被占用的空位（0位），將i賦給選中的空位。

（4）從左到右，根據(jù)各零件i和工序號j，從可選的設備集Mij中隨機選擇一個設備，從可選的工人集P中隨機選擇一個工人，分別賦給H（k）的第二行和第三行（即設備編碼和工人編碼）。

（5）令k=k+1。

（6）若k≤n，轉(zhuǎn)向（2），否則，退出循環(huán)。

4.3棲息地解碼

解碼過程就是根據(jù)棲息地的編碼信息，確定每道工序在設備上的加工順序及開始/結束時間，確定操作加工設備的工人，從而產(chǎn)生相應的調(diào)度方案。具體步驟是：

（1）根據(jù)棲息地中零件編號的相對位置，確定每個位置對應的工序編號，用Oij表示零件i的第j道工序，設備和工人狀態(tài)均為空閑（即為0）。

（2）從左到右依次讀取Oij，計算Oij的最早開始時間Sij。首先判斷Oij是否為零件i的第一道工序，如果是第一道工序，Sij=Ti（Ti為零件釋放時間），如果不是第一道工序，則是前一道工序的完工時間Sij=Ci（j-1）（Ci（j-1）為工序Oi（j-1）的完工時間）。

（3）獲取加工Oij的設備m當前所有的空閑時間段（即設備狀態(tài)為0的時間段），并將最早的空閑時段記為［Rm，Qm］。

（4）獲取操作m的工人p當前所有的空閑時間段（即工人p狀態(tài)為0的時間段），并將最早的空閑時段記為［Rp，Qp］。

（5）比較max（Sij，Rm，Rp）+Tijm與Qm和Qp，Tijm表示Oij在設備m上的加工時間，如果max（Sij，Rm，Rp）+ Tijm≤min（Qm，Qp），將Oij插入到設備和工人空閑時間段［max（Sij，Rm，Rp），max（Sij，Rm，Rp）+Tijm］中，并更新零件的結束時間、設備的開始時間和結束時間，工人的開始時間和結束時間。并將設備對應的工人狀態(tài)置為1，工序oij加工完成后，將設備和工人的狀態(tài)置為0，否則，轉(zhuǎn)向（6）。

（6）令［Rm，Qm］和［Rp，Qp］為下一個可加工Oij的設備的時間段和工人的時間段，轉(zhuǎn)向（5）。如果沒有符合的空間時間段，則在該設備和工人加工序列的末尾安排Oij。

（7）當所有零件的全部工序安排到指定的設備和操作工人后，獲得每個零件的完工時間，設備加工時間、讀取單位時間內(nèi)設備費用和可以操作設備的工人的單位工資成本，根據(jù)公式（1）和（2）分別計算總生產(chǎn)時間F1和加工成本F2。

4.4適應度函數(shù)計算

本文中適應度函數(shù)計算過程如下：

（1）將每個棲息地按照約束條件對其進行解碼，根據(jù)公式（1）和公式（2）計算調(diào)度分目標函數(shù)值F1和F2。

（2）對于每個棲息地，根據(jù)計算的F1和F2，計算其對應的模糊適宜值FFM。

本文算法中模糊適宜值FFM計算的偽代碼如圖1所示。

4.5遷移

BBO算法通過遷移算子使各解之間進行信息共享，從而對求解空間進行廣域搜索，進而更新棲息地得到更大更豐富的解集合。每個個體具有各自的遷入率λ和遷出率μ，文獻［19］分析了6種線性和非線性物種遷移模型，本文選用符合自然規(guī)律的余弦遷移模型，從圖2可以看出，當棲息地中有較少或較多物種時，λ和μ的變化比較平穩(wěn)，而當棲息地種群數(shù)量達到平衡點時，λ和μ的變化比較快。余弦遷移模型計算如下：

I表示最大遷入率，E表示最大遷出率，可將每個棲息地的HSI轉(zhuǎn)換成物種數(shù)量來衡量其優(yōu)劣。首先將棲息地按照其對應的HIS從大到小進行排序，并且設Smax=n，則Sr=Smax-r，r=1，2，…，n，r表示排序后的標號。將Si帶入到公式（12）中，計算出棲息地Hr的遷入率λr和遷出率μr。

圖1　模糊適宜值計算偽代碼

圖2　余弦遷移模型

遷移操作的具體過程是：根據(jù)遷入率λr確定棲息地Hr是否發(fā)生遷移操作（棲息地的數(shù)量h作為循環(huán)次數(shù)）。隨機產(chǎn)生（0，1）之間的隨機數(shù)，如果小于λr，則Hr被確定發(fā)生遷入操作，那么利用其他棲息地的遷出率μ進行輪盤選擇需遷出的棲息地Hq，然后按照遷移策略修改棲息地Hr。

當確定遷入棲息地Hi和遷出棲息地Hj以后，為保證棲息地可行性，結合棲息地的編碼方案，本文采用的遷移策略的實現(xiàn)方式是：

（1）先將零件集｛n1，n2，…，nN｝隨機劃分為兩個非空的集合G1和G2。

（2）將遷入棲息地Hi工序編碼中屬于G1的零件復制到臨時棲息地Hk工序編碼中，并保持它們的前后順序和位置，同時將對應的設備和工人保持位置不動，復制到Hk設備編碼和工人編碼中。

（3）將遷出棲息地Hj中工序編碼中包含G2的零件依次填到Hk中工序編碼的空余位置，同時將對應的設備和工人保持位置不動，填到Hk設備編碼和工人編碼空余的位置。

遷移操作完成后，用Hk替換Hi。以3個零件，并且每個零件有4道加工工序為列，G1中包括零件1，G2中包含零件2和3，如圖3所示。

圖3　遷移操作

4.6變異

其中，mmax為預定義的最大突變率，Pmax=max（Ps），s∈（1，2，…，n）。

在車間調(diào)度問題中，對于選擇發(fā)生變異的棲息地（即調(diào)度方案），為保證變異后的個體是可行解，則按照以下策略進行變異。

（1）基于工序的變異：從種群中隨機選取一個棲息地，在對應的棲息地第一行隨機選取兩個變異點，交換選取的兩個變異點的位置，為保證變異的可行性，保存變異前的機床號和工人號。例如隨機選取的棲息地如圖4所示。

對其第一行的第二位和第六位交換位置，并保存對應的機器號和工序號，得到變異后棲息地如圖5所示。

BBO算法的變異策略對算法是否會陷入局部最優(yōu)和收斂精度均有較大影響。BBO變異操作是通過棲息地容納物種數(shù)量的概率來對棲息地的特征變量進行突變，設棲息地恰好包含物種數(shù)S的概率為Ps，變異率為：

圖4　變異前棲息地

圖5　變異后棲息地

（2）基于設備的變異：在基于設備的編碼部分，隨機選擇兩個位置上的設備編號，然后在其對應位置上的工序可用設備集合中獲取加工時間最小的設備，如果與現(xiàn)使用的設備不同，則使用被選中的設備加工這道工序，否則，采用原來的加工設備。例如對于圖5中的棲息地，假設工序o21可以在機器1、2和4上加工，采用機器2加工時間最小，則將棲息地的第二行第一位變?yōu)?，變異后的棲息地如圖6所示。

（3）基于工人的變異：在基于工人的編碼部分，隨機選擇某個位置上的工人編號，然后從設備可用的工人集中隨機獲取工人號，如果與其現(xiàn)在的操作工人不同，則替換原來的操作工人操作其對應的設備。例如對于圖5中的棲息地，工序o31在機器3加工，假設機器3可由工人1、2和3操作，則隨機從工人集中選取工人號代替當前工人3，變異后的棲息地如圖7所示。

圖6　基于設備的變異

圖7　基于工人的變異

4.7FPDCBBO算法

基于模糊Pareto支配的生物地理學算法（Fuzzy Pareto Dominance-CombinedBiogeography-BasedOptimization Scheduling Algorithm，F(xiàn)PDCBBO）基本思想是：在生物地理學算法（BBO）的基礎上，用模糊適宜值和擁擠距離對解進行排序，代替基本的BBO算法中棲息地適宜度指數(shù)（HIV）作為解的評價標準。在算法迭代過程中，不用遷移和變異后的個體代替原有的個體，而是將產(chǎn)生的進化解集合與排序后的原解集融合，重新排序，選擇排序靠前的解作為下一代解集，保證解集的多樣性。

在離散制造車間作業(yè)調(diào)度問題中，待調(diào)度的設備、工人和未加工的任務作為棲息地中的決策變量，每個棲息地對應一個可行的調(diào)度方案，將FPDCBBO應用與車間作業(yè)調(diào)度的具體實現(xiàn)步驟為：

步驟1輸入計算所需的原始數(shù)據(jù)，包括車間作業(yè)調(diào)度模型中的零件數(shù)量，每個零件對應的工序、設備參數(shù)、工人參數(shù)、約束參數(shù)等。設置BBO算法參數(shù)，設定棲息地數(shù)量n，棲息地最大物種數(shù)量Smax=L，遷入率函數(shù)最大值I，遷出率最大值E，全局遷移率Pmod。

步驟2初始化棲息地的SIV，這里的SIV指的是車間作業(yè)調(diào)度系統(tǒng)中的設備、工人和待加工的任務。對SIV進行編碼，產(chǎn)生規(guī)模為n的初始棲息地SIV。

步驟3按照約束條件對棲息地進行解碼，根據(jù)目標函數(shù)F1和F2計算調(diào)度分目標函數(shù)值。

步驟4非支配排序，對于每個棲息地，根據(jù)步驟3中的F1和F2，計算其對應的模糊適宜值FFM，F(xiàn)FM大的棲息地排在前面。如果FFM相同，則擁擠距離大的棲息地排在前面。則產(chǎn)生排序后的群棲息地n1。

步驟5將排序后的棲息序號映射為物種數(shù)量，來衡量棲息地所對應的車間解決方案的優(yōu)劣。設棲息地最大物種數(shù)量Smax=L，則Sr=Smax-r，r=1，2，…，n，r表示排序后的標號。根據(jù)每個棲息地的物種數(shù)量，利用公式（12）計算其對應的遷入率和遷出率。

步驟6根據(jù)步驟5計算出的遷入率、遷出率和變異概率，對棲息地中的工序編碼、設備編碼和工人編碼進行遷移和變異操作，產(chǎn)生進化群棲息地n2。

步驟7融合群棲息地n1和n2，形成數(shù)量為2n的群棲地w。

步驟8計算w中棲息地個體對應的分目標函數(shù)值，然后按照步驟4進行非支配排序。

步驟9選擇前n個棲息地構成新一代群棲息地n3。

步驟10判斷是否達到最大迭代次數(shù)，如果是，則結束運算，輸出結果，否則迭代次數(shù)加1，轉(zhuǎn)向步驟3。

對于步驟4中模糊Pareto實現(xiàn)的偽代碼如圖8所示。

圖8　模糊Pareto實現(xiàn)偽代碼

表2　不同規(guī)模測試問題結果比較

5　實例仿真

5.1基準測試仿真

為驗證本文算法的有效性，以完工時間、所有機器總負荷、最大機器負荷為目標，使用文獻［20］中8×8和10×10的柔性作業(yè)車間實例問題進行測試，并同已有的PSO+SA［21］，IGA［22］算法進行對比和分析，結果如表2所示，Cmax表示加工時間，TWL表示所有機器總負荷，CWL表示最大機器負荷。從表中可知，對于三個性能指標，本文算法在這些問題上的求解平均值優(yōu)于其他算法得到的結果。

5.2實例仿真

以某離散模具車間為例，該車間擁有數(shù)控車床、普通車床、搖臂鉆床、萬向搖臂鉆床、電火花、銑床6臺多功能設備（M1～M6），每個設備可以加工不同的工序。在一個生產(chǎn)周期內(nèi)，需要為一套注塑模具加工不同的6種模具零件（N1～N6），每個零件有4道加工工序（O1～O4），有4個工人（P1～P4）操作這6臺設備。具體描述信息如表3，表4，表5，表6。

表3　制造單元信息

表4　設備費用（元·h-1）

表5　工人費用（元·h-1）

表6　工人與設備的關系

以本文所建立作業(yè)調(diào)度數(shù)學模型中的加工周期最小和生產(chǎn)成本最小目標為優(yōu)化目標，將本文提出的算法應用于上述實例，設置算法參數(shù)：棲息地數(shù)量n=100，最大變異率mmax=0.05，最大遷入概率和最大遷出概率I=E=1.0，迭代次數(shù)為150，獨立運行20次，得到完工時間最小為121時，面向設備的調(diào)度甘特圖如圖9所示，面向工人的調(diào)度甘特圖如圖10所示，時間-成本關系如圖11所示。

圖9　面向設備的調(diào)度甘特圖

圖10　面向工人的調(diào)度甘特圖

圖11　FPDCBBO生產(chǎn)時間-成本關系圖

在圖9中，方塊中的第一個數(shù)為零件號，第二個數(shù)為零件對應工序號，第三個數(shù)為操作該設備的工人號。如第一行中的‘311’表示第3個零件的第1道工序在設備1上加工，由工人1操作。在圖10中，方塊中的第一個數(shù)為零件號，第二個數(shù)為零件對應工序號，第三個數(shù)為該工人操作的設備號。如第二行中的‘513’表示第5個零件的第1道工序在設備3上加工，在由工人2操作。從甘特圖的結果可以看出，設備和工人雙資源的利用率比較均衡，加工零件可按時完成。

為了驗證本文提出的調(diào)度算法在求解人機雙資源約束的作業(yè)調(diào)度上的優(yōu)越性，與NSGA-II算法進行對比分析，算法的種群規(guī)模和最大迭代次數(shù)與FPDCBOO算法相同，得到的時間-成本關系如圖12所示。

圖12　NSGA-II生產(chǎn)時間-成本關系圖

由圖12可以看出，NSGA-II算法輸出的生產(chǎn)時間-成本關系圖中解集分布在生產(chǎn)總流程時間區(qū)間（130，190）與成本區(qū)間（15 500，15 850）的交集中，由圖11可以看出，本文FPDCBBO算法輸出的生產(chǎn)時間-成本關系圖中，解集分布在生產(chǎn)總流程時間區(qū)間（120，155）與成本區(qū)間（15 300，15 650）的交集中，即本文算法縮短了生產(chǎn)總流程時間。此外，相比NSGA-II算法，本文算法產(chǎn)生的Pareto均勻性較好。表7中對于完工時間最小化和總加工成本最小化目標，本文算法得到的最優(yōu)值及平均值均優(yōu)于NSGA-II算法，更適合求解多目標柔性車間調(diào)度問題。

表7　算法結果的對比

6　結束語

本文基于制造車間的生產(chǎn)特點建立了以設備和工人雙資源約束的，以最小化加工時間和最小化加工成本為目標的車間調(diào)度模型，提出了一種采用基于模糊Pareto支配的生物地理學算法，在BBO算法中，決策變量采用三層編碼方法，既解決了工序調(diào)度問題，又解決了設備和人員分配的問題，采用余弦遷移模型提高生物地理學算法的收斂速度。采用綜合模糊Pareto支配和分布密度的Pareto解集排序方法，促進Pareto最優(yōu)前沿向理想Pareto前沿逼近，并保持了Pareto解集的多樣性。通過模擬某制造車間的實際數(shù)據(jù)對本文算法進行了仿真，結果驗證了調(diào)度模型的合理性和調(diào)度算法的有效性。

［1］王萬良，吳啟迪.生產(chǎn)調(diào)度智能算法及其應用［M］.北京：科學出版社，2007：12-13.

［2］Xing L，Chen Y，Yang K.Multi-objective flexible Job Shop scheduling：design and evaluation by simulation modeling［J］. Applied Soft Computing，2009，9（1）：362-376.

［3］徐新黎，應時彥，王萬良.求解模糊柔性Job shop調(diào)度問題的多智能體免疫算法［J］.控制與決策，2010，25（2）：171-184.

［4］Zhang G，Gao L，Shi Y.A genetic algorithm and tabu search for multi objective flexible job shop scheduling problems［C］// 2010 International Conference on Computing，Control and Industrial Engineering（CCIE），2010，4：250-254.

［5］劉愛軍，楊育，程文明，等.復雜制造環(huán)境下的改進非支配排序遺傳算法［J］.計算機集成制造系統(tǒng)，2012，18（11）：2446-2458.

［6］李鵬，邱順流，宋豫川，等.基于瓶頸工序的多資源多目標機械加工車間調(diào)度研究［J］.現(xiàn)代制造工程，2013，1（1）：1-6.

［7］Peteghem V，Vanhoucke M.A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem［J］.European Journal of Operational Research，2010，201（2）：409-418.

［8］袁亮，袁逸萍，孫文磊，等.雙資源柔性車間多目標調(diào)度優(yōu)化研究［J］.組合機床與自動化加工技術，2013（12）：149-152.

［9］Sha D Y，Lin H H.A multi-objective PSO for job shop scheduling problems［C］//Proceedings of theInternational Conference on Computer and Industrial Engineering.Troyes，2009：489-494.

［10］宋存利.求解柔性作業(yè)調(diào)度問題的協(xié)同進化粒子群算法［J］.計算機工程與應用，2013，49（21）：15-18.

［11］Sun B，Wang H，F(xiàn)ang Y.Application of ant colony algorithm in discrete job shop scheduling［C］//Proceedings of the 2nd International Symposium on Knowledge Acquisition and Modeling（KAM），Wuhan，2009：29-31.

［12］王碩.基于改進蟻群算法的作業(yè)車間調(diào)度研究［D］.上海：華東理工大學，2013.

［13］Simon D.Biogeography-based optimization［J］.IEEE Transactions Evolutionary Computation，2008，6（12）：702-713.

［14］Panchal V K，Singh P，Kaur N.Biogeography based satellite image classification［J］.International Journal of Computer Science and Information Security，2009，6（2）：269-274.

［15］Savsani V，Rao R，Vakharia D.Discrete optimization of a gear train using biogeography based optimization technique［J］.InternationalJournalofDesignEngineering，2009，2（2）：205-223.

［16］陳道君，龔慶武，喬卉，等.采用改進生物地理學算法的風電并網(wǎng)電力系統(tǒng)多目標發(fā)電調(diào)度［J］.中國電機工程學報，2012，32（31）：150-158.［17］Rahmati S H A，Zandieh M.A new biogeography-based optimization algorithm for the flexible job shop scheduling problem［J］.International Journal of Advanced Manufacturing Technology，2012，58（9）：1115-1129.

［18］He Z，Yen G G，Zhang J.Fuzzy-based Pareto optimality many-objective evolutionary algorithms［J］.IEEE Transactions on Evolutionary Computation，2013，99（1）：1-15.

［19］Ma H.An analysis of the equilibrium of migration models for biogeography-based optimization［J］.Information Sciences，2010，180（18）：3444-3464.

［20］Kacem I，Hammadi S，Borne P.Approach by localization and multi-objective evolutionary optimization for flexible job-shop scheduling problems［J］.IEEE Transactions on Systems，Man and Cybernetics，2002，32（1）：408-419.

［21］Xia W J，Wu Z M.An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problem［J］.Computers&Industrial Engineering，2005，48：409-425.

［22］周晏明.基于改進遺傳算法的多目標作業(yè)車間調(diào)度研究［D］.哈爾濱：東北林業(yè)大學，2013.

Biogeography-based optimization algorithm for flexible job-shop scheduling problems.

WU Dinghui，KONG Fei，ZHU Shaowen，JI Zhicheng

Key Laboratory of Advanced Process Control for Light Industry，Jiangnan University，Wuxi，Jiangsu 214122，China

To solve the multi-objective problem in flexible job-shop scheduling considering the resource constraints of machines and operators，F(xiàn)uzzy Pareto Dominance-Combined Biogeography-Based Optimization scheduling algorithm（FPDCBBO）is proposed.Using the method of fuzzy Pareto to calculate the dominant degree between the solutions and sorted，updating the global optimal value.Cosine migration model is used to improve the convergence speed of biogeography-based algorithm.Finally，the algorithm is applied in an actual production instances，the feasibility and efficiency of algorithm are verified.

flexible job-shop scheduling；Fuzzy Pareto Dominance（FPD）；Biogeography-Based Optimization algorithm（BBO）；cosine migration model；double resource constraints

A

TP393

10.3778/j.issn.1002-8331.1408-0178

國家高技術研究發(fā)展計劃（No.2013AA040405）。

吳定會（1970—），男，博士，副教授，研究領域為RFID網(wǎng)絡優(yōu)化，生產(chǎn)調(diào)度；孔飛（1986—），男，碩士研究生，研究領域為車間作業(yè)調(diào)度；朱紹文（1988—），女，碩士，研究領域為生產(chǎn)作業(yè)調(diào)度；紀志成（1961—），男，博士，教授，研究領域為運動控制、RFID網(wǎng)絡優(yōu)化。E-mail：wh033098@163.com

2014-08-28

2014-11-25

1002-8331（2015）22-0206-08

CNKI網(wǎng)絡優(yōu)先出版：2015-04-01，http://www.cnki.net/kcms/detail/11.2127.TP.20150401.1639.014.html