云制造生產(chǎn)模式下的生產(chǎn)調(diào)度研究

萬(wàn)雨松，余開(kāi)朝

（昆明理工大學(xué)機(jī)電工程學(xué)院，云南昆明 650093）

0 引言

我國(guó)各地區(qū)制造業(yè)水平差別巨大，制造資源分布極不均勻，并且存在著制造企業(yè)擁有很多制造資源，但由于沒(méi)有充足的制造任務(wù)致使其被閑置的現(xiàn)象，從而導(dǎo)致了制造資源的浪費(fèi)［1］。針對(duì)該情況，并且考慮到《中國(guó)制造2025》戰(zhàn)略目標(biāo)的需要，李伯虎院士［2］提出了云制造這一全新的生產(chǎn)模式。

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

目前學(xué)者們對(duì)于云制造的研究主要是考慮制造的服務(wù)屬性，如Vahedi 等［4］在參與云制造的工廠之間建立相關(guān)權(quán)重，并設(shè)置提交訂單客戶的偏好權(quán)重，以便更好地進(jìn)行任務(wù)匹配；郭亮等［5］研究云制造不同任務(wù)層次的加工任務(wù)匹配，構(gòu)建了相對(duì)應(yīng)的優(yōu)化任務(wù)匹配模型。但目前已有研究比較關(guān)心的是云制造的服務(wù)屬性，對(duì)于云制造模式下的生產(chǎn)相關(guān)部分的研究較少。

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

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

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

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

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

1 問(wèn)題模型

1.1 云制造模式與調(diào)度框架

如圖1 所示，在云調(diào)度生產(chǎn)模式中，個(gè)人或企業(yè)用戶根據(jù)自身需要提交制造需求訂單，生產(chǎn)訂單會(huì)在云制造平臺(tái)上拆分成不同的加工部件生產(chǎn)任務(wù)，然后這些任務(wù)會(huì)根據(jù)企業(yè)的制造能力進(jìn)行匹配調(diào)度。生產(chǎn)任務(wù)的分配結(jié)果會(huì)返送給客戶和企業(yè)，企業(yè)再將生產(chǎn)任務(wù)拆分成工序，進(jìn)行柔性生產(chǎn)調(diào)度，并將調(diào)度結(jié)果下達(dá)至生產(chǎn)一線進(jìn)行生產(chǎn)。

Fig.1 Cloud manufacturing production mode圖1 云制造生產(chǎn)模式

針對(duì)云制造模式下的生產(chǎn)任務(wù)排序與機(jī)器選擇的組合問(wèn)題特性，找到合理的求解方法以充分利用企業(yè)的制造能力是有必要的。云制造模式下的柔性調(diào)度問(wèn)題計(jì)算適合采用元啟發(fā)式方法，即在一定時(shí)間內(nèi)獲得可接受的調(diào)度方案，而不是耗費(fèi)大量計(jì)算時(shí)間獲得最優(yōu)解。

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

Fig.2 Cloud manufacturing mode scheduling framework圖2 云制造模式調(diào)度框架

在云制造模式下，生產(chǎn)調(diào)度需要考慮的不僅僅是工序的加工順序排列和工序選擇哪個(gè)加工設(shè)備，而且需要適應(yīng)整個(gè)生產(chǎn)模式的要求。如企業(yè)需要制定自身的生產(chǎn)任務(wù)計(jì)劃，然后需要利用空閑的制造資源接收云平臺(tái)的生產(chǎn)任務(wù)，這就要平衡兩組任務(wù)使用機(jī)器時(shí)可能導(dǎo)致的加工時(shí)間沖突問(wèn)題。在常規(guī)的調(diào)度問(wèn)題基礎(chǔ)上，云制造模式下的調(diào)度問(wèn)題還引入了效率要求，所以問(wèn)題的構(gòu)成與求解更為復(fù)雜。

1.2 云制造模式下FJSP問(wèn)題模型構(gòu)建

為更好地描述與解決柔性作業(yè)車間調(diào)度問(wèn)題，用以下參數(shù)和約束式對(duì)FJSP 問(wèn)題構(gòu)建相應(yīng)數(shù)學(xué)模型，如表1所示。

判斷參數(shù)：

Table 1 Flexible production scheduling model parameters表1 柔性生產(chǎn)調(diào)度模型參數(shù)

要符合云調(diào)度生產(chǎn)模型，就有一定的限制條件，具體如下：

（1）工序約束。

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

（2）加工設(shè)備約束。

