針對最小化內(nèi)部完工期與總外包費用的雙機流水車間外包與調(diào)度聯(lián)合優(yōu)化問題,開發(fā)了一種混合變鄰域搜索算法。在該算法中,采用工件剔除型啟發(fā)式方法產(chǎn)生初始聯(lián)合決策解;基于3種新型鄰域結(jié)構(gòu)提出了最佳改進式局部搜索規(guī)程;引入概率式準則來決定下輪迭代的目標搜索鄰域。通過算法校準實驗分析,探索出合適的鄰域變更次序和溫度參數(shù)的計算方式。通過與CPLEX軟件、隱枚舉測試程序?qū)Ρ蕊@示,對于工件數(shù)不超過30的算例,校準后所提算法求得最優(yōu)解的耗用時間更少。通過與遺傳算法、模擬退火算法、和聲搜索3種對比算法在工件數(shù)不少于100的算例上進行對比發(fā)現(xiàn),所提算法經(jīng)校準后,在求解質(zhì)量和解的魯棒性上均具有顯著優(yōu)勢。 

【文章來源】：計算機集成制造系統(tǒng). 2019,25(05)北大核心

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

【部分圖文】：

VN5算法的基本流幸鑒

第５期劉樂等：雙機流水車間外包與調(diào)度聯(lián)合優(yōu)化問題的混合變鄰域搜索算法疊（即不存在統(tǒng)計意義上的顯著差異），但在指標ＲＰＤ的均值比較中，ｅｘＯ＆Ｉ→ｉｎｓＯ２Ｉ→ｉｎｓＩ２Ｏ還是以微弱優(yōu)勢勝出�？梢姡澹希Γ伞椋睿螅希玻伞椋睿螅桑玻细m宜作為ＨＶＮＳ算法中的鄰域變更次序。事實上，鄰域的變更次序在一定程度上取決于各鄰域結(jié)構(gòu)的內(nèi)存使用量［３６］，鄰域結(jié)構(gòu)對內(nèi)存的消耗量越大，該鄰域?qū)?yōu)化性質(zhì)的利用越充分，對其內(nèi)部解的搜索質(zhì)量越高，相同“抖動”次數(shù)下搜索到更高質(zhì)量鄰近解的幾率就越大。由于無需對新的內(nèi)部工件集重新排序，鄰域ｉｎｓＩ２Ｏ的內(nèi)存使用量最少。另外，兩種鄰域都需對新的內(nèi)部工件集按照Ｊｏｈｎｓｏｎ規(guī)則重新排序，但就對內(nèi)存的消耗而言，鄰域ｅｘＯ＆Ｉ比ｉｎｓＯ２Ｉ更大。因此，鄰域ｅｘＯ＆Ｉ應(yīng)以相對更高的概率成為下輪迭代的目標搜索鄰域。在ＢＶＮＳ變體算法中，Ｎ１成為下輪迭代的目標鄰域的可能性最高，Ｎ２次之，Ｎηｍａｘ成為下輪迭代的目標鄰域的可能性最低，這也就從理論上解釋了ｅｘＯ＆Ｉ→ｉｎｓＯ２Ｉ→ｉｎｓＩ２Ｏ作為ＨＶＮＳ算法中鄰域變更次序的合理性。在校準后的ＨＶＮＳ算法中，確定鄰域變更次序為ｅｘＯ＆Ｉ→ｉｎｓＯ２Ｉ→ｉｎｓＩ２Ｏ，λ的取值為０．１。４．３求解精度實驗分析下面以相對求解精度（ＲＳＡ）為量化指標分析校準后ＨＶＮＳ算法在小規(guī)模ＴＦＳＯＳＰＩＭ＋ＴＯＣ算例上的優(yōu)化精度表現(xiàn)。對于每個算例，校準后ＨＶＮＳ算

