蔡躍坤，朱智鵬，譚 沖

（廣東科技學(xué)院 機電工程學(xué)院，廣東 東莞 523083）

0 引言

隨著時代的發(fā)展，人們對個性化產(chǎn)品的需求日益增長，一種新型的制造服務(wù)模式C2M（Customerto-Manufacturer）應(yīng)運而生。C2M通過互聯(lián)網(wǎng)使消費者和生產(chǎn)線得以連結(jié)在一起，從而可以取消掉中間周轉(zhuǎn)環(huán)節(jié)，用戶直接參與產(chǎn)品的設(shè)計與制造過程，以生產(chǎn)符合用戶需求的定制化產(chǎn)品[1-2]。C2M以開放式結(jié)構(gòu)產(chǎn)品（Open Architecture Product，OAP）為實現(xiàn)形式，將產(chǎn)品分為可大批量生產(chǎn)的通用模塊、用戶適應(yīng)的大批量定制模塊和完全由用戶設(shè)計的個性化定制模塊[3-4]。一方面，OAP為客戶端提供了個性化定制的服務(wù)，滿足了客戶的消費需求。另一方面，OAP通過制造模塊的劃分，為企業(yè)制造端降低了制造成本。制造能力強的企業(yè)或車間生產(chǎn)大規(guī)模通用或定制模塊零部件，而柔性能力強的企業(yè)或車間則生產(chǎn)客戶個性化模塊產(chǎn)品零部件，最終通過企業(yè)或車間的協(xié)作，為客戶提供個性化產(chǎn)品定制服務(wù)。

在智能制造生產(chǎn)調(diào)度方面，國內(nèi)外學(xué)者做了許多研究，主要集中在以下幾個方面：基于數(shù)據(jù)挖掘的動態(tài)生產(chǎn)調(diào)度[6-8]，主要是利用制造車間的加工數(shù)據(jù)進行訓(xùn)練，挖掘其與生產(chǎn)系統(tǒng)相映射的調(diào)度規(guī)則；在制造物聯(lián)的環(huán)境下利用分布式協(xié)同控制的多智能體技術(shù)來實現(xiàn)實時生產(chǎn)調(diào)度[9-12]，一般有兩種解決方案。第一種是借用CPS（Cyber-Physical Systems，CPS）理念，在虛擬空間中建立與制造實體以及工件、AGV（Automatic Guided Vehicle）相對應(yīng)的智能體，通過智能體的交互得出實時調(diào)度策略再反饋控制到制造實體上。另一種方案是使用嵌入式多智能體技術(shù)，直接嵌入到制造實體中，最終也同樣通過智能體交互作出實時調(diào)度策略。在智能制造的研究對象方面來說，目前大多數(shù)研究都僅針對傳統(tǒng)的生產(chǎn)制造模式，在考慮多種不同的約束條件下進行研究[13-14]。

總的來說，要實現(xiàn)智能制造生產(chǎn)調(diào)度，就必須要利用好實時制造數(shù)據(jù)來作出相應(yīng)的實時調(diào)度策略。而C2M制造服務(wù)模式對制造車間的柔性化、數(shù)字化和智能化能力提出了更高的要求。因此，在智能制造的背景下，研究C2M制造服務(wù)模式的生產(chǎn)調(diào)度模塊具有重要意義。

1 問題描述與調(diào)度模型

1.1 問題描述與條件假設(shè)

以柔性作業(yè)車間（Flexible Job Shop）作為C2M制造服務(wù)模式的最小量化單位展開研究。在智能柔性作業(yè)車間中，依托制造物聯(lián)網(wǎng)，訂單任務(wù)數(shù)據(jù)以及制造數(shù)據(jù)可以被實時采集與傳輸?shù)紺PS（Cyber Physical Production）。如圖1所示，智能工廠柔性作業(yè)車間生產(chǎn)調(diào)度模塊基本架構(gòu)如下：

圖1 智能制造生產(chǎn)調(diào)度模塊示意圖Figure 1 Schematic diagram of intelligent manufacturing production scheduling module

（1）ERP（Enterprise Resource Planning）層：收集來自客戶的訂單數(shù)據(jù)，并將訂單進行分解得到通用模塊子任務(wù)、定制模塊子任務(wù)和個性化模塊子任務(wù)，子任務(wù)進一步工序分解得到產(chǎn)品各階段加工工序。

