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

吳定會(huì)，孔飛，朱紹文，紀(jì)志成

江南大學(xué)輕工過(guò)程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇無(wú)錫214122

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

吳定會(huì)，孔飛，朱紹文，紀(jì)志成

江南大學(xué)輕工過(guò)程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇無(wú)錫214122

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

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

1　引言

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

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

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

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

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

2.1問(wèn)題描述

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

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

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

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

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

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

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

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

目標(biāo)函數(shù)：

約束條件：

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

3　多目標(biāo)預(yù)備知識(shí)

3.1模糊Pareto支配

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

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

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

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

定義2（模糊Pareto支配）對(duì)于Nobj個(gè)最小化問(wèn)題，給定兩個(gè)解向量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個(gè)解向量，利用高斯型隸屬度函數(shù)分別計(jì)算出每個(gè)解向量與其他n-1個(gè)解向量的模糊值，然后通過(guò)公式（9）分別計(jì)算兩個(gè)解向量之間的模糊支配度，將n-1個(gè)模糊支配度相加后除以n-1得到的值，作為每個(gè)解向量的模糊適宜度值FFM。

3.2解的擁擠距離

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

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

3.3非支配排序

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

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

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

4　生物地理學(xué)算法

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

4.1棲息地編碼

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

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

表1　CHPSO棲息地編碼圖

4.2棲息地初始化

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

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

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

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

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

（5）令k=k+1。

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

4.3棲息地解碼

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

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

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

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

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

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

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

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

4.4適應(yīng)度函數(shù)計(jì)算

本文中適應(yīng)度函數(shù)計(jì)算過(guò)程如下：

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

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

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

4.5遷移

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

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

圖1　模糊適宜值計(jì)算偽代碼

圖2　余弦遷移模型

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

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

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

（2）將遷入棲息地Hi工序編碼中屬于G1的零件復(fù)制到臨時(shí)棲息地Hk工序編碼中，并保持它們的前后順序和位置，同時(shí)將對(duì)應(yīng)的設(shè)備和工人保持位置不動(dòng)，復(fù)制到Hk設(shè)備編碼和工人編碼中。

（3）將遷出棲息地Hj中工序編碼中包含G2的零件依次填到Hk中工序編碼的空余位置，同時(shí)將對(duì)應(yīng)的設(shè)備和工人保持位置不動(dòng)，填到Hk設(shè)備編碼和工人編碼空余的位置。

遷移操作完成后，用Hk替換Hi。以3個(gè)零件，并且每個(gè)零件有4道加工工序?yàn)榱校珿1中包括零件1，G2中包含零件2和3，如圖3所示。

圖3　遷移操作

4.6變異

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

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

（1）基于工序的變異：從種群中隨機(jī)選取一個(gè)棲息地，在對(duì)應(yīng)的棲息地第一行隨機(jī)選取兩個(gè)變異點(diǎn)，交換選取的兩個(gè)變異點(diǎn)的位置，為保證變異的可行性，保存變異前的機(jī)床號(hào)和工人號(hào)。例如隨機(jī)選取的棲息地如圖4所示。

對(duì)其第一行的第二位和第六位交換位置，并保存對(duì)應(yīng)的機(jī)器號(hào)和工序號(hào)，得到變異后棲息地如圖5所示。

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

圖4　變異前棲息地

圖5　變異后棲息地

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

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

圖6　基于設(shè)備的變異

圖7　基于工人的變異

4.7FPDCBBO算法

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

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

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

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

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

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

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

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

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

步驟8計(jì)算w中棲息地個(gè)體對(duì)應(yīng)的分目標(biāo)函數(shù)值，然后按照步驟4進(jìn)行非支配排序。

步驟9選擇前n個(gè)棲息地構(gòu)成新一代群棲息地n3。

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

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

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

表2　不同規(guī)模測(cè)試問(wèn)題結(jié)果比較

5　實(shí)例仿真

5.1基準(zhǔn)測(cè)試仿真

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

5.2實(shí)例仿真

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

表3　制造單元信息

表4　設(shè)備費(fèi)用（元·h-1）

表5　工人費(fèi)用（元·h-1）

表6　工人與設(shè)備的關(guān)系

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

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

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

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

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

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

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

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

表7　算法結(jié)果的對(duì)比

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

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

［1］王萬(wàn)良，吳啟迪.生產(chǎn)調(diào)度智能算法及其應(yīng)用［M］.北京：科學(xué)出版社，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］徐新黎，應(yīng)時(shí)彥，王萬(wàn)良.求解模糊柔性Job shop調(diào)度問(wèn)題的多智能體免疫算法［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］劉愛(ài)軍，楊育，程文明，等.復(fù)雜制造環(huán)境下的改進(jìn)非支配排序遺傳算法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2012，18（11）：2446-2458.

［6］李鵬，邱順流，宋豫川，等.基于瓶頸工序的多資源多目標(biāo)機(jī)械加工車間調(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］袁亮，袁逸萍，孫文磊，等.雙資源柔性車間多目標(biāo)調(diào)度優(yōu)化研究［J］.組合機(jī)床與自動(dòng)化加工技術(shù)，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)度問(wèn)題的協(xié)同進(jìn)化粒子群算法［J］.計(jì)算機(jī)工程與應(yīng)用，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］王碩.基于改進(jìn)蟻群算法的作業(yè)車間調(diào)度研究［D］.上海：華東理工大學(xué)，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］陳道君，龔慶武，喬卉，等.采用改進(jìn)生物地理學(xué)算法的風(fēng)電并網(wǎng)電力系統(tǒng)多目標(biāo)發(fā)電調(diào)度［J］.中國(guó)電機(jī)工程學(xué)報(bào)，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］周晏明.基于改進(jìn)遺傳算法的多目標(biāo)作業(yè)車間調(diào)度研究［D］.哈爾濱：東北林業(yè)大學(xué)，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

國(guó)家高技術(shù)研究發(fā)展計(jì)劃（No.2013AA040405）。

吳定會(huì)（1970—），男，博士，副教授，研究領(lǐng)域?yàn)镽FID網(wǎng)絡(luò)優(yōu)化，生產(chǎn)調(diào)度；孔飛（1986—），男，碩士研究生，研究領(lǐng)域?yàn)檐囬g作業(yè)調(diào)度；朱紹文（1988—），女，碩士，研究領(lǐng)域?yàn)樯a(chǎn)作業(yè)調(diào)度；紀(jì)志成（1961—），男，博士，教授，研究領(lǐng)域?yàn)檫\(yùn)動(dòng)控制、RFID網(wǎng)絡(luò)優(yōu)化。E-mail：wh033098@163.com

2014-08-28

2014-11-25

1002-8331（2015）22-0206-08

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