基于改進(jìn)生物地理學(xué)優(yōu)化算法的分布式裝配置換流水車間調(diào)度問題

黃佳琳， 張丫丫， 顧幸生

（華東理工大學(xué)化工過程先進(jìn)控制和優(yōu)化技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，上海 200237）

置換流水車間調(diào)度問題(Permutation Flowshop Scheduling Problem, PFSP)是制造系統(tǒng)和工業(yè)過程中廣泛研究的組合優(yōu)化問題[1]，通常假設(shè)所有的工件都在一個(gè)工廠中進(jìn)行加工，即單一工廠生產(chǎn)模式?，F(xiàn)如今，在全球化的背景下，分布式制造以低成本、低風(fēng)險(xiǎn)、高質(zhì)量的優(yōu)勢(shì)取代了單一工廠生產(chǎn)模式，成為工業(yè)生產(chǎn)過程中的主流形式。比起單一工廠調(diào)度問題，分布式制造的調(diào)度問題更為復(fù)雜。它不僅需要考慮工件在機(jī)器上的加工順序，還必須考慮如何將工件合理地分配到相應(yīng)的工廠進(jìn)行加工。不同工廠的不同工件分配會(huì)形成不同的調(diào)度方案，從而影響供應(yīng)鏈的績效[2]。

裝配流水車間調(diào)度問題(Assembly Flowshop Scheduling Problem, AFSP)廣泛存在于生產(chǎn)制造系統(tǒng)中，用于生產(chǎn)由不同工件裝配而成的多種產(chǎn)品[3]?？紤]到裝配系統(tǒng)在工業(yè)過程中的實(shí)際應(yīng)用，裝配流水車間調(diào)度問題也是生產(chǎn)調(diào)度領(lǐng)域的重點(diǎn)問題。裝配流水車間是一個(gè)混合生產(chǎn)系統(tǒng)，其中各個(gè)生產(chǎn)操作都是獨(dú)立并且同時(shí)執(zhí)行的，以便將工件運(yùn)輸?shù)窖b配線，及時(shí)進(jìn)行產(chǎn)品的組裝。在組裝過程中，可以由給定數(shù)量的不同工件根據(jù)裝配程序制造各種各樣的最終產(chǎn)品，裝配程序代表了由不同供應(yīng)商提供的不同工件之間的組裝關(guān)系[4]。

分布式裝配置換流水車間調(diào)度問題(Distributed Assembly Permutation Flowshop Scheduling Problem,DAPFSP)是分布式置換流水車間調(diào)度問題和裝配流水車間調(diào)度問題的結(jié)合，最早由Hatami 等[5]提出。Hatami 等針對(duì)DAPFSP 問題，以最小化裝配工廠完工時(shí)間為目標(biāo)，提出了基于不同結(jié)構(gòu)的啟發(fā)式算法和可變鄰域下降(VND)算法等12 種方法。在此基礎(chǔ)上，越來越多的優(yōu)化算法被應(yīng)用于求解DAPFSP問題。2016 年，Wang 等[6]提出了基于分布估計(jì)算法的模因算法(EDAMA)來求解DAPFSP 問題，通過與文獻(xiàn)[5]的12 種啟發(fā)式與元啟發(fā)式算法比較，驗(yàn)證了 EDAMA 算法的優(yōu)越性。2017 年，Lin 等[7]采用回溯搜索超啟發(fā)式(BS-HH)算法，同樣與12 種方法以及EDAMA 等智能優(yōu)化算法進(jìn)行比較，突出了BSHH 算法的有效性。2019 年，Pan 等[8]針對(duì)新型 DAPFSP問題的不同的CPU 時(shí)間和解決方案質(zhì)量的需求，提出了一個(gè)混合整數(shù)線性模型，還列出了3 種不同結(jié)構(gòu)的啟發(fā)式算法、兩種可變鄰域搜索方法以及迭代貪婪算法，最后在算法性能和運(yùn)算時(shí)間兩方面與其他16 個(gè)已有算法進(jìn)行對(duì)比，結(jié)果表明所提算法能夠高效地解決新型DAPFSP 問題。

