云制造生產模式下的生產調度研究

萬雨松，余開朝

（昆明理工大學機電工程學院，云南昆明 650093）

0 引言

我國各地區制造業水平差別巨大，制造資源分布極不均勻，并且存在著制造企業擁有很多制造資源，但由于沒有充足的制造任務致使其被閑置的現象，從而導致了制造資源的浪費［1］。針對該情況，并且考慮到《中國制造2025》戰略目標的需要，李伯虎院士［2］提出了云制造這一全新的生產模式。

云制造是源于工業4.0 概念的一種新的制造模式，其可采用網絡技術充分利用分散的生產資源。在云制造過程中，集中利用分散的制造資源合理安排各級生產計劃，為需要的客戶提供制造服務［3］。然而，云制造這種新型生產模式給生產調度提出了新問題：從整體生產的角度而言，需要實時和快速反應的調度方法可大大提升分散制造資源的利用率，但相應地在生成生產調度計劃時會存在效率問題。

目前學者們對于云制造的研究主要是考慮制造的服務屬性，如Vahedi 等［4］在參與云制造的工廠之間建立相關權重，并設置提交訂單客戶的偏好權重，以便更好地進行任務匹配；郭亮等［5］研究云制造不同任務層次的加工任務匹配，構建了相對應的優化任務匹配模型。但目前已有研究比較關心的是云制造的服務屬性，對于云制造模式下的生產相關部分的研究較少。

云制造調度問題面向的是多樣化的產品需要和眾多的柔性制造資源，因此如何更好地解決柔性作業車間調度問題（Flexible Job Shop Scheduling Problem，FJSP）是解決云制造調度問題的基礎［6］。FJSP 是在最典型的車間調度問題（Job Shop Scheduling Problem，JSP）和可選擇加工機器的基礎上擴展產生的問題［7］。對于一個制造資源中心，加工工件的多個工序都可在制造資源中心進行加工，并且每一個工序都有一個或多個機器選擇，這就是柔性車間調度問題。

目前對FJSP 的研究主要是如何求得高質量和更優的解。如Yazdani 等［8］提出一種混合整數線性規劃模型，并且結合進化算法最小化FJSP 的完工時間；Brucker 等［9］證明了FSSP 是一個NP-hard 問題，即問題可能的解會隨著問題規模的擴大而以爆炸般的速度增加。因此，精確方法在解決大規模柔性調度問題時效率不高，因其計算量很大。例如混合整數線性規劃的求解方式可構造數學模型并求取全部解，但相對應的是求解時間很長，所以很難處理和求解云制造模式下的大規模調度問題。

因此，元啟發式方法逐漸成為FJSP 最主要的研究方向。各種元啟發式方法如粒子群算法、遺傳算法、退火算法等被用于解決FJSP 問題。例如，Pezzella 等［10］使用優化的遺傳算法（Genetic Algorithm，GA）求解FJSP 問題，該算法使用不同策略生成初始種群、選擇個體并進行迭代搜索；代招等［11］在初始種群中利用混沌映射和反向學習策略提高初始種群質量，進而提高算法收斂速度；Huang 等［12］在交叉方法和變異方法基礎上對遺傳算法進行改進，在子代種群生成過程中采用新的自適應交叉和變異概率，大大提高了收斂速度；顧幸生等［13］使用博弈解集，在粒子群算法基礎上對種群迭代進行改進，將改進算法用于求解FJSP。

然而，常用于求解FJSSP 的元啟發式算法本身存在一定缺點，比如遺傳算法的編碼可能會出現不可行解的問題，需要增加剔除不可行解的步驟，導致計算量增加，并且因采用基于概率搜索的方式，所以在局部搜索時效率較低。粒子群算法在求解FJSP 離散組合問題時性能不佳，容易快速損失種群多樣性，迭代至局部最優的陷阱中。因此，將不同算法結合，充分發揮各自算法的優點也是常用的算法優化手段。Li 等［14］將具有良好全局搜索能力的遺傳算法與具有良好局部搜索能力的退火算法相結合，提出一種新的混合算法；Rohaninejad 等［15］針對FJSP，開發了一種將GA、粒子群算法（Particle Swarm Optimization，PSO）與局部搜索啟發式方法相結合的新型混合算法；Zhang 等［16］處理FJSP 時將可變鄰域搜索引入到GA 算法中，提升了求解質量，但是相應的算法運行時間大幅增加。