第５期劉樂等：雙機流水車間外包與調(diào)度聯(lián)合優(yōu)化問題的混合變鄰域搜索算法疊（即不存在統(tǒng)計意義上的顯著差異），但在指標ＲＰＤ的均值比較中，ｅｘＯ＆Ｉ→ｉｎｓＯ２Ｉ→ｉｎｓＩ２Ｏ還是以微弱優(yōu)勢勝出�？梢�，ｅｘＯ＆Ｉ→ｉｎｓＯ２Ｉ→ｉｎ－ｓＩ２Ｏ更適宜作為ＨＶＮＳ算法中的鄰域變更次序。事實上，鄰域的變更次序在一定程度上取決于各鄰域結(jié)構(gòu)的內(nèi)存使用量［３６］，鄰域結(jié)構(gòu)對內(nèi)存的消耗量越大，該鄰域?qū)?yōu)化性質(zhì)的利用越充分，對其內(nèi)部解的搜索質(zhì)量越高，相同“抖動”次數(shù)下搜索到更高質(zhì)量鄰近解的幾率就越大。由于無需對新的內(nèi)部工件集重新排序，鄰域ｉｎｓＩ２Ｏ的內(nèi)存使用量最少。另外，兩種鄰域都需對新的內(nèi)部工件集按照Ｊｏｈｎｓｏｎ規(guī)則重新排序，但就對內(nèi)存的消耗而言，鄰域ｅｘＯ＆Ｉ比ｉｎｓＯ２Ｉ更大。因此，鄰域ｅｘＯ＆Ｉ應(yīng)以相對更高的概率成為下輪迭代的目標搜索鄰域。在ＢＶＮＳ變體算法中，Ｎ１成為下輪迭代的目標鄰域的可能性最高，Ｎ２次之，Ｎηｍａｘ成為下輪迭代的目標鄰域的可能性最低，這也就從理論上解釋了ｅｘＯ＆Ｉ→ｉｎｓＯ２Ｉ→ｉｎｓＩ２Ｏ作為ＨＶＮＳ算法中鄰域變更次序的合理性。在校準后的ＨＶＮＳ算法中，確定鄰域變更次序為ｅｘＯ＆Ｉ→ｉｎｓＯ２Ｉ→ｉｎｓＩ２Ｏ，λ的取值為０．１。４．３求解精度實驗分析下面以相對求解精度（ＲＳＡ）為量化指標分析校準后ＨＶＮＳ算法在小規(guī)模ＴＦＳＯＳＰＩＭ＋ＴＯＣ算例上的優(yōu)化精度表現(xiàn)。對于每個算例，校準后ＨＶＮＳ算

【參考文獻】：
期刊論文
[1]單機單轉(zhuǎn)包商調(diào)度與外包聯(lián)合優(yōu)化問題的改進啟發(fā)式算法[J]. 劉樂.  運籌與管理. 2017(11)
[2]帶轉(zhuǎn)包選項的自由作業(yè)排序[J]. 陳榮軍,唐國春.  數(shù)學進展. 2017(02)
[3]可轉(zhuǎn)包兩臺流水作業(yè)機排序的近似算法[J]. 陳光亭,陳蕾,張安,陳永.  運籌學學報. 2016(04)
[4]基于自適應(yīng)變鄰域搜索算法的一類混合流水車間調(diào)度問題[J]. 李坤,徐錚,田慧欣.  系統(tǒng)工程. 2015(11)
[5]具有外包選擇的無等待流水線干擾修復模型[J]. 薄洪光,張鑫,潘裕韜.  系統(tǒng)管理學報. 2015(04)
[6]可轉(zhuǎn)包的兩機自由作業(yè)排序問題(英文)[J]. 陳榮軍,唐國春.  數(shù)學進展. 2014(06)
[7]求解作業(yè)車間JIT調(diào)度問題的VNS/MP混合算法[J]. 楊宏安,齊亮亮,李錦遠,王宏浩.  計算機集成制造系統(tǒng). 2014(02)



本文編號：2993545