生物地理學(xué)優(yōu)化(Biogeography-Based Optimization, BBO)[9]算法自提出以來，因?qū)栴}依賴度小、算法參數(shù)少、易于實(shí)現(xiàn)等優(yōu)點(diǎn)備受青睞。Rahmati 等[10]采用BBO 算法求解包含3 個(gè)目標(biāo)函數(shù)的柔性作業(yè)車間調(diào)度問題，并且對(duì)遺傳算法和BBO 算法進(jìn)行比較，利用基準(zhǔn)測(cè)試數(shù)據(jù)（Brandimart 數(shù)據(jù)）以及Barnes和Chamber 數(shù)據(jù)的運(yùn)算，凸顯了BBO 算法的優(yōu)勢(shì)。Lin 等[11]采用和聲搜索算法和基于對(duì)立的學(xué)習(xí)方法改進(jìn)BBO 算法來求解專色印刷的專色匹配問題，通過與粒子群算法的比較，驗(yàn)證了BBO 算法的有效性。然而，BBO 算法存在收斂速度緩慢、易陷入局部最優(yōu)解以及在規(guī)定迭代次數(shù)中難以獲得最優(yōu)解等缺點(diǎn)[12]?？紤]到分布式裝配置換流水車間的加工特點(diǎn)，本文設(shè)計(jì)了3 種改進(jìn)策略：首先，使用加工時(shí)間最短優(yōu)先（Shortest Processing Time，SPT）規(guī)則和 NR2規(guī)則改善初始可行解的結(jié)構(gòu)；其次，在變異過程中加入基于工廠完工時(shí)間的工件插入啟發(fā)式方法，優(yōu)化工件的工廠分配策略及其在各工廠內(nèi)的加工順序；最后結(jié)合模擬退火算法，跳出局部最優(yōu)，提高算法尋優(yōu)的質(zhì)量。仿真結(jié)果證明了改進(jìn)的BBO 算法求解分布式裝配置換流水車間調(diào)度問題的有效性。

1 分布式裝配置換流水車間調(diào)度問題

1.1 問題的描述

分布式裝配置換流水車間調(diào)度問題包括兩個(gè)階段：生產(chǎn)階段和裝配階段，并且可以概括為3 個(gè)子問題：工件調(diào)度、產(chǎn)品調(diào)度和工廠分配，如圖1 所示。

圖 1 分布式裝配置換流水車間調(diào)度問題Fig. 1 Distributed assembly permutation flowshop scheduling problem

1.2 模型的目標(biāo)函數(shù)

2 生物地理學(xué)優(yōu)化算法

BBO 算法是一類基于種群和生物啟發(fā)的群智能優(yōu)化算法，其核心是棲息地間種群的遷移和變異過程，同時(shí)這兩個(gè)過程也是算法實(shí)現(xiàn)優(yōu)化操作的主要步驟。

2.1 生物地理學(xué)優(yōu)化算法的設(shè)計(jì)原理

生物種群分布于不同的棲息地，各棲息地都可用對(duì)應(yīng)的適宜度指數(shù)(Habitat Suitability Index,HSI)來表示。與HSI 相關(guān)的特征包括棲息地的降雨量、植被的多樣性和氣候等因素，構(gòu)成了一個(gè)描述棲息地適宜度的向量SIV(Suitable Index Vector)[15]。應(yīng)用BBO 算法求解優(yōu)化問題時(shí)，一個(gè)棲息地對(duì)應(yīng)優(yōu)化問題的一個(gè)可行解，通過計(jì)算各棲息地的適宜度值來評(píng)價(jià)這些解的優(yōu)劣程度。根據(jù)不同棲息地之間物種的遷移操作和棲息地內(nèi)物種的變異操作，使適應(yīng)度值較差的棲息地獲得更多適應(yīng)度值較好的棲息地的信息，實(shí)現(xiàn)棲息地的不斷進(jìn)化[16]。