（2）MES（Manufacturing Execution System）層：收集來自于ERP層的訂單數(shù)據(jù)和來自于制造層的實時制造數(shù)據(jù)，根據(jù)兩類數(shù)據(jù)作出實時調(diào)度決策，并反饋到制造層各制造實體。

（3）制造層：實體制造設(shè)備如機床、AGV等實現(xiàn)人-設(shè)備、設(shè)備-設(shè)備互聯(lián)，并通過無線射頻RFID（Radio Frequency Identification）等技術(shù)實現(xiàn)數(shù)據(jù)的實時采集，將實時數(shù)據(jù)傳輸?shù)組ES層。

整個生產(chǎn)調(diào)度過程是由自感知-自決策-自執(zhí)行-自適應(yīng)的閉環(huán)結(jié)構(gòu)組成：

自感知：訂單到達與任務(wù)工序分解、實時制造數(shù)據(jù)；

自決策：MES中調(diào)度模塊作出實時調(diào)度決策；

自執(zhí)行：調(diào)度決策通過網(wǎng)絡(luò)傳輸、PLC控制等傳達到調(diào)度參與設(shè)備；

自適應(yīng)：識別緊急插單和設(shè)備故障等擾動事件，作出重調(diào)度決策，修正調(diào)度方案。

針對上述C2M制造服務(wù)模式的智能工廠柔性作業(yè)車間生產(chǎn)調(diào)度問題，作出如下假設(shè)：

（1）在C2M制造服務(wù)模式中，客戶訂單隨機出現(xiàn)，無法預(yù)測。針對該情況，本文采用先到先服務(wù)與周期性調(diào)度結(jié)合的方式進行，并假設(shè)訂單的交貨期遠大于等待加工及加工時間之和。

（2）在先到先服務(wù)與周期性調(diào)度的情況下，仍有特別緊急的訂單存在。

（3）加工時間、等待時間等數(shù)據(jù)可以被實時記錄與傳輸。

（4）每道工序可以在至少一臺機床上加工，且工序在不同機床上的加工時間已知。

1.2 調(diào)度模型

在C2M制造服務(wù)模式智能工廠中，先將一段周期內(nèi)的訂單全部進行任務(wù)分解得到N個子任務(wù)，用Fi來表示，其中，i={1，2，…，N}。每個子任務(wù)都可以在M個制造資源上加工。其中，任意的加工機床設(shè)備用k表示，k={1，2，…，M}。每個子任務(wù)都有L道加工工序，其中，j={1，2，…，L}，產(chǎn)品的任務(wù)i中的第j道工序用Fij來表示。選取最小化最大總加工時間為該調(diào)度問題的優(yōu)化目標(biāo)，目標(biāo)函數(shù)如下：

式中：hijk表示工序是否在設(shè)備k上加工，具體由（4）式表示；si表示子任務(wù)Fi所對應(yīng)的工件數(shù)量；tijk表示任務(wù)i中的第j道工序在機床k上面的加工時間；式（2）表示任務(wù)的工序有一定的順序約束；式（3）表示同一機床上的待加工任務(wù)順序約束；式（5）表示加工總時間T必須小于交貨期約束Tmax。

2 算法設(shè)計

麻雀搜索算法（Sparrow Search Algorithm，SSA）是一種新的群智能搜索算法[5]。在實際的優(yōu)化過程中，該算法容易收斂于零點和當(dāng)前最優(yōu)解點，易陷入局部最優(yōu)?；诖?，本文設(shè)計一種基于遺傳算法（Genetic Algorithm，GA）與麻雀搜索算法融合的尋優(yōu)算法，相較于SSA，GA具有更強的全局搜索能力。因此，GA-SSA算法既保留了SSA的簡單、靈活、參數(shù)少等優(yōu)點，同時也能兼顧全局尋優(yōu)能力。

2.1 SSA算法簡介

SSA算法具有發(fā)現(xiàn)者、加入者和警戒者三種角色。發(fā)現(xiàn)者尋找食物，為種群其他個體提供覓食方向；加入者根據(jù)發(fā)現(xiàn)者提供的信息覓食；發(fā)現(xiàn)者和加入者都可以發(fā)現(xiàn)捕食者，都可以扮演警戒者角色。也就是每只麻雀有三種可能的行為：第一，作為發(fā)現(xiàn)者，繼續(xù)搜索食物；第二，作為跟隨者，跟隨一個發(fā)現(xiàn)者覓食；第三，警戒偵查，有危險則放棄食物。每經(jīng)過一次迭代都要對位置進行一次變更，其位置變更精確表達式如下：