云制造的概念有一部分源自于云計算，在研究過程中，很多學者主要研究制造架構，針對制造生產部分的研究較少。因此，本文主要研究云制造模式在制造層面的生產情況，對云制造環境下的FJSP 問題需要考慮求解速度和質量的問題，進一步優化求解的元啟發式算法，以優化云制造環境下的生產能力。為了在保證算法搜索性能的基礎上加快求解速度，本文基于候鳥算法，利用分享鄰域解的機制提升尋優速度；使用矩陣編碼方式，省去了染色體修復步驟；采用3 種種群初始化策略，以保證種群質量和解空間分布，有助于快速搜索到最優解附近；引入變鄰域搜索，但是只有優秀個體才會進行此搜索，在保證搜索能力的同時，可減少算法運算時間。

1 問題模型

1.1 云制造模式與調度框架

如圖1 所示，在云調度生產模式中，個人或企業用戶根據自身需要提交制造需求訂單，生產訂單會在云制造平臺上拆分成不同的加工部件生產任務，然后這些任務會根據企業的制造能力進行匹配調度。生產任務的分配結果會返送給客戶和企業，企業再將生產任務拆分成工序，進行柔性生產調度，并將調度結果下達至生產一線進行生產。

Fig.1 Cloud manufacturing production mode圖1 云制造生產模式

針對云制造模式下的生產任務排序與機器選擇的組合問題特性，找到合理的求解方法以充分利用企業的制造能力是有必要的。云制造模式下的柔性調度問題計算適合采用元啟發式方法，即在一定時間內獲得可接受的調度方案，而不是耗費大量計算時間獲得最優解。

根據上文對云制造模式運行的分析，本文提出如圖2所示的云制造模式調度框架。第一步是企業對自身已有的生產任務進行調度，并根據調度方案分析設備使用情況，然后將獲得的剩余空閑生產能力發送到云制造平臺上；第二步是云制造平臺對用戶提交的制造任務進行分析，將相應的制造任務與空閑制造資源進行匹配，使制造需求方與企業都能滿意；第三步是企業接受訂單后進行相應的云制造調度，看得到的調度方案是否符合要求，如果可以接受，則調度方案轉入生產車間進行執行。

Fig.2 Cloud manufacturing mode scheduling framework圖2 云制造模式調度框架

在云制造模式下，生產調度需要考慮的不僅僅是工序的加工順序排列和工序選擇哪個加工設備，而且需要適應整個生產模式的要求。如企業需要制定自身的生產任務計劃，然后需要利用空閑的制造資源接收云平臺的生產任務，這就要平衡兩組任務使用機器時可能導致的加工時間沖突問題。在常規的調度問題基礎上，云制造模式下的調度問題還引入了效率要求，所以問題的構成與求解更為復雜。

1.2 云制造模式下FJSP問題模型構建

為更好地描述與解決柔性作業車間調度問題，用以下參數和約束式對FJSP 問題構建相應數學模型，如表1所示。

判斷參數：

Table 1 Flexible production scheduling model parameters表1 柔性生產調度模型參數

要符合云調度生產模型，就有一定的限制條件，具體如下：

（1）工序約束。

式（1）表示對于每個工件，自身工序的加工順序是固定的，不可更換。

（2）加工設備約束。

式（2）表示在同一時間，一個加工設備上只能進行一個工序的加工。

（3）加工過程約束。

式（3）表示任意加工工序在加工時不能中斷。

在上述約束之外，考慮到實際情況，還有一些其他約束：在初始時間，需要加工的工件和對應的加工機器都已準備就緒，所有參數均為非負數。

本文采用的求解指標是最大完工時間最小指標，也是最常用的調度性能指標，具體如式（4）所示。

對一組調度計劃來說，就是要求得使時間最長、Ti值最小的調度方案，并且求解方法可擴展成多目標優化求解，也可引入生產平衡率、加工成本等其他生產指標。因此，本文對問題的研究主要基于最大完工時間最小指標，并將本文算法的求解結果與目前國內外比較典型的算法結果進行比較，以衡量算法性能。由于候鳥算法的通用性，尤其是其領飛鳥的設計方案，使得該算法不會受到問題約束條件的影響。

2 候鳥算法

MBO（Migratory Bird Optimization Algorithm）算法是一種利用共享搜索解機制的群體元啟發式算法。該方法是基于候鳥在飛行中保持V 型編隊以節省能量消耗的原理，由Duman 等［17］在2012 年首次提出，用于解決二次分配優化問題。MBO 算法主要有以下幾個步驟：種群初始化、領飛鳥進化更新最優值、跟飛鳥進化更新解、更換領飛鳥，通過這樣的循環找到最優解。

