王艷紅 于 寧 蔡 明 邢大偉

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

0 引言

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

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

1 問題的描述

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

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

“動靜聯(lián)盟式”計劃與調度總費用H為

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

(1)

(2)

(3)

(4)

(5)

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

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

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為調整時間。

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

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

2 協(xié)同優(yōu)化策略

2.1 閉環(huán)集成策略

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

圖1 集成策略Fig.1 Integration strategy

2.2 滾動重調度策略

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

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

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

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

2.3 優(yōu)化算法

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

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

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

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

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

圖2 動態(tài)調整機制策略Fig.2 Dynamic adjustment mechanism strategy

3 仿真研究與分析

3.1 仿真算例

假定訂單有6個工件、4臺機床，每個工件有4道工序，且這些工件必須按照規(guī)則進行加工，各工件、各工序在機器Mi上所需作業(yè)時間如表1所示，考慮到動態(tài)加工包含多個方面的情況，這里為了簡化問題，將各費用所占權重設為1，只考慮動態(tài)加工下的機器故障問題。

表1各工件各工序所需作業(yè)時間表

Tab.1Timetablerequiredfortheworkofeachworkpiece

工件號工序1工序2工序3工序413/M18/M24/M32/M426/M25/M13/M32/M431/M47/M32/M24/M144/M36/M43/M13/M2( M1)54/M25/M33/M42/M162/M34/M43/M12/M2( M4)

注：x/Mi表示第i臺加工機器的加工時間為x，h；括號內的是備選加工機器。

3.2 靜態(tài)優(yōu)化仿真

圖3 加工甘特圖Fig.3 Processing Gantt chart

圖4 收斂曲線Fig.4 Convergent curve

為了驗證所提出算法的有效性和優(yōu)越性，用基準數(shù)據作為測試例，將蟻群算法與遺傳算法的混合算法(下文簡稱混合算法)同遺傳算法進行對比，結果如表2所示。

表2 基準數(shù)據測試仿真結果對比

同時在同一標準參數(shù)下對同種情況進行多次仿真，得到了最優(yōu)解和最優(yōu)解均值，見表3。

表3 運行結果對比

3.3 動態(tài)優(yōu)化仿真

為驗證動態(tài)環(huán)境下重調度的可行性，假設加工進行到某一時刻，機器發(fā)生故障，動態(tài)控制平衡機制會在故障點，根據滾動調度傳達動態(tài)實時加工信息，以在不改變最小加工時間的情況下減少總費用，重新進行計劃信息調整和調度重組。圖5為機器2在某一時刻發(fā)生故障時，加工信息和調度重新調整重組的甘特圖。

圖5 故障發(fā)生后調度重組的甘特圖Fig.5 Gantt chart of scheduling reconfiguration after failure

4 結論

(1)針對動態(tài)車間的生產計劃與調度問題，建立了一種“聯(lián)盟協(xié)作”模型，可根據實際生產模式設置不同需求費用所占權重。

(2)在集成策略上設計了計劃與調度互相傳遞信息的閉環(huán)響應模式，并提出滾動調度和預測調度相結合的策略，使加工計劃與調度能根據返回的有效動態(tài)信息進行更改，避免頻繁調整。

(3)通過實例仿真，對計劃與調度策略進行分析，并對某一時刻機器故障對系統(tǒng)調整的影響進行驗證，得出重調度策略的計算時間和仿真結果。

(4)通過用不同算法對基準算例進行仿真，在不同目標情況下進行對比，驗證了所提出算法的有效性和優(yōu)越性。