其中，式（6）表示每一次迭代后的發(fā)現(xiàn)者位置更新策略；式（7）表示跟隨者經(jīng)過迭代后的位置更新策略；式（8）表示警戒者的位置更新策略。式（6）~式（8）字母具體釋義可參考文獻[5]，這里不再具體解釋。

2.2 編碼與交叉變異

C2M制造服務(wù)模式需要將訂單劃分為子任務(wù)和工序集，因此本文提出一種雙層編碼的方式對任務(wù)和工序進行編碼，如圖2所示。染色體的第一層表示子任務(wù)編號以及所對應(yīng)的的工序，例如第一層出現(xiàn)的第一個3表示第3個任務(wù)的第一道工序。染色體第二層表示子任務(wù)所對應(yīng)的訂單產(chǎn)品，例如第二層出現(xiàn)的第一個1表示訂單產(chǎn)品1的第3個子任務(wù)的第3道工序。這里子任務(wù)編號1-3分別表示為通用模塊子任務(wù)、定制模塊子任務(wù)、個性化模塊子任務(wù)。

圖2 編碼方式Figure 2 Encoding method

由于SSA每個個體的位置是離散的，用D維位置空間向量X=（x1，x2，…，xd）表示，則本文編碼方式對應(yīng)的麻雀位置解讀為，麻雀x1標(biāo)記為個性化模塊的第3個任務(wù)的第1道工序，以此類推。

在編碼機制中，下層編碼會隨著上層編碼的變化而變化，因此在執(zhí)行交叉和變異操作時，只需要對上層編碼進行交叉變異即可。通過提前設(shè)定合理的交叉變異概率，增強SSA全局搜索能力，同時也能最大程度上保留SSA簡單、靈活和高效的算法特點。

2.3 適應(yīng)度函數(shù)

在GA-SSA算法里，適應(yīng)度值越高則表明被選擇保留的幾率越大。本文適應(yīng)度函數(shù)與目標(biāo)函數(shù)結(jié)合，由于目標(biāo)函數(shù)是最小化最大總加工時間，這里取目標(biāo)函數(shù)的倒數(shù)為適應(yīng)度函數(shù)，即f（x）為：

其中，minT表示本文求解的目標(biāo)函數(shù)值，即最小化總加工時間。

2.4 調(diào)度算法流程

結(jié)合GA和SSA，設(shè)計算法流程如圖3所示，具體步驟如下：

圖3 算法調(diào)度流程Figure 3 Algorithm scheduling process

Step1：設(shè)置算法相關(guān)參數(shù)，種群初始化，區(qū)分發(fā)現(xiàn)者與跟隨者；

Step2：進行位置更新操作，計算并保留適應(yīng)度值；

Step3：個體與個體隨機交叉，計算適應(yīng)度值，比較保留較好適應(yīng)度值對應(yīng)位置；

Step4：判斷是否達到預(yù)設(shè)迭代次數(shù)，如未能達到則隨機變異后返回step2，如達到則繼續(xù)下一步驟；

Step5：算法結(jié)束，輸出結(jié)果。

3 基于效能偏差判別的重調(diào)度策略

3.1 效能偏差值

C2M智能工廠基于信息物聯(lián)系統(tǒng)作為其生產(chǎn)架構(gòu)，通過物聯(lián)系統(tǒng)采集和傳輸制造實時數(shù)據(jù)。在實時數(shù)據(jù)的支撐下，對制造車間或訂單產(chǎn)生的動態(tài)擾動作出實時重調(diào)度策略，最大程度上消除生產(chǎn)擾動帶來的影響。

在生產(chǎn)制造中，會有緊急插單和設(shè)備故障等擾動情況發(fā)生。但在實際生產(chǎn)調(diào)度中，并不是一有擾動事件發(fā)生就開始實行重調(diào)度，而是需要判別擾動情況對生產(chǎn)系統(tǒng)產(chǎn)生的效能影響。頻繁的重調(diào)度策略會降低生產(chǎn)系統(tǒng)的穩(wěn)定性，從而增加不必要的制造成本。本文提出的效能影響判別機制具有制造延遲率和資源利用率兩個指標(biāo)，制造延遲率是越小越好，資源利用率越大越優(yōu)，因此其判別機制如下：