2.2 生物地理學(xué)優(yōu)化算法的遷移操作

BBO 算法通過遷移算子實(shí)現(xiàn)棲息地之間的信息交互，從而達(dá)到進(jìn)化的目的。棲息地的適宜度值越高，其所能容納的物種數(shù)量越多，反之則越少，這就需要建立一個(gè)表征物種數(shù)量與棲息地適宜度關(guān)系的映射函數(shù)[17]。BBO 算法根據(jù)各個(gè)棲息地的適宜度值，從大到小進(jìn)行排序，設(shè)棲息地?cái)?shù)量為P，最大物種數(shù)為 Nmax，則棲息地 n 的物種數(shù)量 N(n)=Nmax-n，n=1, 2, …, P（n 是各棲息地經(jīng)過排序后的序號(hào)）。物種在棲息地之間的遷移操作根據(jù)遷出率μ(n)和遷入率λ(n)進(jìn)行，各棲息地的μ(n)和λ(n)的計(jì)算公式如式(8)、式 (9)所示：

圖 2 遷入率、遷出率與物種數(shù)量的關(guān)系Fig. 2 Relationship between immigration rate, emigration rate and species quantity

2.3 生物地理學(xué)優(yōu)化算法的變異操作

突發(fā)的災(zāi)難性事件能夠完全改變一個(gè)棲息地的生態(tài)環(huán)境，導(dǎo)致棲息地的適宜度值產(chǎn)生巨變，生物地理學(xué)中通過變異來模擬這一情況[19]。BBO 算法根據(jù)變異概率隨機(jī)地修改棲息地的特征向量，變異概率主要取決于棲息地的物種數(shù)量概率，也可以說和棲息地的物種數(shù)量息息相關(guān)。物種數(shù)量為N(n)的棲息地發(fā)生變異的概率 mn如式(10)所示：

3 MBBO 算法求解 DAPFSP 問題

3.1 編碼與解碼

應(yīng)用改進(jìn)的生物地理學(xué)優(yōu)化(MBBO)算法求解分布式裝配置換流水車間調(diào)度問題時(shí)，在初始化階段將采用兩種不同的編碼方式生成初始可行解，分別稱為規(guī)則解和隨機(jī)解。

規(guī)則解主要是根據(jù)SPT 規(guī)則生成。將每個(gè)產(chǎn)品中的工件按SPT 規(guī)則進(jìn)行排列，確定每個(gè)產(chǎn)品的工件加工順序。在此基礎(chǔ)上，計(jì)算每個(gè)產(chǎn)品的裝配開始時(shí)間，并規(guī)定最早開始裝配的產(chǎn)品排在前面，由此產(chǎn)生產(chǎn)品序列。兩者結(jié)合即為一個(gè)完整的工件加工序列，這樣產(chǎn)生的規(guī)則解是唯一的。最后采用NR2規(guī)則進(jìn)行解碼。NR2規(guī)則定義為[13]：將工件 j 分配給包含工件j 之后最大完工時(shí)間最小的工廠，由此生成新的調(diào)度方案。

隨機(jī)解引入了“虛擬工件”的概念，其包含了工件和工廠兩種因素。首先，將所有工件進(jìn)行隨機(jī)排列，生成一個(gè)工件加工序列；然后，將工廠作為“虛擬工件”，插入到已有的工件加工序列中，“虛擬工件”的個(gè)數(shù)同工廠的數(shù)量一致，并且“虛擬工件”用數(shù)字“0”表示。需要注意的是，每個(gè)隨機(jī)解的第1 列必須是“虛擬工件”，即必須為“0”，否則將存在不能在任何工廠加工的工件，這樣的隨機(jī)解就變成了不可行解。除此之外，若隨機(jī)解存在兩個(gè)“虛擬工件”相鄰的情況，就表示存在某個(gè)工廠處于閑置狀態(tài)，不加工任何工件。這樣的解雖然屬于可行解，但根據(jù)實(shí)際生產(chǎn)過程可以判斷，此類解的適應(yīng)度值一般比較低。為了提高初始可行解的質(zhì)量，MBBO 算法以將工件均勻分配給各個(gè)工廠的方式生成新的初始解，取代存在工廠閑置情況的初始解。隨機(jī)解的解碼根據(jù)最大完工時(shí)間的計(jì)算公式進(jìn)行計(jì)算。

