動態制造系統生產計劃與調度協同優化

2018-12-11 10:10:28王艷紅邢大偉

中國機械工程 2018年22期

王艷紅于寧蔡明邢大偉

1.沈陽工業大學管理學院，沈陽，1108702.沈陽工業大學信息科學與工程學院，沈陽，1108703.東北大學機械工程與自動化學院，沈陽，110819

0 引言

生產計劃與調度是企業生產管理的核心內容，是實現制造業生產高效率、高柔性和高可靠性的關鍵[1]。科學的生產計劃可以充分發揮企業的生產能力，充分滿足市場需求；高效的調度算法可以提高生產效益和資源利用率，從而增強企業的競爭能力[2]。車間生產計劃(shop production planning，SPP)主要解決生產什么、生產多少的問題，車間生產調度(shop production scheduling，SPS)則關注何時開始生產、在哪兒生產的問題[3]。隨著市場競爭的加劇以及客戶訂單需求的多樣化，傳統的生產方式已難以適應現代化生產的需求，且多數企業普遍存在著“同工異地”加工方式，這使得多車間、多品種、小批量的作業模式成為主流生產方式。實際生產過程中，生產系統常會出現很多動態不確定事件(機器異常故障、緊急訂單等)，這勢必會產生大量的擾動事件，結果將是實際生產活動永遠不會與計劃完全匹配，即使是再周密的生產計劃都可能無法獲得可行的生產調度[4]。

計劃調度方案的頻繁調整是為了使系統的生產計劃、調度與生產活動能夠產生一致性，動態制造環境的特點使得方案的調整已不能再局限于生產計劃或調度之內，無論在靜態規劃過程，還是在動態生產過程，都應保持生產計劃與調度具有較高的可靠性、耦合性和實時的協商合作能力，以便能高效地動態控制和調節系統[5]。因此對動態車間生產計劃與調度協同優化的研究具有重要的意義。現階段，很多學者針對不同的作業環境，建立了包含計劃與調度的混合集成模型。張潔等[6-7]以加工時間為目標構建了調度模型；WANG等[8]為生產設置有限周期，通過定義決策變量，考慮機器的容量和客戶的需求，提出了混合整數規劃模型；YANG等[9]根據調度規則技術，建立了多生產線的預制生產流程調度模型；GEIGER等[10]在不確定環境下，建立生產計劃與調度的數據庫和規則庫，進行分層優化。這類模型大多通過一些新的混合算法及分解方法進行求解，例如，WEN等[11]用一種包括隨機模擬技術、神經網絡和遺傳算法的混合智能算法，對集成的再制造生產計劃和調度系統進行優化；ZHANG等[12]采用基于模擬的優化框架來解決重制造的工作選定的過程路徑優化問題；雷德明等[13]針對總能耗約束的柔性作業車間調度問題，設計了兩階段算法，提高了問題搜索能力。這些方法基本上都針對問題的特殊性構造求解。實際應用中，模型的建立往往要考慮多個相互沖突的目標，一個多目標問題可以有很多個候選解。如何選出候選解并確定一個最優的折中方案是集成優化的核心，這就需要在給出計劃和調度方案的同時，對其進行優化和改進，在大多數動態制造過程中更需要對計劃或調度進行重組。本文針對動態制造車間，建立了“動靜聯盟式”計劃與調度模型，以確定動態分布環境下的生產計劃情況，同時在生產計劃中融合滾動調度，調度與計劃形成“閉環響應模式”，用動態約束平衡的混合算法對生產計劃與調度進行協同優化，并用實例驗證了閉環響應下重調度的有效實施。

1 問題的描述

在動態制造環境下，為實現車間加工生產的高效性，以計劃層為起點，用上層決策結果控制調度層的優化方案，再將調度層方案返回給計劃層，從而建立適于批量生產的集成模型。考慮到調度目標的多樣性和不確定性，在制定生產計劃時，不但要考慮生產能力的約束，而且要將滾動的實時調度結果作為約束條件結合到模型中，以保證當動態問題產生時，生產計劃與調度可以協同優化改變。根據調節機制，當動態情況發生時，需要根據能力約束和目標值，盡量在不改變原期望結果的情況下快速尋找最優調整策略，此時平衡機制就起到很好的作用。車間生產計劃根據蟻群算法在分布狀態下搜索并快速收斂從而優化。由于生產計劃與調度的目標往往具有不同的屬性，單目標規劃往往難以達到同時優化的目的，因此采用多約束、多目標來描述生產計劃與調度的優化模型更為合理。

在多品種、小批量的動態制造環境下，將生產分成T個周期，生產車間有m臺設備、n個工件，工件i含k道工序，能完成每道工序加工任務的機器可能有多臺，工件一旦在機器上加工就不中斷。在t周期內，已知工件i的需求量dit、庫存量rit。動態制造車間的首要任務是根據訂單需求分解訂單，根據車間生產能力Wit和庫存量rit去制定動靜結合的主生產計劃和短期生產計劃，同時考慮動靜態調度調整，要求完成時間最小。

“動靜聯盟式”計劃與調度總費用H為

H=min(γH1+θH2+μH3+ωH4)

(1)

(2)

(3)

(4)

(5)

