基于元啟發(fā)式的分布式車間調(diào)度方法研究

發(fā)布時(shí)間：2020-11-21 20:44

　　隨著現(xiàn)今市場和制造全球化趨勢,為應(yīng)對瞬息萬變的市場需求,生產(chǎn)車間已經(jīng)由單一車間向多車間轉(zhuǎn)變,從集中式結(jié)構(gòu)變?yōu)榉稚⑹浇Y(jié)構(gòu),形成了分布式車間生產(chǎn)模式。車間調(diào)度在分布式車間生產(chǎn)中至關(guān)重要,有效的調(diào)度算法和優(yōu)化技術(shù)能夠優(yōu)化生產(chǎn)系統(tǒng)流程,提高生產(chǎn)效率和經(jīng)濟(jì)效益。分布式車間調(diào)度問題相對單車間調(diào)度問題更加復(fù)雜,尤其是調(diào)度方法的研究,已經(jīng)引起了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注。許多分布式車間調(diào)度問題是NP(non-deterministic polynomial)難問題,傳統(tǒng)的調(diào)度方法如分支定界法、數(shù)學(xué)規(guī)劃方法、啟發(fā)式規(guī)則,都很難獲取問題的最優(yōu)解或者計(jì)算量太大。元啟發(fā)式算法(meta-heuristics)不依賴求解問題,通過全局和局部搜索能夠獲得較為滿意的解,是求解調(diào)度問題的有效方法,其研究成果具有重要的學(xué)術(shù)意義和應(yīng)用價(jià)值。本文深入研究了制造系統(tǒng)中廣泛存在的零等待、零空閑、交貨期等加工約束,提出了基于改進(jìn)的教學(xué)優(yōu)化算法以及Memetic算法的調(diào)度方法。并將相關(guān)成果擴(kuò)展到分布式調(diào)度車間調(diào)度中,對分布式零等待流水車間調(diào)度以及帶有裝配過程的分布式零空閑流水車間調(diào)度問題進(jìn)行了求解。主要研究工作如下:(1)針對教學(xué)優(yōu)化算法存在的不足,從概率理論的角度出發(fā),提出了基于概率分布模型的協(xié)同學(xué)習(xí)機(jī)制,將概率模型嵌入教授或者學(xué)習(xí)階段,即將概率分布作為老師或者信息交流平臺。針對零等待流水車間調(diào)度問題,提出了一種基于概率學(xué)習(xí)階段的離散教學(xué)優(yōu)化算法(HDTPL)。該算法通過對工件序列鄰域變換來模擬教授過程,同時(shí)采用概率模型作為知識收集的平臺,每個(gè)學(xué)生通過該平臺交流學(xué)習(xí),實(shí)現(xiàn)了學(xué)生之間的自學(xué)習(xí)。基于標(biāo)準(zhǔn)測試用例的測試結(jié)果驗(yàn)證了HDTPL有效性和優(yōu)越性。(2)研究了分布式零等待流水車間調(diào)度問題,建立了該問題的混合整數(shù)規(guī)劃模型以及提出了若干鄰域變換的加速算法,有效的減少了計(jì)算的復(fù)雜度。針對分布式零等待流水車間調(diào)度問題,結(jié)合變鄰域搜索、變鄰域下降搜索、隨機(jī)變鄰域提出了三種迭代貪婪算法IG_VNS、IG_VND、IG_RNS。大量仿真實(shí)驗(yàn),表明所提出的算法求解效果優(yōu)于當(dāng)前同領(lǐng)域其他分布式車間調(diào)度算法。(3)研究了帶有準(zhǔn)備時(shí)間多目標(biāo)分布式零等待流水車間調(diào)度問題,考慮了最大完成時(shí)間和總延遲時(shí)間為優(yōu)化目標(biāo)。在每臺機(jī)器上,從當(dāng)前工件加工完成到下一工件開始加工前存在準(zhǔn)備時(shí)間。提出了一種基于Pareto非支配解的分布估計(jì)算法求解上述問題。建立了三種概率模型,即工件在空工廠的概率、兩個(gè)工件在同一工廠的概率、兩個(gè)工件相鄰的概率。在該模型的基礎(chǔ)上,提出了一種基于參考模板的采樣算法來產(chǎn)生后代,并對檔案集以及后代個(gè)體進(jìn)行了多目標(biāo)局部搜索。實(shí)驗(yàn)表明,所提出的算法優(yōu)于其他相關(guān)算法,并且所得到的解具有良好的分布性和逼近性。(4)針對零空閑流水車間調(diào)度問題,提出一種基于直方圖模型的Memetic算法(MANEH)。MANEH考慮了工件的順序以及相似工件塊,采用基于混合邊和點(diǎn)直方圖模型的隨機(jī)采樣交叉方式,避免工件選擇的盲目性。在局部搜索部分,在變鄰域搜索中加入了隨機(jī)參考鄰域搜索以及基于模擬退火的接受準(zhǔn)則,使得局部搜索能力進(jìn)一步提高�；诖笠�(guī)模測試用例的實(shí)驗(yàn)驗(yàn)證了MANEH優(yōu)越性。(5)針對帶有交貨期約束的零空閑流水車間調(diào)度問題,提出一種基于概率教授的離散教學(xué)優(yōu)化算法(HDTLM)。在教授階段,根據(jù)優(yōu)秀學(xué)生個(gè)體和教師構(gòu)建概率模型,對概率模型采樣生成一系列位置序列;采用共有序列的概念來代替原始教學(xué)優(yōu)化算法平均個(gè)體的概念,根據(jù)位置序列和共有序列來產(chǎn)生新個(gè)體。在學(xué)習(xí)階段,根據(jù)學(xué)生的學(xué)習(xí)水平,將學(xué)生分為三個(gè)層次,從上到下傳遞知識。通過與當(dāng)前較為先進(jìn)的幾種算法對比,驗(yàn)證了HDTLM的優(yōu)越性。(6)研究了帶有裝配過程的分布式零空閑流水車間調(diào)度問題。針對已有工件分配規(guī)則的不足,提出了一種工件分配規(guī)則,使得同一產(chǎn)品的相關(guān)工件加工順序盡可能緊湊,同時(shí)使得裝配過程盡早開始,減少裝配等待時(shí)間。針對帶有裝配過程的分布式零空閑車間調(diào)度問題,提出混合迭代局部搜索(HILS)算法和混合變鄰域搜索(HVNS)算法。通過求解標(biāo)準(zhǔn)測試用例,驗(yàn)證了HILS和HVNS的性能顯著優(yōu)于同領(lǐng)域同其他相關(guān)算法。
【學(xué)位單位】：南京航空航天大學(xué)
【學(xué)位級別】：博士
【學(xué)位年份】：2018
【中圖分類】：TP18;TH186
【部分圖文】：