以 8 個(gè)工件、2 臺(tái)機(jī)器、2 個(gè)工廠、2 個(gè)產(chǎn)品的分布式裝配置換流水車間調(diào)度問題為例，隸屬于2 個(gè)產(chǎn)品的工件分別為：產(chǎn)品1={1,2,4,8}，產(chǎn)品2={3,5,6,7}。對(duì)于規(guī)則解，所有工件按SPT 規(guī)則排列后，每個(gè)產(chǎn)品的工件加工順序如下：產(chǎn)品1={8,1,2,4}，產(chǎn)品2={7,5,3,6}，此時(shí)，兩個(gè)產(chǎn)品的開始裝配時(shí)間分別為：產(chǎn)品1=127，產(chǎn)品2=133，則規(guī)則解的工件排序如圖3 所示。最后根據(jù)NR2規(guī)則解碼，得出規(guī)則解的具體形式及最大完工時(shí)間 Cmax(Λrule)=501 ，規(guī)則解的具體形式如圖4所示。

圖 4 規(guī)則解的具體形式Fig. 4 Specific form of rule solution

針對(duì)這個(gè)例子，隨機(jī)解就是利用randperm 函數(shù)對(duì)1～9 進(jìn)行隨機(jī)排序，并把大于8 的數(shù)置零，最后在首位插入一個(gè)“0”。隨機(jī)解的數(shù)量很多，從中挑出一個(gè)，其具體形式如圖5 所示。

圖 5 隨機(jī)解的具體形式Fig. 5 Specific form of random solution

3.2 按照適應(yīng)度值排序

在執(zhí)行精英保留策略、遷移操作和變異操作之前，需要計(jì)算各個(gè)棲息地即各個(gè)初始可行解的適應(yīng)度值，并按照從大到小的順序進(jìn)行降序排序，最優(yōu)解排在第一位。

3.3 精英保留策略

BBO 算法在迭代過程中有可能生成適應(yīng)度值更高的解，若不對(duì)這些優(yōu)良解采取保護(hù)措施[17]，放任它們參與遷移操作和變異操作，很容易破壞優(yōu)良解的結(jié)構(gòu)，喪失獲取更優(yōu)可行解的機(jī)會(huì)，導(dǎo)致算法的搜索能力下降。MBBO 算法加入了精英保留策略，即在每次執(zhí)行遷移和變異操作之前，取初始可行解數(shù)量的10%作為精英解，不作任何改變，而是保留到下一步迭代過程再進(jìn)行相應(yīng)操作。

3.4 遷移操作

BBO 算法通過遷移操作，用較優(yōu)解中的元素來取代較差解中的元素，以此實(shí)現(xiàn)棲息地之間的信息交互。MBBO 算法的遷移操作和BBO 算法的遷移操作大同小異。對(duì)每個(gè)解，在執(zhí)行遷移操作時(shí)，改進(jìn)前后的算法同樣都是按位進(jìn)行循環(huán)，根據(jù)遷入率判斷該位是否發(fā)生遷入，若發(fā)生遷入，再根據(jù)輪盤賭法選擇遷出的位，進(jìn)行相應(yīng)位的交換操作。MBBO 算法有兩個(gè)特別之處：第一，對(duì)于規(guī)則解，規(guī)定其不參與遷移操作。因?yàn)橐?guī)則解的特色就在于它是產(chǎn)品序列和各產(chǎn)品工件序列的結(jié)合，每個(gè)產(chǎn)品的工件不能分開，否則將會(huì)影響產(chǎn)品的裝配開始時(shí)間，進(jìn)而影響解的結(jié)構(gòu)，致使該解失去作為規(guī)則解的優(yōu)勢(shì)。第二，對(duì)于隨機(jī)解，在按位循環(huán)判斷是否發(fā)生遷入或是根據(jù)輪盤賭選擇遷出位的時(shí)候，都必須跳過每個(gè)解的第一位（第一位都是“0”，即“虛擬工件”），否則將會(huì)生成不可行解。

