一種規則可配置的柔性制造系統自適應調度方法

劉政君

（中國航空制造技術研究院 數字化制造技術航空科技重點實驗室，北京 100024）

柔性制造系統在航空零部件生產中運用廣泛，但由于其在不同的調度場景下具有各異的調度特征，導致柔性制造系統的調度系統難以在不同調度場景之間復用。實際生產中，調度系統開發者目前的普遍做法是根據不同場景各自的特征，針對性地研究調度方法和開發調度系統，但任務量龐大。若能夠針對復雜的調度情境快速構建排產系統，可節約大量的時間和人力成本。因此，針對柔性制造系統復雜多變的調度特征，如何快捷高效地開發與之相適應的調度系統是一個值得深入研究的問題。

目前，針對柔性制造系統調度問題的研究大都是針對某個特定場景。例如：對于動態流水車間場景，EL-BOURI等提出了一種對相鄰設備進行協同分派的優先級規則，并取得了較好的調度求解結果[1]；對于部分柔性的制造環境，邵斌彬等設計了一種基于綜合分配規則的快速啟發式調度算法[2]；針對作業車間調度場景，CHEN等提出一種柔性的依據偏好來決策的分派規則，證明了該分派規則相較于傳統分派規則具有優越性[3]；也有不少學者通過人工智能方法解決柔性制造系統的調度問題，取得了不錯的進展[4-7]。但是，在開發復用型調度系統方面，國內還少有研究。

針對調度系統在不同場景之間的復用性問題，本文提出了一種規則可配置的自適應調度方法。決策者只需根據生產線的特征配置對應的參數，就能應對不同特征的調度場景，同時分析并處理柔性制造系統的擾動，使調度方法更具魯棒性。

1 規則可配置的調度框架構建

針對柔性制造系統復雜多變的調度特征和柔性制造系統可能出現的擾動，提出了一種規則可配置的調度框架。整體調度框架如圖1所示，共分為3部分。第1部分為規則配置，負責根據不同生產線的特征來配置相應的排產規則，并根據規則將排產的約束條件抽象為排產算法所需的輸入參數。第2部分為排產算法，負責確定邊界和約束條件的基于優先級的排產算法。算法的輸入需要遵守配置規則的約束條件和擾動約束條件。第3部分為擾動分析與處理，負責對柔性制造系統擾動進行歸類分析，并根據擾動類型處理 擾動。

圖1 整體調度框架

2 基于優先級規則的排產算法簡介

基于優先級規則的啟發式排產算法具有無須迭代運算、運算速度快、容易認知理解等特點，在求解實際生產調度中被廣泛運用。眾多學者對該算法進行了改進，目前已有多種優先級規則[8-12]。該算法通過某種預定的規則為各個工序任務賦予優先級（如SPT規則、EDD規則等），然后按照優先級的高低順序依次為各個工序任務安排生產設備。算法的執行流程如 圖2所示。

圖2 基于優先級排產算法流程

（1）篩選可排產的工序任務序列，輪訓當前所有訂單，將排產的工序任務加入待排產序列；

（2）為待排產序列中的工序任務安排優先級；

（3）按照優先級順序依次為最高優先級的工序任務安排加工設備；

（4）每安排一個工序任務，更新設備的任務隊列，并重復步驟（1）直至所有的工序任務都被安排完畢。

3 規則配置

優先級是基于優先級規則的排產算法中較為關鍵的參數，包括任務優先級和設備優先級。任務優先級指工序任務被安排的先后順序。任務優先級排產算法按照優先級的高低順序依次為所有工序任務安排生產設備。設備優先級指當某工序任務擁有超過多臺可用設備且需在多臺設備中選擇一個用于加工時，選擇加工設備的優先順序。設備優先級排產算法會為工序任務安排擁有當前最高優先級的可用設備。

