求解工件加工調(diào)度問題的一種混合鄰域搜索算法.pdf

1、工件加工調(diào)度問題是最困難的組合優(yōu)化問題之一。工件加工調(diào)度是利用有限的機(jī)器資源滿足加工任務(wù)的各種要求，確定工件在相關(guān)加工機(jī)器上的加工順序和時間，以保證所選擇的性能指標(biāo)最優(yōu)。 鄰域搜索是一種很重要的求解工件加工調(diào)度問題的啟發(fā)式算法。論文重點研究了鄰域搜索算法，介紹了鄰域搜索在工件加工調(diào)度問題中的應(yīng)用。通過面向具體問題的啟發(fā)式策略，針對現(xiàn)有的鄰域搜索算法的缺點，研究如何改進(jìn)鄰域搜索的有關(guān)技術(shù)，提出了基于鄰域搜索的，結(jié)合單機(jī)調(diào)度和擬物擬

2、人思想的快速的啟發(fā)式算法。 為了說清楚所提算法的思想，提出了一些定義和定理,并嚴(yán)格證明了定理。提出了一種新的啟發(fā)式調(diào)度規(guī)則以生成初始解，作為鄰域搜索和回溯算法的出發(fā)點。利用擬物擬人的思想，構(gòu)造出新的鄰域。分析了移動瓶頸過程的子算法Schrage算法的優(yōu)缺點，提出了一種改進(jìn)的單機(jī)調(diào)度算法。 針對鄰域搜索在計算的過程中經(jīng)常會陷入局部極小值陷阱的缺點，以文中提出的新鄰域結(jié)構(gòu)為基礎(chǔ)，結(jié)合單機(jī)調(diào)度策略得到一個基于混合式鄰域結(jié)構(gòu)的搜

3、索算法HNLS。混合鄰域結(jié)構(gòu)與單一鄰域結(jié)構(gòu)相比，有助于計算跳出局部極小值的陷阱，走向前景更好的區(qū)域，搜索到更好的解。在HNLS算法中不僅把單機(jī)調(diào)度作為一種跳出局部極小值陷阱的策略，還結(jié)合擬人擬物思想，提出了“模擬調(diào)整”、“同工件工序調(diào)整”及“最小工件后移”多種策略以保證計算走向新的前景更好的區(qū)域。 使用了不同規(guī)模和難度的68個國際標(biāo)準(zhǔn)算例做為HNLS算法的測試實驗集，這些算例是近十年以來經(jīng)常被國際文獻(xiàn)提到的，其中包括OR-Lib

4、rary中所有的3個FT算例、5個ABZ算例、40個LA算例、10個ORB算例及TA1-TA10算例。試驗結(jié)果表明，對于實驗集中所有的18個10工件10機(jī)器算例，其中包括著名的難例FT10，HNLS算法全部算出了最優(yōu)解。對于實驗集中所有的40個LA算例，HNLS算法算出了其中37個算例的最優(yōu)解。HNLS算法的優(yōu)度優(yōu)于一些經(jīng)典算法，比如模擬退火、遺傳算法、禁忌搜索、移動瓶頸過程。HNLS還和目前國際上的兩種先進(jìn)算法TSSB以及Balas的

5、算法進(jìn)行了比較。Balas提出的算法根據(jù)設(shè)置參數(shù)和使用方法的不同有GLS 、SB-GLS1、SB-GLS2、SB-RGLS1和SB-RGLS2等版本，BV-best是Balas不同版本的算法對所求問題最好的解。對于HNLS和TSSB算法共同報告了計算結(jié)果的63個算例，HNLS對其中19個算例解的質(zhì)量優(yōu)于TSSB對它們解的質(zhì)量，只有一個算例TSSB對它解的質(zhì)量優(yōu)于HNLS對它解的質(zhì)量。對于HNLS和Balas的算法共同報告了計算結(jié)果的63

6、個算例, HNLS對其中6個算例解的質(zhì)量優(yōu)于BV-best的質(zhì)量，7個算例BV-best的質(zhì)量優(yōu)于HNLS對它們解的質(zhì)量。對于所測試的算例，HNLS算法中的參數(shù)是統(tǒng)一不變的。實驗結(jié)果表明，HNLS對這些算例解的優(yōu)度好于Balas的任何一個確定參數(shù)的算法對它們解的優(yōu)度。 論文還提出了一種求解工件加工調(diào)度問題的回溯算法。測試了實驗集中的22個算例，回溯算法找到了其中17個算例的最優(yōu)解。算法也測試和分析了不同回溯參數(shù)及嵌套重數(shù)對算法效