3.5 改進(jìn)的變異操作

BBO 算法利用變異操作來保證解的多樣性，抑制算法的早熟現(xiàn)象。BBO 算法的變異過程是根據(jù)變異概率判斷解（棲息地）的某個(gè)特征分量是否發(fā)生突變，具體操作與遷移過程相似。首先按位進(jìn)行循環(huán)，根據(jù)變異概率判斷該位置元素是否發(fā)生變異，若發(fā)生變異，則隨機(jī)選擇變異的位，進(jìn)行合法交換即可。然而，BBO 算法的變異過程隨機(jī)性較大，很有可能破壞之前的優(yōu)勢(shì)解，因此MBBO 算法對(duì)此進(jìn)行了改進(jìn)，加入了基于工廠完工時(shí)間的工件插入啟發(fā)式方法。在MBBO 算法的變異過程中，利用變異概率判斷某個(gè)解而不是解的某個(gè)特征分量是否進(jìn)行突變，若確定該解發(fā)生突變，則依次將該解中完工時(shí)間最大的工廠的每個(gè)工件插入到該解中完工時(shí)間最小的工廠的工件序列中，并找到最佳的插入位置。插入最佳位置后，比較新解和舊解的工廠最大完工時(shí)間，若新解的工廠最大完工時(shí)間小于舊解的最大完工時(shí)間，則接受新解，反之，則返回舊解。基于工廠完工時(shí)間的工件插入啟發(fā)式方法的偽代碼如下：

3.6 模擬退火算法

為了提高解的質(zhì)量，MBBO 算法還結(jié)合了模擬退火算法，有助于跳出局部最優(yōu)解，增強(qiáng)算法的搜索能力。

考慮到MBBO 算法的效率問題，在算法迭代過程中，記錄每次的最優(yōu)值，若在最后20 次的迭代過程中，最優(yōu)值都保持不變，則對(duì)得到的最優(yōu)解采用模擬退火算法進(jìn)行進(jìn)一步尋優(yōu)。模擬退火算法的偽代碼如下：

3.7 MBBO 算法求解 DAPFSP 問題

MBBO 算法求解DAPFSP 問題的過程中，可行解表示棲息地，每個(gè)可行解都由一個(gè)行矩陣表示，而棲息地中的物種由矩陣中的元素及它的位置信息共同表示。適應(yīng)度值對(duì)應(yīng)著于目標(biāo)函數(shù)值的倒數(shù)，目標(biāo)函數(shù)值即式(7)計(jì)算出的值。MBBO 算法求解DAPFSP 問題的具體流程如圖6 所示。

4 仿真實(shí)驗(yàn)

為了驗(yàn)證改進(jìn)的生物地理學(xué)優(yōu)化算法求解分布式裝配置換流水車間調(diào)度問題的有效性，對(duì)兩組基準(zhǔn)數(shù)據(jù)（http://soa.iti.es）進(jìn)行仿真計(jì)算。每組數(shù)據(jù)由4 個(gè)變量組成：n（工件數(shù)）、m（機(jī)器數(shù)）、F（工廠數(shù)）、H（產(chǎn)品數(shù)）。第1 組由900 個(gè)小型實(shí)例組成，其中，n={8,12,16,20,24}，m={2,3,4,5}，F(xiàn)={2,3,4}，H={2,3,4}。第2 組由540 個(gè)大型實(shí)例組成，其中，n={100,200}，m={5,10,20}，F(xiàn)={4,6,8}，H={30,40,50}。對(duì)于小型實(shí)例，每個(gè)組合都有5 個(gè)例子；對(duì)于大型實(shí)例，每個(gè)組合有 10 個(gè)例子[6]。

