- 相關(guān)推薦
改善地理學(xué)算法求解柔性作業(yè)調度問(wèn)題論文
1、問(wèn)題描述
本文采用最小化最大完工時(shí)間作為目標函數，假定：(1)工序的加工順序既定，且在可供選擇的機器上的加工時(shí)間確定；(2)所有機器相互獨立，且在t＝0時(shí)刻均可用；(3)所有工件相互獨立，且在t＝0時(shí)刻均可被加工；(4)工件或機器之間具有相同優(yōu)先級；(5)不同工件的工序之間沒(méi)有相互約束；(6)同一時(shí)刻，一臺機器只能加工一個(gè)工件；(7)某個(gè)工序一旦開(kāi)始加工就不能中斷；(8)不考慮工件在不同機器之間的移動(dòng)時(shí)間。
2、BBO算法求解
2.1算法概述
BBO算法是以棲息地（habitat）作為個(gè)體進(jìn)行操作。棲息地適合物種生存的優(yōu)劣程度用棲息適應指數（habitatsuitabilityindex，HSI）來(lái)表示，具有較高HSI的棲息地更適合物種生存。與HSI相關(guān)的因素包括該區域的降雨量、植被多樣性、地貌特征和溫度等，將其稱(chēng)為適應指數變量（suitabilityindexvariables，SIV)。HSI較高的棲息地容納的物種數目較多，而HSI較低的棲息地容納的物種數目較少。對于HSI較高的棲息地，隨著(zhù)大量物種的涌入，使得容納的物種數趨于飽和，就會(huì )有大量的物種遷出，即有較大的遷出率和較小的遷入率。相應地，對于HSI較小的棲息地，其物種數量稀疏，就會(huì )有較多的物種遷入和較少的物種遷出，即有較大的遷入率與較小的遷出率。由于HSI與生物多樣性成正比，因此新種群的遷入同時(shí)又會(huì )使HSI升高。如果某個(gè)棲息地的HSI一直較低，那可能導致該棲息地物種的滅絕，或者有大量其他物種的遷入。棲息地的遷入和遷出機制使得HSI較高的個(gè)體提供優(yōu)秀個(gè)體的變量（SIV）與適應度較低的個(gè)體共享，同時(shí)又使適應度低的個(gè)體接受來(lái)自?xún)?yōu)秀個(gè)體好的特征變量，從而可能提高自己的適應度。此外，BBO算法通過(guò)對棲息地進(jìn)行突變操作，使得算法具有較強的自適應能力[14]。以生物地理學(xué)數學(xué)模型為基礎，將模型中各變量與優(yōu)化算法中的變量以及問(wèn)題空間相對應，其對應關(guān)系如表2所示。
2.2編碼
本文采用兩段式實(shí)數編碼，一段是基于工序的工序排序編碼（OperationSequence，OS)，確定各工序的加工順序；另一段是基于機器的機器分配編碼(MachineAssignment，MA)，確定每道工序的加工機器。本文采用的分段式編碼能直接體現問(wèn)題的約束條件，從而保證編碼后個(gè)體的有效性�；诠ば蚓幋aOS：長(cháng)度為工序總數L，每個(gè)OS編碼是所有工序的一個(gè)排列，每個(gè)工件的工序用相應的工件序號表示。從左到右依次掃描OS，第j次出現的工件序號，表示該工件的第j道工序�；跈C器編碼MA：長(cháng)度與OS編碼相等，每個(gè)編碼位對應每道工序的加工機器。機器順序是按照每個(gè)工件的加工順序排列，不需要與基于工序的編碼對應，即從第一個(gè)工件的第一道工序開(kāi)始，到最后一個(gè)工件的最后一道工序結束。其中MA的每個(gè)位置表示工序選擇的機器在可選機器集中的序號，而不是對應的機器號[15]。
3、仿真實(shí)驗與結果
根據上述改進(jìn)BBO算法的描述，采用VisualC++7.0作為編程語(yǔ)言，在IntelCore2CPU/主頻2.00GHz/內存2.00G的電腦上進(jìn)行仿真實(shí)驗。為了評估該算法的性能，本文選取研究較普遍的Kacem基準問(wèn)題進(jìn)行測試，問(wèn)題用N×M（工件數×機器數）來(lái)表示，分別是4×6、8×8、10×10、15×10柔性作業(yè)車(chē)間調度實(shí)例，對該數據集進(jìn)行仿真實(shí)驗，驗證算法的有效性。
4、結論
本文在運用BBO算法求解FJSP時(shí)，(1)首先在初始種群中引入基于規則的啟發(fā)式算法生成的優(yōu)良個(gè)體，保證多樣性的同時(shí)，加快了搜索進(jìn)程；(2)其次在迭代過(guò)程中采用了精英保留策略，通過(guò)保留一定數量的最優(yōu)或次優(yōu)個(gè)體進(jìn)行下次迭代，可避免由于特征遷移而導致的算法退化；(3)然后對遷移策略進(jìn)行了改進(jìn)，采用了更加符合FJSP的遷移率模型，當HSI從0開(kāi)始變化時(shí)，遷移率的變化率不斷增大，從而不斷加大搜索空間，提高了全局搜索性能，隨著(zhù)HSI增大到最大值附近時(shí)，遷移率的變化趨于平穩，局部搜索能力得到加強；(4)最后完善自適應變異機制，HSI較低或較高的棲息地比處于穩態(tài)的棲息地更易受到外界干擾而發(fā)生突變，這樣的變異有利于HSI較低的解集有機會(huì )獲得提高，同時(shí)又能防止陷入局部最優(yōu)。從仿真結果可以看出，改進(jìn)的BBO算法表現出了良好的搜索能力和魯棒性，能有效地求解柔性作業(yè)車(chē)間調度問(wèn)題。在算法研究上，今后還可以考慮嘗試用其他優(yōu)化算法與BBO算法結合，取長(cháng)補短設計出更好求解FJSP問(wèn)題的混合算法。另外在調度問(wèn)題上，我們將進(jìn)一步探討一些企業(yè)的多目標車(chē)間調度問(wèn)題，滿(mǎn)足更多企業(yè)的生產(chǎn)需求。
【改善地理學(xué)算法求解柔性作業(yè)調度問(wèn)題論文】相關(guān)文章：
應用遺傳算法解決車(chē)間作業(yè)調度問(wèn)題03-07
柔性機械臂逆動(dòng)力學(xué)問(wèn)題的分析和求解03-20
車(chē)輛路徑調度問(wèn)題的啟發(fā)式算法綜述11-22
人文地理學(xué)論文寫(xiě)作問(wèn)題03-27
遺傳算法及其在求解TSP中的應用03-07
小學(xué)數學(xué)作業(yè)批改問(wèn)題的研討論文12-08
初中化學(xué)教學(xué)問(wèn)題與改善對策論文11-08
調度算法等對NCS性能影響的仿真與分析03-07
迭代注水算法求解高斯矢量信道和容量研究03-07