關于優先級的啟發式規則的研究目前已經比較成熟，產生了眾多優先級規則，如SPT規則、EDD規則、Johnson規則、CDS規則、Palmer規則、LNS規則以及FIFO規則等。但是，這些規則往往只是對工序任務的某一個或幾個屬性較為關注，存在各自的局限性。若能夠將這些規則集合封裝形成一個優先級規則系統，決策者就能夠在系統中選取適用的規則進行排產，甚至編制優先級規則，大大提高了優先級規則的適用性。因此，提出優先級規則的配置方法用于實現優先級規則系統的構建，主要包括離散型配置方法和連續型配置方法。

離散型任務優先級的配置規則如表1所示。決策者可以配置決定優先級的各個屬性值，并直接指定對應屬性下的任務優先級。本文以剩余交貨時間、緊迫率、重要程度和加工時間為例，講述離散型任務優先級的配置過程。決策者可以根據各個屬性的值直接給定一個對應的優先級值，如任務的交貨期為1～3 d，緊迫率為1.0～7.2，重要程度為“很重要”，加工時間為10～24 h，給定優先級值為5。離散型規則配置表格并不局限于上述屬性，表格屬性的數量是可配置的，決策者可以根據需要在系統中添加或者刪除某列屬性。

表1 離散型任務優先級配置表

與離散型優先級配置方法直接指定任務的優先不同，連續性任務優先級配置方法是通過權衡幾個屬性的權重計算出一個加權值，并用“1”除以該加權值作為任務的優先級。如表2所示，決策者選擇添加參與決策的屬性，并給定這些屬性的權重值。權重值越大，表明該項屬性越受到重視。為了統一量綱，使得每個屬性對優先級的貢獻得分大致落在相同的量級范圍內，不出現因量級差距過大導致某項屬性的貢獻被忽略的現象，需對各個屬性的取值進行歸一化處理。

表2 連續性任務優先級規則配置表

本文以加工時間、剩余交貨時間、緊迫率和重要程度為例進行說明。

加工時間得分的取值S1為

式中：S1為加工時間得分的取值；t為任務加工時間；tmin為待排產任務中的最小加工時間；tmax為待排產任務中的最大加工時間。

剩余交貨時間得分的取值S2為

式中：S2為剩余交貨時間得分的取值；T1為最長交貨期；T2為任務剩余交貨時間；Tmax為待排產任務中最長交貨期。

緊迫率得分的取值S3為

式中：S3為緊迫率得分的取值；a為任務的緊迫率；amax為待排產任務中最大緊迫率；amin為待排產任務中最小緊迫率。

重要程度得分的取值S4為

式中：S4為重要程度得分的取值；Smax為任務最大取值得分；S為任務取值得分；Smin為任務最小取值得分。關于重要程度，規定“非常重要”取值為“1”，“很重要”取值為“2”，“一般”取值為“3”，“不重要”取值為“4”。

規定各屬性權重值的取值范圍為0～100的整數，計算時將各權重值進行歸一化處理。

優先級的計算公式為

式中：Ai為各個屬性值的得分；ωi為各個屬性對應的權重值。

利用這兩種方法，決策者可以通過適當的配置得到現有的優先級規則，也可以自定義屬于某種場景的特殊規則。例如，EDD規則關注工件任務的交貨期，交貨期越接近的工件，優先級越高。在配置規則時，采用離散型配置法只需配置各個交貨期時間段的對應任務優先級即可完成配置。在配置規則時，采用連續型配置法需要配置交貨期這一屬性的權重，并將其他權重值設為0。

離散型任務優先級配置方法只要參數設置得當，各個優先級規則的擬合效果就會較好。理論上，通過離散優先級的配置方法，可以擬合出現有大部分的優先級規則。它的缺點在于需要配置的參數較多，配置過程較為煩瑣。連續型配置方法的優點在于配置簡單，只需添加相關屬性并配置對應的權重值，缺點在于由于優先級配置公式為線性公式，對某些非線性優先級規則的擬合效果可能不好。

設備優先級的配置過程與任務優先級類似，區別在于所配置屬性不同，這里不再贅述。

4 擾動分析與處理