采用平均相對(duì)百分比偏差(ARPD)來評(píng)估算法的性能[7]，計(jì)算公式如下：

其中：Cbest為所有實(shí)例已知的最佳解決方案的最優(yōu)值；Ci為算法每次運(yùn)行后得到的最大完工時(shí)間的最小值，即算法的最優(yōu)值，一共運(yùn)行 R 次。如果ARPD＜0，則表明產(chǎn)生了新的最佳解決方案。所有實(shí)例的已知最優(yōu)解都可在http://soa.iti.es 上獲得。

4.1 參數(shù)設(shè)置

MBBO 算法有4 個(gè)關(guān)鍵參數(shù)：棲息地?cái)?shù)量P（初始化產(chǎn)生的可行解的數(shù)量）、最大突變率mmax、最大迭代次數(shù)MaxIterations 以及退火率α。為了研究這4 個(gè)參數(shù)對(duì)MBBO 算法性能的影響，采用正交試驗(yàn)的方法對(duì)實(shí)例I_24_3_2_2_1 進(jìn)行仿真計(jì)算。其中的“24”表示工件總數(shù)為 24，“3”表示每個(gè)工廠都有 3 臺(tái)機(jī)器，第 1 個(gè)“2”表示一共有兩個(gè)工廠，第 2 個(gè)“2”表示最終裝配出兩個(gè)產(chǎn)品，末尾的1 表示這個(gè)實(shí)例是這個(gè)組合的第1 個(gè)例子。表1 列出了影響算法性能的關(guān)鍵參數(shù)的不同組合。

圖 6 MBBO 算法求解DAPFSP 問題的流程圖Fig. 6 Flow chart of MBBO for solving DAPFSP

表 1 不同參數(shù)值的組合Table 1 Combination of different parameters

所有的參數(shù)組合都采用MBBO 算法運(yùn)行10 次，計(jì)算平均最大完工時(shí)間(AM)，所得結(jié)果列于表2，由此觀察不同參數(shù)對(duì)算法性能的影響，最終找出最令人滿意的參數(shù)組合。

對(duì)于每個(gè)參數(shù)，將平均最大完工時(shí)間作為關(guān)鍵指標(biāo)，判斷每個(gè)參數(shù)的趨勢(shì)，結(jié)果如圖7 所示。

由圖7 可以看出，棲息地?cái)?shù)量和最大迭代次數(shù)越大，算法的性能越好，但同時(shí)計(jì)算成本會(huì)增加，時(shí)間明顯變慢。綜合考慮算法的性能效果以及耗費(fèi)的時(shí)間成本，選取MBBO 算法參數(shù)如下：P=50，mmax=0.10，MaxIterations=100，α=0.9。此外，最大遷入率 I 和最大遷出率E 均設(shè)為1，取棲息地?cái)?shù)量P 的10%作為保留的精英解。

4.2 模擬退火算法對(duì)MBBO 算法的影響

圖 7 參數(shù)趨勢(shì)圖Fig. 7 Parameter trend chart

表 2 不同組合的平均最大完工時(shí)間Table 2 Average maximum completion time for different combinations

為了驗(yàn)證模擬退火算法對(duì)改進(jìn)生物地理學(xué)優(yōu)化算法的有效性，對(duì)所有小型實(shí)例進(jìn)行仿真，比較了使用和不使用模擬退火算法的MBBO 算法的實(shí)例運(yùn)算結(jié)果。兩個(gè)算法都具有相同的參數(shù)設(shè)置（除了SA 算法的部分）和停止條件，并且獨(dú)立運(yùn)行5 次。表3 列出了F 和n 的15 個(gè)組合的平均ARPD 值，每個(gè)組合包含60 個(gè)小型實(shí)例。

模擬退火算法具有很強(qiáng)的全局搜索能力，能夠使算法跳出局部最優(yōu)而趨向于全局最優(yōu)。從表3 可以看出，在大多數(shù)組合中，融合了模擬退火算法的MBBO 算法可以利用模擬退火算法的優(yōu)勢(shì)來獲得較低的ARPD 值。不僅如此，MBBO 算法在有和沒有模擬退火算法的情況下獲得的ARPD 平均值分別為0.051 和0.100，前者的算法性能明顯高于后者。由此可見，混合入模擬退火算法可以有效地改善所提出的MBBO 算法的性能。

