改善地理學算法求解柔性作業調度問題論文

改善地理學算法求解柔性作業調度問題論文

　　1、問題描述

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

　　2、BBO算法求解

　　2.1算法概述

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

　　2.2編碼

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

　　3、仿真實驗與結果

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

　　4、結論

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

【改善地理學算法求解柔性作業調度問題論文】相關文章：

應用遺傳算法解決車間作業調度問題03-07

柔性機械臂逆動力學問題的分析和求解03-20

車輛路徑調度問題的啟發式算法綜述11-22

人文地理學論文寫作問題03-27

遺傳算法及其在求解TSP中的應用03-07

小學數學作業批改問題的研討論文12-08

礦山機電設備管理的問題及改善途徑論文11-20

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

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

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