初始候鳥群（也即問題可能的解）組成一個V 形編隊，包括一個先導候鳥和一些跟隨候鳥。如圖3 所示，在解決方案群中，為每個候鳥搜索鄰域（即在每個解決方案附近生成數量有限的解決方案），評估每個候鳥的相鄰解決方案。如果有更好的優化解，則該候鳥將被替換為更好的解決方案。

Fig.3 Schematic diagram of excellent neighborhood sharing圖3 優秀鄰域分享示意圖

算法使用分享鄰域解來模擬前鳥給予跟隨鳥的抬升力，即每個跟隨鳥（主要解決方案）都可以在其前鳥共享的解決方案幫助下改進自身解。因此，除領飛鳥外，群體的其他跟飛鳥都有機會被其前面候鳥的鄰域加以改進。如圖4 所示，算法搜索多次后，領飛鳥由于搜索過久，產生更優解的可能性變小，因此移動到隊伍后列，選取后續的跟飛鳥成為新的領飛鳥繼續搜索。然后在后續搜索過程中繼續同樣的替換過程，直到達到迭代次數。最后，引入群體最優解作為MBO 算法的解。

Fig.4 Schematic diagram of replacing the collar bird圖4 更換領飛鳥示意圖

分析候鳥算法的過程，單個候鳥的不同鄰域搜索和進化策略能保證全局分散的搜索能力，共享鄰域解能保證單個個體能通過整體的較優解進化，保證算法集中的搜索性能。MBO 算法在局部搜索的能力是比較優異的。

對于啟發式算法而言，種群收斂不是越快越好。若種群收斂太快，會在全局搜索不足的情況下過早地聚集在局部解，陷入局部最優。MBO 算法將前面個體的鄰域解分享給后面的多個跟隨個體，從一方面來看，優化了種群的整體性能，但從另一方面來看，更多候鳥進入到前鳥附近，造成候鳥的種群多樣性損失嚴重，容易陷入局部最優的陷阱。所以需要對MBO 算法進行相應的優化改進，以提升搜索性能。

2.1 編碼／解碼方案

柔性生產調度會有多種實際生產上的約束，在算法搜索過程中可能會產生不可行解的情況，所以本文使用矩陣編碼的方式進行編碼：云制造情況下收到n個工件的制造訂單，每個工件有m道工序需要加工，每道工序有m（jj=1，2，…，m）臺可選擇的柔性機器，初始化種群Xn×m的元素Xij采用隨機實數生成。式中，i=1，2，…，n，j=1，2，…，m。初始化的候鳥是一個問題的解，對于某個解Xi，整數部分表示待制造元件的柔性機器號，小數部分表示在機器上的加工順序，優先度按照小數部分降序排列。這種編碼方式是將每個矩陣當成一個候鳥，也即一個調度方案。采用該方式不僅能提高計算速度，而且能保證后續搜索、進化不會出現不可行解，節省了計算時間。

解碼是對編碼的逆向操作，根據得到的矩陣給出合理的柔性調度方案，例如給出一個初始種群X：

就第一列而言，觀察整數部分可得：工件J1和J2是在機器一（整數部分）上加工，機器一先加工O11，再加工O21（小數部分升序順序）；工件J3、J4是在機器二上加工，機器二先加工O31，再加工O4（1小數部分升序順序）。根據各個工件的加工時間，最后給出一個可行的柔性調度方案。

2.2 種群初始化方案

類似于其他的群體智能算法，良好的種群初始化方法對于豐富種群多樣性和提高搜索速度是很有幫助的。生成的初始候鳥種群需要保證質量和多樣性，即初始解決方案覆蓋的解空間很大，并且接近最優解。為了滿足這兩個要求，本文用以下3 種方式生成初始解，并且為保證多樣性和質量進行了比例劃分，具體如下：

（1）隨機生成方式。為保證群體的多樣性，使用隨機生成方法生成60%的初始候鳥，即對于機器選擇和操作序列，都是隨機生成矩陣序列。

（2）優先機器的選擇方法。首先是第一個工序和下一個工序隨機選擇加工機器，然后記錄每臺機器的操作時間，在下一個工序Oij選擇機器時，將可選擇機器之前的加工時間與Oij的加工時間相加，選擇總加工時間最短的機器，然后繼續下一個工序的機器選擇，直到所有工序都選擇了對應的加工機器。使用優先機器的選擇方法生成20%的初始候鳥，使用該方法的優點是其可在算法初始階段使機器的工作時間盡量一致，從而更好地探索搜索空間，并考慮機器的工作負載平衡。