4.3 DAPFSP 問題的小型實(shí)例

運(yùn)用MBBO 算法求解分布式裝配置換流水車間調(diào)度問題的900 個(gè)小型實(shí)例，每個(gè)實(shí)例都獨(dú)立運(yùn)行5 次，記錄每次得到的算法最優(yōu)值，利用ARPD 值評(píng)估算法的性能。表4 列出了F 和n 的15 種不同組合分組的統(tǒng)計(jì)結(jié)果，每個(gè)組合都包含60 個(gè)實(shí)例。取60 個(gè)實(shí)例的平均ARPD 值作為最終結(jié)果，并與H11、H12、 H21、 H22、 H31、 H32、 V NDH11、 V NDH12、 V NDH21、VNDH22、 V NDH31、 V NDH32算法進(jìn)行比較。這 12 個(gè)算法都是用來解決DAPFSP 問題的有效方法，各算法的結(jié)果直接從文獻(xiàn)中獲得[5]。

表 3 MBBO 算法的小型實(shí)例運(yùn)算結(jié)果Table 3 Small-sized instances results of MBBO algorithm

表 4 小型實(shí)例平均ARPD 值的結(jié)果對(duì)比Table 4 Comparison of average ARPD values of small-sized instances

從表4 可以看出，對(duì)于所有的小型實(shí)例，MBBO算法獲得的結(jié)果明顯優(yōu)于12 個(gè)啟發(fā)式與元啟發(fā)式算法，且每個(gè)組合的平均ARPD 值和MBBO 算法的平均值均遠(yuǎn)遠(yuǎn)小于列出的12 個(gè)算法。不僅如此，MBBO 算法還更新了一些已知最佳方案，例如組合2×20 和 2×24 的 60 個(gè)實(shí)例的 ARPD平均值小于零。

本文還將MBBO 算法與BBO 算法的運(yùn)算結(jié)果進(jìn)行了比較。由于BBO 算法較為簡(jiǎn)單，運(yùn)算速度快，因此對(duì)BBO 算法的參數(shù)進(jìn)行如下調(diào)整：P=100，mmax=0.1，MaxIterations=200，I=E=1，取 P 的 10% 作為保留的精英解。由表4 可知，MBBO 算法求解DAPFSP問題的效率明顯高于BBO 算法。在工廠數(shù)和工件數(shù)均較小的情況下（如 2×8 和 2×12），BBO 算法以初始棲息地和迭代次數(shù)多的優(yōu)勢(shì)，比MBBO 算法略勝一籌，但差別并不大。而當(dāng)工廠數(shù)和工件數(shù)增大之后，BBO 算法便顯出頹勢(shì)，所得結(jié)果大不如MBBO 算法。所以，針對(duì)DAPFSP 問題，引入本文的3 種策略能有效地改善BBO 算法的性能，提高所得最優(yōu)解的質(zhì)量。

4.4 DAPFSP 問題的大型實(shí)例

針對(duì)分布式裝配置換流水車間調(diào)度問題的540 個(gè)大型實(shí)例，同樣運(yùn)用MBBO 算法，將每個(gè)實(shí)例獨(dú)立運(yùn)行5 次，記錄每次得到的算法最優(yōu)值，利用ARPD 值評(píng)估算法的性能。表5 列出了工件數(shù)n=100和n=200 時(shí)的統(tǒng)計(jì)結(jié)果，每組都包含270 個(gè)實(shí)例，最終結(jié)果為每組所有實(shí)例的ARPD 平均值，然后與12 個(gè)啟發(fā)式與元啟發(fā)式算法以及BBO 算法的結(jié)果進(jìn)行比較。

表 5 大型實(shí)例平均ARPD 值的結(jié)果對(duì)比Table 5 Comparison of average ARPD values of large-sized instances