式中，γ、θ、μ、ω為實際車間加工生產中各方面所占的權重；H1為當前協同車間批量生產的制造費用；H2為延期的懲罰費用；H3為庫存費用；H4為重調度費用；T為總周期數；Xit為工件的生產量；Cit為生產費用；Fit為成本費用；pit為加工時間；Pit為懲罰費用；Rit為庫存費用；sit為調整費用；Lit為重調度加工分配時間；Qit為重調度加工延遲時間；下標it表示第i個工件在第t個周期。

計劃模型的約束函數考慮庫存平衡約束，把生產能力和工序順序的約束以及單機加工能力約束結合到模型中。基本的庫存平衡方程為

ri(t-1)+Xit-dit=rit

(6)

同一工件不同工序間的加工順序約束為

Eikt-Sikt≤hit+Ei(k+1)t-Si(k+1)t

(7)

式中，Eikt為在t周期工件i的第k道工序加工完成的結束時間；Sikt為在t周期工件i的第k道工序開始加工時間。

能力約束不等式為

(8)

式中，hit為調整時間。

在計劃制定時，盡可能安排工件成批生產，減少準備時間，以獲得設備最大利用率以保證零件的準時完工，從而達到預定的目標。

另外，對訂單分解后的加工過程進行動態分析，用滾動調度來反饋控制調度和計劃的形成，直至達到動態加工需求結束為止，最終使所有工件的總完工時間最小。

2 協同優化策略

2.1 閉環集成策略

集成策略是將計劃與調度形成動態“閉環響應模式”。如圖1所示，將能力約束加到短期生產計劃及車間調度，再把調度約束與短期生產計劃結合起來，把加工順序約束與車間調度結合起來。約束后的短期生產計劃與生產調度互相傳遞信息，形成閉環控制。所有約束用數學語言描述并放在數學模型中，在約束條件中考慮完工時間，相當于建立一個跟時間有關的目標函數，這樣在動態制造生產中建立“動靜聯盟 (靜態動態生產結合) ”的關系，通過共享信息，實現信息的雙向流動，最終實現對生產系統的生產計劃與調度控制。

圖1 集成策略Fig.1 Integration strategy

2.2 滾動重調度策略

滾動重調度策略本質上是在車間調度過程中，收集和反饋實時信息，將反饋的信息作為新的目標約束，從而對計劃和調度進行調整。動態不確定情況下，具體規則如下：

(1)需求訂單改變時，在不增加庫存成本的前提下，根據以往生產的預測信息，將原有信息和預測信息融合作為新的約束，調度加工在最小調整費用的前提下形成重調度方案。

(2)在訂單不變的前提下，若某些工件完工時間提前或延遲，在盡量不改變最小完工時間的基礎上，在調度方案中調整交換工序，形成重調度方案。

(3)加工過程中，若加工機器發生故障，則需要將未加工工件或工序調整到其他機器上完成。首先盡可能少地更改現行調度方案，根據工件加工工序的可調整方案，考慮多個約束和完成時間，控制調度方案的調整范圍，以減小重調度方案帶來的目標值的改變。

2.3 優化算法

遺傳算法(genetic algorithm，GA)的快速全局搜索能力很強，但無法利用系統反饋的信息，導致求解效率較低。蟻群優化(ant colony optimization，ACO) 算法有較好的分布、全局收斂能力，通過累積的信息素更新，收斂于最優選擇。考慮到蟻群算法和遺傳算法的特點，將兩者混合，應用到多車間、多品種、多批量的作業模式中，使算法整體性能得到了改善。算法的主要思路是：

(1)當訂單需求發送到多車間、多機器上時，系統根據當前車間生產的能力約束，分配生產計劃到機器上。在已知各工件、各工序在機器上作業所需時間和規則的基礎上，將工件的加工工序作為上層染色體，將工件的加工機器作為下層染色體，最終形成雙層編碼的染色體，每一個雙層編碼的染色體對應一個調度方案，所形成的染色體為

全部工件完成時間越短，該染色體越好。種群通過交叉操作獲得新的染色體，通過變異獲得新的個體，實驗中，遺傳算法參數選取如下：選擇概率Pk=0.8，交叉概率Pc=0.8，變異概率Pm=0.3。

(2)動態情況(如機器故障)一旦發生，故障機器上原本加工的工件和工序都需要調整，此時需要根據能力約束和目標值，盡量在不延長加工生產的總完成時間的基礎上，快速尋找最優調整策略，平衡機制就起到了很好的作用，通過改變信息素增量的大小，使蟻群算法能在分布狀態下快速搜索并收斂。在實驗中，蟻群算法參數選取如下：循環次數N=100，螞蟻數量λ=100，信息素增量Q=100，信息素啟發因子α=1.5，期望啟發式因子β=5，信息素剩余量系數ρ=0.6。

因此本文采用混合遺傳蟻群算法，用遺傳算法判斷是否滿足終止條件，進一步判斷是否達到融合條件，并針對蟻群算法的揮發系數加入動態調整策略。蟻群算法使用的轉移規則(隨機比例規則)定義了螞蟻位于節點工件i經過第m次運動時運行到節點工件j的轉移概率Pijm。根據算法的局部最優傾向程度來動態調整揮發系數，從而避免算法早熟和局部停滯，其動態調整機制如圖2所示。