迭代貪婪算法是一種具有較強局部搜索能力的元啟發(fā)式算法,但由于傳統(tǒng)迭代貪婪算法搜索范圍過大,搜索效率有限,為了進(jìn)一步提升傳統(tǒng)迭代貪婪算法的搜索能力,考慮到閾值接受算法具有能縮小搜索范圍的特點,提出了一種改進(jìn)的迭代貪婪算法解決流水車間預(yù)制生產(chǎn)的訂單接受與調(diào)度問題;該改進(jìn)算法是在破壞原調(diào)度序列后加入一種基于構(gòu)造啟發(fā)式規(guī)則的重建策略,并結(jié)合閾值接受算法的自適應(yīng)接受準(zhǔn)則用以跳出局部最優(yōu);經(jīng)大量仿真實驗結(jié)果顯示,與傳統(tǒng)迭代貪婪算法、禁忌搜索算法以及遺傳算法對比,改進(jìn)的迭代貪婪算法具有更好的求解質(zhì)量和魯棒性。

【文章頁數(shù)】：6 頁

【部分圖文】：

圖1 基于構(gòu)造啟發(fā)式規(guī)則的破壞-重建策略圖

本文中的鄰域搜索方法采用是一種插入式的局部鄰域搜索方法。其基本思想是：每次從當(dāng)前解中隨機地選擇一個訂單，將訂單從左至右逐一試插，最終將訂單插入是目標(biāo)值增加最多的位置。如果通過鄰域搜索找到的新解優(yōu)于當(dāng)前解，則對當(dāng)前解進(jìn)行替換并繼續(xù)搜索，否則就結(jié)束搜索。3.4閾值接受準(zhǔn)則

圖2 4種算法在不同規(guī)模下的ARPD對比圖

從圖2中可以看出當(dāng)訂單規(guī)模為20的時候所有算法的ARPD值均很小，隨著問題規(guī)模的增大，IGTA算法的ARPD值呈現(xiàn)出遞增趨勢。且在哪種訂單規(guī)模下，統(tǒng)計上IGTA算法的ARPD值都是最小的，由此我們可以得出IG-TA算法在小、中、大規(guī)模問題下的求解質(zhì)量均優(yōu)于其余3種對比算法。5結(jié)....

本文編號：4056033