式（2）表示在同一時(shí)間，一個(gè)加工設(shè)備上只能進(jìn)行一個(gè)工序的加工。

（3）加工過(guò)程約束。

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

在上述約束之外，考慮到實(shí)際情況，還有一些其他約束：在初始時(shí)間，需要加工的工件和對(duì)應(yīng)的加工機(jī)器都已準(zhǔn)備就緒，所有參數(shù)均為非負(fù)數(shù)。

本文采用的求解指標(biāo)是最大完工時(shí)間最小指標(biāo)，也是最常用的調(diào)度性能指標(biāo)，具體如式（4）所示。

對(duì)一組調(diào)度計(jì)劃來(lái)說(shuō)，就是要求得使時(shí)間最長(zhǎng)、Ti值最小的調(diào)度方案，并且求解方法可擴(kuò)展成多目標(biāo)優(yōu)化求解，也可引入生產(chǎn)平衡率、加工成本等其他生產(chǎn)指標(biāo)。因此，本文對(duì)問(wèn)題的研究主要基于最大完工時(shí)間最小指標(biāo)，并將本文算法的求解結(jié)果與目前國(guó)內(nèi)外比較典型的算法結(jié)果進(jìn)行比較，以衡量算法性能。由于候鳥(niǎo)算法的通用性，尤其是其領(lǐng)飛鳥(niǎo)的設(shè)計(jì)方案，使得該算法不會(huì)受到問(wèn)題約束條件的影響。

2 候鳥(niǎo)算法

MBO（Migratory Bird Optimization Algorithm）算法是一種利用共享搜索解機(jī)制的群體元啟發(fā)式算法。該方法是基于候鳥(niǎo)在飛行中保持V 型編隊(duì)以節(jié)省能量消耗的原理，由Duman 等［17］在2012 年首次提出，用于解決二次分配優(yōu)化問(wèn)題。MBO 算法主要有以下幾個(gè)步驟：種群初始化、領(lǐng)飛鳥(niǎo)進(jìn)化更新最優(yōu)值、跟飛鳥(niǎo)進(jìn)化更新解、更換領(lǐng)飛鳥(niǎo)，通過(guò)這樣的循環(huán)找到最優(yōu)解。

初始候鳥(niǎo)群（也即問(wèn)題可能的解）組成一個(gè)V 形編隊(duì)，包括一個(gè)先導(dǎo)候鳥(niǎo)和一些跟隨候鳥(niǎo)。如圖3 所示，在解決方案群中，為每個(gè)候鳥(niǎo)搜索鄰域（即在每個(gè)解決方案附近生成數(shù)量有限的解決方案），評(píng)估每個(gè)候鳥(niǎo)的相鄰解決方案。如果有更好的優(yōu)化解，則該候鳥(niǎo)將被替換為更好的解決方案。

Fig.3 Schematic diagram of excellent neighborhood sharing圖3 優(yōu)秀鄰域分享示意圖

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

Fig.4 Schematic diagram of replacing the collar bird圖4 更換領(lǐng)飛鳥(niǎo)示意圖

分析候鳥(niǎo)算法的過(guò)程，單個(gè)候鳥(niǎo)的不同鄰域搜索和進(jìn)化策略能保證全局分散的搜索能力，共享鄰域解能保證單個(gè)個(gè)體能通過(guò)整體的較優(yōu)解進(jìn)化，保證算法集中的搜索性能。MBO 算法在局部搜索的能力是比較優(yōu)異的。

對(duì)于啟發(fā)式算法而言，種群收斂不是越快越好。若種群收斂太快，會(huì)在全局搜索不足的情況下過(guò)早地聚集在局部解，陷入局部最優(yōu)。MBO 算法將前面?zhèn)€體的鄰域解分享給后面的多個(gè)跟隨個(gè)體，從一方面來(lái)看，優(yōu)化了種群的整體性能，但從另一方面來(lái)看，更多候鳥(niǎo)進(jìn)入到前鳥(niǎo)附近，造成候鳥(niǎo)的種群多樣性損失嚴(yán)重，容易陷入局部最優(yōu)的陷阱。所以需要對(duì)MBO 算法進(jìn)行相應(yīng)的優(yōu)化改進(jìn)，以提升搜索性能。

2.1 編碼／解碼方案

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

解碼是對(duì)編碼的逆向操作，根據(jù)得到的矩陣給出合理的柔性調(diào)度方案，例如給出一個(gè)初始種群X：

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

2.2 種群初始化方案

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

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

