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

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

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

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

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ù)響應值及排名水平參數(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ù),計算結果,均值

同工廠數(shù)量下 NEH2 以及 DNEH+Dipak 計算結果 95%置信區(qū)間olm’s procedure 檢驗：不同初始方法下的 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

測試用例,比較算法