（3）優先工件的選擇方法。對工件的可選擇機器進行隨機選擇，在機器的加工順序上，優先加工剩余工序總時長最長工件的一個工序，然后再以同樣的規則選擇下一個工件進行工序加工。使用優先工件的選擇方法生成20%的初始候鳥，該方法的優點是可以搜索到令所有工件加工時間最大值盡可能小的解空間。

2.3 候鳥群進化

在MBO 算法中，領飛鳥是第一個開始搜索鄰域解的個體，然后如果有更好的解，則編碼矩陣更換為更好的解，這被稱為鳥群個體的進化，之后分享自身的優秀解給后續候鳥。這種機制就是模擬實際候鳥隊列給后續候鳥的抬升力，后續候鳥可在自身搜索的解和前鳥提供的解中進行選擇與進化，這就是候鳥群的進化。搜索解的方法主要是鄰域搜索，柔性調度和常規調度的主要區別在于多了機器選擇，本文主要采用以下4種鄰域搜索策略：

（1）機器隨機搜索。任意選擇一個工序，將其加工機器改成其他可加工的機器，即整數部分編碼改成其他，小數部分隨機選擇并且保證不重復。

（2）工序交換搜索。隨機將一個機器上的兩個工序交換（也即交換矩陣編碼的小數部分）。

（3）工序前移搜索。隨機選取一個機器上的任意兩個工序，將后面加工工件的加工順序插入到另一工件之前，即在插入的兩個工件的小數部分之間隨機生成一個小數。

（4）工序后移搜索。隨機選取一個機器上的任意兩個工序，將前面加工工件的加工順序插入到另一工件之后，即在插入的兩個工件的小數部分之間隨機生成一個小數。

然而，由于初始的鳥群順序是隨機生成的，一些具有優秀解的候鳥可能處于隊伍后方，難以給整個鳥群分享優秀解。因此，根據每個候鳥的適應度函數進行排序，解碼后加工時間最短的候鳥排第一，然后依次排序，最差的候鳥在最后，該方式能夠分享整個候鳥群的優秀解。同時考慮到MBO 算法的全局搜索能力，在迭代次數達到總搜索次數的一定比例時才開始排序，即設置巡回次數，從而避免種群多樣性的快速損失，在后期增強局部搜索能力。局部搜索策略如圖5所示。

Fig.5 Local search strategy圖5 局部搜索策略

2.4 變鄰域搜索

對于元啟發式算法，對最優解范圍的搜索能力是一個很重要的性能。變鄰域搜索算法（VNS）是由Mavrotas等［18］首先提出的用于對給出的算法解進行范圍尋優的局部搜索算法，主要原理是通過變動規則在某個較優解附近進行搜索，然后用更好的解替換掉原解。在改進的MBO算法中，變動規則主要是使用2.3 節的鄰域搜索策略，對MBO 搜索到的最優解按規則變動進行搜索。主要步驟如下：

步驟1：選取候鳥群進化的最優個體B 作為變鄰域搜索的起始值，搜索策略Smax=4，搜索次數Nmax=n。

步驟2：令S=1，從2.3 節的第S 個鄰域搜索策略開始對B 的矩陣編碼進行搜索變換，得到編碼矩陣B1。

步驟3：利用鄰域結構設定搜索次數對B1進行搜索，達到搜索次數后將其中的最優解設為B2。

步驟4：若B2是最優解，則將B2賦值給B，跳回步驟2繼續搜索；若B 是最優解，則S=2，繼續搜索，直到搜索策略S和搜索次數達到上限。

步驟5：選取最優解賦值給B，變鄰域搜索結束。

2.5 改進候鳥算法流程

通過上述改進，本文提出了改進候鳥算法（Improved Migratory Bird Optimization Algorithm，IM-MBO），主要流程如下：①按3 種策略進行種群初始化；②領飛鳥通過搜索產生鄰域解集U1；③如果產生的鄰域解優于領飛鳥，領飛鳥進化為更優解；④跟飛鳥搜索產生鄰域解集U2，然后將U1和U2中的最優解與跟飛鳥進行對比，取最優解；⑤選擇20%的個體進行變鄰域搜索；⑥如果達到巡回次數，進行領飛鳥替換；⑦如果達到終止條件，導出求出的最優解。具體流程如圖6所示。

3 實驗結果與分析