（2）優(yōu)先機(jī)器的選擇方法。首先是第一個(gè)工序和下一個(gè)工序隨機(jī)選擇加工機(jī)器，然后記錄每臺(tái)機(jī)器的操作時(shí)間，在下一個(gè)工序Oij選擇機(jī)器時(shí)，將可選擇機(jī)器之前的加工時(shí)間與Oij的加工時(shí)間相加，選擇總加工時(shí)間最短的機(jī)器，然后繼續(xù)下一個(gè)工序的機(jī)器選擇，直到所有工序都選擇了對(duì)應(yīng)的加工機(jī)器。使用優(yōu)先機(jī)器的選擇方法生成20%的初始候鳥(niǎo)，使用該方法的優(yōu)點(diǎn)是其可在算法初始階段使機(jī)器的工作時(shí)間盡量一致，從而更好地探索搜索空間，并考慮機(jī)器的工作負(fù)載平衡。

（3）優(yōu)先工件的選擇方法。對(duì)工件的可選擇機(jī)器進(jìn)行隨機(jī)選擇，在機(jī)器的加工順序上，優(yōu)先加工剩余工序總時(shí)長(zhǎng)最長(zhǎng)工件的一個(gè)工序，然后再以同樣的規(guī)則選擇下一個(gè)工件進(jìn)行工序加工。使用優(yōu)先工件的選擇方法生成20%的初始候鳥(niǎo)，該方法的優(yōu)點(diǎn)是可以搜索到令所有工件加工時(shí)間最大值盡可能小的解空間。

2.3 候鳥(niǎo)群進(jìn)化

在MBO 算法中，領(lǐng)飛鳥(niǎo)是第一個(gè)開(kāi)始搜索鄰域解的個(gè)體，然后如果有更好的解，則編碼矩陣更換為更好的解，這被稱為鳥(niǎo)群個(gè)體的進(jìn)化，之后分享自身的優(yōu)秀解給后續(xù)候鳥(niǎo)。這種機(jī)制就是模擬實(shí)際候鳥(niǎo)隊(duì)列給后續(xù)候鳥(niǎo)的抬升力，后續(xù)候鳥(niǎo)可在自身搜索的解和前鳥(niǎo)提供的解中進(jìn)行選擇與進(jìn)化，這就是候鳥(niǎo)群的進(jìn)化。搜索解的方法主要是鄰域搜索，柔性調(diào)度和常規(guī)調(diào)度的主要區(qū)別在于多了機(jī)器選擇，本文主要采用以下4種鄰域搜索策略：

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

（2）工序交換搜索。隨機(jī)將一個(gè)機(jī)器上的兩個(gè)工序交換（也即交換矩陣編碼的小數(shù)部分）。

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

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

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

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

2.4 變鄰域搜索

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

步驟1：選取候鳥(niǎo)群進(jìn)化的最優(yōu)個(gè)體B 作為變鄰域搜索的起始值，搜索策略Smax=4，搜索次數(shù)Nmax=n。

步驟2：令S=1，從2.3 節(jié)的第S 個(gè)鄰域搜索策略開(kāi)始對(duì)B 的矩陣編碼進(jìn)行搜索變換，得到編碼矩陣B1。

步驟3：利用鄰域結(jié)構(gòu)設(shè)定搜索次數(shù)對(duì)B1進(jìn)行搜索，達(dá)到搜索次數(shù)后將其中的最優(yōu)解設(shè)為B2。

步驟4：若B2是最優(yōu)解，則將B2賦值給B，跳回步驟2繼續(xù)搜索；若B 是最優(yōu)解，則S=2，繼續(xù)搜索，直到搜索策略S和搜索次數(shù)達(dá)到上限。

步驟5：選取最優(yōu)解賦值給B，變鄰域搜索結(jié)束。

2.5 改進(jìn)候鳥(niǎo)算法流程

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

下面用mk01 的案例進(jìn)行說(shuō)明，最終得出調(diào)度方案的甘特圖如圖7 所示（彩圖掃OSID 碼可見(jiàn)）。數(shù)字是加工工件的序號(hào)，橫軸方向是工序加工時(shí)間，縱軸是機(jī)器上的加工工序。

Fig.7 Optimal scheduling result of mk01 of MBO algorithm圖7 MBO算法mk01最優(yōu)調(diào)度結(jié)果

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

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

Table 2 Comparison of efficienty of main heuristic algorithms表2 主要啟發(fā)式算法效率對(duì)比

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

4 結(jié)語(yǔ)

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