式中：γ為制造車間產(chǎn)生擾動后，對工序加工產(chǎn)生的最大制造延遲率；β為資源利用率。式（12）中q為加工資源數(shù)；Toriginal為原始調(diào)度方案完工時間；TM表示制造資源的加工時間。γ與β的比值求得式（10）的效能偏差值δ。

3.2 重調(diào)度策略

根據(jù)實際加工情況可人為設(shè)置效能偏差閾值δ′。當(dāng)生產(chǎn)系統(tǒng)效能偏差值δ≤δ′時，則認(rèn)為此時不需要進行重調(diào)度，具體可以解釋為此時生產(chǎn)系統(tǒng)產(chǎn)生的擾動影響可以忽略不計，對制造結(jié)果改變不大；當(dāng)生產(chǎn)系統(tǒng)效能偏差值δ＞δ′時，則此時擾動對生產(chǎn)系統(tǒng)影響較大，需要立即進行重調(diào)度。重調(diào)度流程如圖4所示。

圖4 重調(diào)度流程Figure 4 Rescheduling process

4 仿真算例驗證

為驗證GA-SSA算法的有效性，設(shè)置6×6仿真算例如下：有6個待加工工件，其子任務(wù)的每一道工序都可以在6臺機床的至少一臺機床上加工，實驗數(shù)據(jù)如表1所示。

表1 仿真數(shù)據(jù)集Table 1 Simulation dataset

首先進行算法可行性驗證，選取工件1~5作為算例，采用MATLAB對模型進行求解，設(shè)置參數(shù)如表2所示。

表2 參數(shù)設(shè)置Table 2 Parameter settings

為了評估GA-SSA混合算法的性能，在相同實驗條件下，分別與GA和SSA算法做對比實驗。求解優(yōu)化變化曲線圖如圖5所示。算法運行結(jié)果對比如表3所示，GA-SSA在迭代40多次時得到最優(yōu)解66，并且在收斂速度與最優(yōu)解質(zhì)量兩方面均優(yōu)于GA和SSA。

圖5 算法求解最優(yōu)過程Figure 5 Algorithm to solve the optimal process

表3 算法運行對比Table 3 Algorithm running comparison

為進一步驗證重調(diào)度方案的可行性，以工件6作為緊急插單工件，此時生產(chǎn)系統(tǒng)效能偏差大于設(shè)置的閾值，緊急插單帶來的生產(chǎn)擾動影響比較大，系統(tǒng)開始進行重調(diào)度。原始調(diào)度方案甘特圖和重調(diào)度甘特圖分別如圖6和圖7所示。

圖6 靜態(tài)調(diào)度甘特圖Figure 6 Static Scheduling Gantt Chart

圖7 重調(diào)度甘特圖Figure 7 Rescheduling Gantt Chart

經(jīng)過靜態(tài)調(diào)度與動態(tài)調(diào)度實驗對比，驗證了本文所提出GA-SSA混合算法的優(yōu)越性，以及本文提出的重調(diào)度策略的有效性。

5 結(jié)論

本文針對面向C2M的智能制造生產(chǎn)調(diào)度問題，首先對C2M制造服務(wù)模式進行了分析，進一步提出將該生產(chǎn)調(diào)度任務(wù)分解為三個模塊子任務(wù)以及加工工序?；谥悄芄S的基本構(gòu)架，提出基于物聯(lián)網(wǎng)的ERP-MES-制造層聯(lián)動的自感知、自決策、自執(zhí)行和自適應(yīng)調(diào)度方案。本文建立以最小化最大總加工時間為目標(biāo)函數(shù)的優(yōu)化模型，利用GA-SSA融合算法，不僅具有GA的良好全局搜索能力還具有SSA簡單、靈活、收斂快速的算法特點，用以求解目標(biāo)函數(shù)。同時，在周期性靜態(tài)調(diào)度的基礎(chǔ)上，本文還提出一種基于效能偏差判別機制的重調(diào)度策略，以實時對生產(chǎn)系統(tǒng)擾動事件作出響應(yīng)。最后以一個6×6的算例驗證了本文所提出調(diào)度方案的可行性與優(yōu)越性。由于本文假設(shè)的條件相對比較多，未來的研究將會進一步接近于現(xiàn)實問題，以及研究C2M制造服務(wù)模式的物流規(guī)劃等問題，希望對C2M模式以及智能制造的最終落地提供理論上的指導(dǎo)與借鑒。