由表 5 可以看出，當(dāng)n=100 時(shí)，MBBO 算法有較大的優(yōu)越性，其獲得的大型實(shí)例的ARPD 平均值要遠(yuǎn)小于 H11、H12、H21、H22、H31、H32、 V NDH11、 V NDH12、VNDH21、 V NDH31這10 種算法的結(jié)果。當(dāng)工件個(gè)數(shù)上升到 n=200 時(shí)，MBBO 算法獲得的大型實(shí)例的ARPD 平均值均優(yōu)于 H11、H12、H31、H32這 4 種啟發(fā)式算法的結(jié)果，而比另外幾種啟發(fā)式和元啟發(fā)式算法稍顯不足。在大規(guī)模的實(shí)例中，與BBO 算法相比，MBBO 算法顯然更為合理、高效，兩個(gè)算法結(jié)果的平均值相差0.753，MBBO 算法優(yōu)勢(shì)顯著。

綜上所述，利用MBBO 算法求解DAPFSP 問題時(shí)，針對(duì)ARPD 平均值這個(gè)指標(biāo)，在多數(shù)規(guī)模的實(shí)例上均效果良好，在某些實(shí)例上還找到了比已知方案更佳的結(jié)果。表6 列出了小型實(shí)例和大型實(shí)例中MBBO算法更新的最佳方案。MBBO 算法在初始化階段利用SPT 規(guī)則、NR2規(guī)則和“虛擬工件”改良初始解，縮小算法搜索解空間的范圍，提高搜索效率。在變異階段，根據(jù)各工廠完工時(shí)間的信息，采用基于工廠完工時(shí)間的工件插入啟發(fā)式方法，優(yōu)化工件的工廠分配及加工順序。同時(shí)，結(jié)合模擬退火算法，跳出局部最優(yōu)，提高了算法的搜索能力。MBBO 算法是求解DAPFSP 問題的一種有效算法。

5 結(jié)束語

本文針對(duì)分布式裝配置換流水車間調(diào)度問題，提出了一種改進(jìn)的生物地理學(xué)優(yōu)化算法及其應(yīng)用于分布式裝配置換流水車間調(diào)度問題的基本步驟，取得了較好的優(yōu)化效果。針對(duì)BBO 算法的缺點(diǎn)，提出了3 種改進(jìn)策略：使用SPT 規(guī)則和NR2規(guī)則初始化棲息地；在變異過程中加入基于工廠完工時(shí)間的工件插入啟發(fā)式方法；加入模擬退火算法跳出局部最優(yōu)。這3 種改進(jìn)策略提高了算法的搜索能力，改善了算法的尋優(yōu)效果。通過900 小型實(shí)例和540 個(gè)大型實(shí)例的仿真計(jì)算，并與12 個(gè)啟發(fā)式與元啟發(fā)式算法以及BBO 算法進(jìn)行比較，驗(yàn)證了MBBO 算法求解DAPFSP 問題的有效性。

今后可以從以下幾個(gè)方面做進(jìn)一步的研究：

(1) 在遷移和變異操作過程中，MBBO 算法只是針對(duì)遷移和變異的方式進(jìn)行改進(jìn)，沒有對(duì)其根本的

遷入率、遷出率和變異概率進(jìn)行優(yōu)化?？梢钥紤]對(duì)遷移概率和變異概率的計(jì)算公式做出相應(yīng)的改進(jìn)，以提高算法的搜索能力。

表 6 MBBO 算法更新的最佳方案Table 6 Best solutions updated by MBBO

(2) 目前，利用啟發(fā)式方法和智能優(yōu)化算法求解分布式裝配置換流水車間調(diào)度問題已經(jīng)有了初步進(jìn)展。可以考慮在DAPFSP 問題的基礎(chǔ)上進(jìn)行拓展，進(jìn)一步加深問題的復(fù)雜度，例如研究具有順序相關(guān)準(zhǔn)備時(shí)間的分布式裝配置換流水車間調(diào)度問題等。