當柔性制造系統發生擾動時，調度系統會根據可編程邏輯控制器（Programmable Logic Controller，PLC）反饋的現場情況判斷擾動類型，并根據不同的故障信息觸發對應的處理策略，重新生成符合現狀的調度方案，并下發至動作規劃層執行。在生成新的調度方案時，需遵循盡量少改動原排產方案的原則，盡量減小擾動對調度方案的影響。

匯總并歸類分析柔性制造系統常見的擾動可知，常見擾動主要包括設備故障類擾動、進度異常類擾動和訂單變動類擾動[13-14]。擾動處理的流程圖如圖3所示。當調度系統接收到反饋的擾動信息后，會優先判斷擾動的種類。如果擾動是設備故障類擾動或者訂單變動類擾動，將直接觸發系統進行重新排產。如果擾動是進度異常類擾動，會根據重排產策略計算擾動的重排產判別值。如果判別值未超過設定閾值，則認為該擾動造成的影響較小，不需要重新排產。如果判別值超過設備閾值，則認為擾動造成影響較大，必須重新排產。重新排產后利用得到的新排產方案下發到動作執行層執行，如此循環往復，直至方案執行完畢。

圖3 擾動處理流程圖

4.1 設備故障類擾動分析與處理

設備故障類異常包括設備故障、設備定時維修等。某些與設備相關的資源長時間短缺，也會造成設備故障類擾動，如刀具、人員等。該類擾動具體表現為設備在一段時間內不可用，不同之處在于設備定時維修一般可以預知擾動恢復的時間，而設備故障一般不能確定擾動的恢復時間。在處理擾動時，這兩種情況的處理過程基本相同，區別在于解除設備鎖定的時刻不同。

生產線上的設備發生故障，會導致原本安排在故障設備上的工序任務無法執行。因此，發生設備故障時，需要處理原本安排在故障設備上的工序任務。當系統發生設備故障時，調度系統會將故障設備鎖定，使其不再參與后續的工序任務排產，并查詢與故障設備加工能力相同的設備，把原本安排在故障設備上的工序任務轉移至可替代設備，生成新的調度方案交付動作規劃層執行。待排除設備故障后，解除故障設備的鎖定狀態，并生成新的排產方案。

4.2 進度異常類擾動

引起加工進度異常的擾動較多，較為常見的有資源短缺、加工時間變化等。工序任務的開始時間不能早于所需資源的最晚到達時刻，所以資源短缺往往會導致工序任務不能按照計劃時間開始，進度異常。此外，加工時間變化會導致工序任務計劃未按計劃時間結束，也會導致加工進度的異常。

工序任務的實際開始時間受資源準備時間的約束。假設某工序任務的加工需要人員、刀具、物料3種資源支持，若工裝在t1時刻到位，人員在t2時刻到位，刀具在t3時刻到位，則該工序任務最早開始時間不能早于t3。

當系統出現資源短缺類擾動導致工序任務不能按計劃時間開工時，調度系統會根據實際執行與計劃的偏差計算新排產判別值。偏差值的取值為工序任務的實際開始（結束）時間與計劃開始（結束）時間的差值。當該值超出設定閾值時，意味著偏差較大，需要重新排產。此時，根據資源管理系統的反饋獲得各個資源到位的具體時間，并重排當前的工序任務，獲得滿足資源到位時間約束的新排產方案。

加工時間變化對進度的影響主要體現在工序任務結束時間方面。加工時間變長或者變短，會導致工序任務結束時間的滯后或者提前。其中：工序任務結束時間提前會導致設備利用率降低，但對整體排產方案影響較小；工序任務時間滯后會影響下一工序任務的開始時間，若滯后時間較長，則會對排產方案產生較大影響，必須重新排產。

4.3 訂單變動類擾動

訂單變動類擾動包括插入訂單、緊急訂單和取消訂單等。

當系統接收到新的訂單時，根據系統配置的優先級規則為新任務安排優先級，并將新訂單中的工序任務加入待排產序列。調度系統會對當前所有未加工的工序任務進行重新排產，得到新的調度方案。