上述改進候鳥算法用MATLAB 語言實現，編寫程序并運行的計算機是Window10 版本，處理器為Intel（R）Core（TM）i5-6300HQ，CPU 主頻為2.3GHz，MATLAB 軟件型號為MATLAB R2019a。為了測試候鳥算法的性能，選用在柔性調度鄰域常用mk 系列的10 個實例［19］，加工工件數目范圍為10～20，工序數目范圍為5～15，機器數目范圍為4～15。元啟發式方法每次搜索得出的解可能不一樣，為消除運算中的隨機性，使最后的結果更具說服力，對每個案例運行10 次計算平均值。對比的目標一方面是遺傳（GA）算法和粒子群（PSO）算法這兩種常用于調度的元啟發式算法，另一方面是Gu 等［20］提出的IGA-AVNS 算法和顧幸生等［13］提出的博弈粒子群算法（Gaming PSO）。參考任彩樂等［21］的研究，算法參數設置鳥群個體為51，候鳥搜索自身鄰域解數目k=3，分享給跟隨鳥的鄰域解數目x=1，巡回次數S=10。求解結果如表2 所示。其中，n 代表需加工的工件數目，m 代表可供選擇的機器數目，w 代表總工序數目，S是MBO 算法求解10 次的最優解，Ave 是MBO 算法求解10次獲得最優解的平均值，T 是各個算法10 次求解的平均時間。

Fig.6 IM-MBO algorithm flow圖6 IM-MBO算法流程

對比表2 中數據得出如下結論：先對比在同一運算環境下的3 種算法，對比mk 案例的最優解和平均解，IMMBO 在搜索能力與搜索速度上優于GA 算法和PSO 算法，說明整體的搜索性能良好。在算法運算時間上，由于編碼方式不用染色體修復，加快了運算速度，IM-MBO 比GA 算法快34%，比PSO 算法快16%。對另外兩位學者的求解結果進行對比，因為運算環境不同，所以不對比運算速度。IM-MBO 在10 個問題上的最優解總體上略優于Gaming PSO 算法，且有部分問題的解優于IGA-AVNS 算法，總體而言在搜索能力上差距不大。考慮到本算法因考慮運算速度，犧牲了部分求解性能，這樣的結果是可以接受的。

下面用mk01 的案例進行說明，最終得出調度方案的甘特圖如圖7 所示（彩圖掃OSID 碼可見）。數字是加工工件的序號，橫軸方向是工序加工時間，縱軸是機器上的加工工序。

Fig.7 Optimal scheduling result of mk01 of MBO algorithm圖7 MBO算法mk01最優調度結果

在計算速度上，PSO 算法由于迭代方式簡單，搜索速度比PSO 算法略快，但是代價是易快速損失種群多樣性，求解性能降低。為進一步了解MBO 算法的性能，以mk10的基準問題為算例，將本文提出的IM-MBO 與經典的粒子群算法PSO、遺傳算法GA 進行收斂性能對比，3 種算法搜索過程如圖8 所示。由圖8 可知，3 種算法中，IM-MBO 約在60 次迭代時收斂到自身的最優解，最終求解值為215，并且搜索下降速度很快；PSO 初始收斂速度快，但是缺乏全局搜索能力，后期陷入局部最優，求解值為236；GA 收斂速度最慢，但是全局搜索能力尚可，所以初期慢于PSO，但后期不易陷入局部最優，求解值為229，優于PSO。

綜上，所得到的IM-MBO 算法在求解速度、收斂速度、全局搜索能力等方面都優于原有算法，可用于云制造模式下的柔性生產調度。

Table 2 Comparison of efficienty of main heuristic algorithms表2 主要啟發式算法效率對比

Fig.8 Solution process of the three algorithms圖8 3種算法求解過程

4 結語

為了解決云制造模式落地存在的問題，使制造產業通過云制造模式充分利用制造資源，提升生產能力上限，進而提高生產效率、縮短生產時間，降低成本和能耗，推動中國制造產業高質量發展。本文主要研究了云制造模式下的柔性生產調度問題，提出了云制造模式調度框架；對MBO 算法進行了優化，在問題求解過程中使用了新的種群編碼方式，利用3 種種群初始化策略按比例生成優質種群；采用新的進化方式并且引入變鄰域搜索，提升算法的全局和局部搜索能力；最后用常用的10 個柔性調度案例驗證了IM-MBO 算法的正確性和有效性，有利于提升云制造環境下的生產速率并降低生產成本。后續會考慮云制造環境下的動態訂單調度問題，并采用IM-MBO 算法將云制造模式擴展成多目標問題求解，以更加符合實際需求。