動態(tài)制造系統(tǒng)生產(chǎn)計劃與調(diào)度協(xié)同優(yōu)化

王艷紅 于 寧 蔡 明 邢大偉

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

0 引言

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

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

1 問題的描述

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

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

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

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

(1)

(2)

(3)

(4)

(5)

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

計劃模型的約束函數(shù)考慮庫存平衡約束，把生產(chǎn)能力和工序順序的約束以及單機(jī)加工能力約束結(jié)合到模型中?；镜膸齑嫫胶夥匠虨?/p>

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

(6)

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

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

(7)

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

能力約束不等式為

(8)

式中，hit為調(diào)整時間。

在計劃制定時，盡可能安排工件成批生產(chǎn)，減少準(zhǔn)備時間，以獲得設(shè)備最大利用率以保證零件的準(zhǔn)時完工，從而達(dá)到預(yù)定的目標(biāo)。

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

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

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

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

圖1 集成策略Fig.1 Integration strategy

2.2 滾動重調(diào)度策略

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

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

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

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

2.3 優(yōu)化算法

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

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

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

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

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

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

3 仿真研究與分析

3.1 仿真算例

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

表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臺加工機(jī)器的加工時間為x，h；括號內(nèi)的是備選加工機(jī)器。

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

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

圖4 收斂曲線Fig.4 Convergent curve

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

表2 基準(zhǔn)數(shù)據(jù)測試仿真結(jié)果對比

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

表3 運行結(jié)果對比

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

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

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

4 結(jié)論

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

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

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

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