趨勢圖,算法性能,參數(shù)α,響應(yīng)值

3 1 3 3 3 3 3 3 3 0.344 0.182 0.188 1.472 0.801 0.514 0.584 1 4 4 4 4 4 4 4 0.435 0.195 0.169 1.616 0.855 0.541 0.635 2 1 2 3 4 1 1 4 0.302 0.192 0.157 1.138 0.563 0.402 0.456 2 2 1 4 3 4 3 3 0.343 0.202 0.210 1.515 0.805 0.574 0.607 2 3 4 1 2 3 2 1 0.346 0.229 0.259 1.198 0.753 0.738 0.588 2 4 3 2 1 2 4 2 0.479 0.247 0.283 1.680 0.919 0.777 0.739 3 1 3 2 2 4 2 2 0.349 0.177 0.195 1.483 0.819 0.641 0.6110 3 2 4 3 1 2 3 1 0.463 0.283 0.337 1.339 0.907 0.860 0.6911 3 3 1 4 3 1 4 4 0.455 0.178 0.221 1.644 0.931 0.605 0.6712 3 4 2 1 4 3 1 3 0.319 0.194 0.164 1.247 0.699 0.479 0.5113 4 1 4 2 1 3 1 3 0.406 0.195 0.188 1.751 0.941 0.624 0.6814 4 2 3 4 3 2 2 2 0.316 0.190 0.233 1.280 0.597 0.608 0.5315 4 3 1 1 4 1 4 1 0.437 0.333 0.300 1.124 0.816 0.803 0.6316 4 4 2 3 2 4 3 4 0.528 0.226 0.199 1.886 1.151 0.754 0.79表 2.3 各參數(shù)響應(yīng)值及排名水平參數(shù)α γ ω TFCr ξ Rt Np1 0.586 0.684 0.636 0.587 0.698 0.588 0.561 0.6272 0.596 0.537 0.577 0.684 0.632 0.626 0.569 0.6053 0.625 0.620 0.731 0.633 0.600 0.593 0.670 0.5984 0.633 0.669 0.651 0.613 0.562 0.661 0.669 0.639極差 0.023 0.066 0.063 0.041 0.058 0.034 0.060 0.019等級 7 1 2 5 4 6 3 8

置信區(qū)間,工廠數(shù),計(jì)算結(jié)果,均值

同工廠數(shù)量下 NEH2 以及 DNEH+Dipak 計(jì)算結(jié)果 95%置信區(qū)間olm’s procedure 檢驗(yàn)：不同初始方法下的 IG_VNS、IG_VND、H0p α/(k-i*+1) Holm’s pDNEH=NEH2 0.0000 0.2503 RDNEH=Random 0.0000 0.0500 RDNEH=NEH2 0.0000 0.2503 RDNEH=Random 0.0000 0.0500 RDNEH=NEH2 0.0000 0.2503 RDNEH=Random 0.0000 0.0500 R0.80.70.60.5ARPDIG_RNS IG_VND IG_VNS

測試用例,比較算法