改善地理學(xué)算法求解柔性作業(yè)調(diào)度問題論文

　　1、問題描述

　　本文采用最小化最大完工時(shí)間作為目標(biāo)函數(shù)，假定：(1)工序的加工順序既定，且在可供選擇的機(jī)器上的加工時(shí)間確定；(2)所有機(jī)器相互獨(dú)立，且在t＝0時(shí)刻均可用；(3)所有工件相互獨(dú)立，且在t＝0時(shí)刻均可被加工；(4)工件或機(jī)器之間具有相同優(yōu)先級；(5)不同工件的工序之間沒有相互約束；(6)同一時(shí)刻，一臺機(jī)器只能加工一個(gè)工件；(7)某個(gè)工序一旦開始加工就不能中斷；(8)不考慮工件在不同機(jī)器之間的移動時(shí)間。

　　2、BBO算法求解

　　2.1算法概述

　　BBO算法是以棲息地（habitat）作為個(gè)體進(jìn)行操作。棲息地適合物種生存的優(yōu)劣程度用棲息適應(yīng)指數(shù)（habitatsuitabilityindex，HSI）來表示，具有較高HSI的棲息地更適合物種生存。與HSI相關(guān)的因素包括該區(qū)域的降雨量、植被多樣性、地貌特征和溫度等，將其稱為適應(yīng)指數(shù)變量（suitabilityindexvariables，SIV)。HSI較高的棲息地容納的物種數(shù)目較多，而HSI較低的棲息地容納的物種數(shù)目較少。對于HSI較高的棲息地，隨著大量物種的涌入，使得容納的物種數(shù)趨于飽和，就會有大量的物種遷出，即有較大的遷出率和較小的遷入率。相應(yīng)地，對于HSI較小的棲息地，其物種數(shù)量稀疏，就會有較多的物種遷入和較少的物種遷出，即有較大的遷入率與較小的遷出率。由于HSI與生物多樣性成正比，因此新種群的遷入同時(shí)又會使HSI升高。如果某個(gè)棲息地的HSI一直較低，那可能導(dǎo)致該棲息地物種的滅絕，或者有大量其他物種的遷入。棲息地的遷入和遷出機(jī)制使得HSI較高的個(gè)體提供優(yōu)秀個(gè)體的變量（SIV）與適應(yīng)度較低的個(gè)體共享，同時(shí)又使適應(yīng)度低的個(gè)體接受來自優(yōu)秀個(gè)體好的特征變量，從而可能提高自己的適應(yīng)度。此外，BBO算法通過對棲息地進(jìn)行突變操作，使得算法具有較強(qiáng)的自適應(yīng)能力[14]。以生物地理學(xué)數(shù)學(xué)模型為基礎(chǔ)，將模型中各變量與優(yōu)化算法中的變量以及問題空間相對應(yīng)，其對應(yīng)關(guān)系如表2所示。

　　2.2編碼

　　本文采用兩段式實(shí)數(shù)編碼，一段是基于工序的工序排序編碼（OperationSequence，OS)，確定各工序的加工順序；另一段是基于機(jī)器的機(jī)器分配編碼(MachineAssignment，MA)，確定每道工序的加工機(jī)器。本文采用的分段式編碼能直接體現(xiàn)問題的約束條件，從而保證編碼后個(gè)體的有效性。基于工序編碼OS：長度為工序總數(shù)L，每個(gè)OS編碼是所有工序的一個(gè)排列，每個(gè)工件的工序用相應(yīng)的工件序號表示。從左到右依次掃描OS，第j次出現(xiàn)的工件序號，表示該工件的第j道工序。基于機(jī)器編碼MA：長度與OS編碼相等，每個(gè)編碼位對應(yīng)每道工序的加工機(jī)器。機(jī)器順序是按照每個(gè)工件的加工順序排列，不需要與基于工序的編碼對應(yīng)，即從第一個(gè)工件的第一道工序開始，到最后一個(gè)工件的最后一道工序結(jié)束。其中MA的每個(gè)位置表示工序選擇的機(jī)器在可選機(jī)器集中的序號，而不是對應(yīng)的機(jī)器號[15]。

　　3、仿真實(shí)驗(yàn)與結(jié)果

　　根據(jù)上述改進(jìn)BBO算法的描述，采用VisualC++7.0作為編程語言，在IntelCore2CPU/主頻2.00GHz/內(nèi)存2.00G的電腦上進(jìn)行仿真實(shí)驗(yàn)。為了評估該算法的性能，本文選取研究較普遍的Kacem基準(zhǔn)問題進(jìn)行測試，問題用N×M（工件數(shù)×機(jī)器數(shù)）來表示，分別是4×6、8×8、10×10、15×10柔性作業(yè)車間調(diào)度實(shí)例，對該數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證算法的有效性。

　　4、結(jié)論

　　本文在運(yùn)用BBO算法求解FJSP時(shí)，(1)首先在初始種群中引入基于規(guī)則的啟發(fā)式算法生成的優(yōu)良個(gè)體，保證多樣性的同時(shí)，加快了搜索進(jìn)程；(2)其次在迭代過程中采用了精英保留策略，通過保留一定數(shù)量的最優(yōu)或次優(yōu)個(gè)體進(jìn)行下次迭代，可避免由于特征遷移而導(dǎo)致的算法退化；(3)然后對遷移策略進(jìn)行了改進(jìn)，采用了更加符合FJSP的遷移率模型，當(dāng)HSI從0開始變化時(shí)，遷移率的變化率不斷增大，從而不斷加大搜索空間，提高了全局搜索性能，隨著HSI增大到最大值附近時(shí)，遷移率的變化趨于平穩(wěn)，局部搜索能力得到加強(qiáng)；(4)最后完善自適應(yīng)變異機(jī)制，HSI較低或較高的棲息地比處于穩(wěn)態(tài)的棲息地更易受到外界干擾而發(fā)生突變，這樣的變異有利于HSI較低的解集有機(jī)會獲得提高，同時(shí)又能防止陷入局部最優(yōu)。從仿真結(jié)果可以看出，改進(jìn)的BBO算法表現(xiàn)出了良好的搜索能力和魯棒性，能有效地求解柔性作業(yè)車間調(diào)度問題。在算法研究上，今后還可以考慮嘗試用其他優(yōu)化算法與BBO算法結(jié)合，取長補(bǔ)短設(shè)計(jì)出更好求解FJSP問題的混合算法。另外在調(diào)度問題上，我們將進(jìn)一步探討一些企業(yè)的多目標(biāo)車間調(diào)度問題，滿足更多企業(yè)的生產(chǎn)需求。

【改善地理學(xué)算法求解柔性作業(yè)調(diào)度問題論文】相關(guān)文章：

應(yīng)用遺傳算法解決車間作業(yè)調(diào)度問題03-07

柔性機(jī)械臂逆動力學(xué)問題的分析和求解03-20

車輛路徑調(diào)度問題的啟發(fā)式算法綜述11-22

人文地理學(xué)論文寫作問題03-27

遺傳算法及其在求解TSP中的應(yīng)用03-07

小學(xué)數(shù)學(xué)作業(yè)批改問題的研討論文12-08

礦山機(jī)電設(shè)備管理的問題及改善途徑論文11-20

初中化學(xué)教學(xué)問題與改善對策論文11-08

調(diào)度算法等對NCS性能影響的仿真與分析03-07

迭代注水算法求解高斯矢量信道和容量研究03-07