緊急訂單為插入訂單的一種特殊情況，要求盡快完成所插入的訂單。因此，調度系統在重新排產時，需要保證緊急訂單的工序任務被優先安排。調度系統基于優先級規則為所有工序任務排序。為保證緊急訂單的加工，應該賦予其一個較高的優先級。實際上，調度系統接收一個訂單后，會調用用戶配置的優先級規則為訂單中的工序任務賦予優先級。

取消訂單的處理過程較為簡單。當一個已排產未執行的訂單被取消時，需要在待排產的任務序列中將該訂單下的所有工序任務刪除，然后對剩余符合排產條件的訂單進行重新排產。

5 應用系統驗證

5.1 規則配置系統軟件界面

根據提出的規則可配置的柔性制造系統調度框架，開發了規則可配置的調度系統。圖4為系統的任務優先級規則管理界面。決策者可以在該界面新增或刪除優先級規則，也可以對某一條規則進行修改或重新定義。圖5為點開圖4中某條規則的“詳情”所看到的界面，可以在該界面選擇添加或刪除屬性，也可以修改各個參數的配置。

圖4 任務優先級規則管理列表

圖5 任務優先級規則配置界面

5.2 擾動案例分析

5.2.1 調度背景

某航空企業柔性制造系統由3臺臥式銑削加工中心、1個裝卸站、1臺清洗機和1臺測量機組成。現在有3個訂單a、A、B需要進行安排生產。訂單a和訂單B的工藝路徑為“裝載—銑削—清洗—測量—卸載”。訂單A只需裝載后測量，然后卸載。其中，訂單a中包含4個工件任務，訂單A中包含2個工件任務，訂單B中包含4個工件任務。

圖6為訂單執行過程中間時刻的排產甘特圖，每個矩形塊為一個工序任務，豎線為當前時刻。由圖6可知，當前時刻a訂單中的4個工件任務的前置工序任務“裝載”“銑削”“清洗”“測量”等工序已經完畢，工件a:1已經執行到“卸載”工序；訂單B尚未開始執行，訂單A已經執行到工件A:2的裝載工序。

圖6 重新排產前甘特圖

5.2.2 進度異常處理案例

按照預定排產計劃，工件a:1的“卸載”工序應該已經結束，A:2的“裝載”工序應正在執行。此時，接收到系統反饋的工件a:1的“卸載”工序由于某種原因未按計劃完成，且A:2的“裝載”工序未按計劃開始。兩者都屬于進度異常類擾動，按照前文的擾動處理方法，由于偏差值超過了設定的10 min，認為需要重排，重排后的甘特圖如圖7所示。由圖7可知，工件a:1的“卸載”工序任務時間已按照系統反饋的時間延后，工件A:2的“裝載”工序任務被推遲至當前時刻。

圖7 重排后甘特圖

5.2.3 插入訂單處理案例

假設當前時刻系統接收了一個新的訂單C，訂單C包含2個工件任務，工藝路徑為“裝載—銑削—清洗—測量—卸載”。根據擾動處理方法，需要對當前所有工序任務進行重排。由圖7可知，訂單C的2個工件任務在重排后已被安排。

5.2.4 設備故障處理案例

假設在當前時刻加工中心1發生故障導致其上的工序任務不能繼續執行，此時根據擾動處理方法，需要對當前所有工序任務進行重排，重排后的甘特圖如圖7所示。由圖7可知，系統將原本安排在加工中心1上的任務分派給了具有相同加工能力的加工中心2和加工中心3。

6 結語

本文提出了一種規則可配置的柔性制造系統自適應調度方法，解決了柔性制造系統調度的復用性問題，設計了規則可配置的調度框架，并經過生產實際驗證了有效性，同時開發了相關規則配置軟件系統。下一步將針對規則配置過程的參數優化問題開展進一步研究，期望能通過參數優化的方式配置出更貼合生產實際需要的排產規則。