基于自適應改進的人工蜂群算法在作業車間實時調度中的應用

彭璐璐 嚴婷婷

（武漢華夏理工學院,湖北 武漢 430073）

隨著社會的不斷進步，科學技術的飛速發展，制造業企業競爭激烈，逐漸被拉大的差距成為難以逾越的鴻溝[1]。企業要想展現給客戶更多好質量的產品，需優化生產車間的實時調度方案[2]，降低流水線產品的場地成本，提高客戶的滿意度。作業車間實時調度的不合理是首先要解決的問題。生由于產企業面向不同類型的客戶，但對作業車間流水線的任務安排單一，這就導致作業車間實時生產的貨物無法及時輸出而大量的堆積，大幅增加了場地成本[3]。因此，越來越多的學者將研究目標轉向了生產調度，設計了許多方法來解決車間調度問題[4]。其中，人工蜂群算法具有數據較少、設計輕松簡易、容易實現的優點，由于其適應環境需求而被廣泛使用，用于解決各種車間調度的問題[5]。

1 作業車間實時調度方法設計

1.1 車間調度問題及解決設計思路

車間調度問題是指在滿足規定準則的條件下，依照車間內現有的生產資源和基本大數據庫，對現存的資源（大小型種類機械和工作零件）進行調用和匹配，盡可能地提高作業車間的效益，并提升客戶滿意度[6]。合理高效的調度方案，不僅可以滿足不同類型企業客戶的產品需求，還可以節省人力資源和物力資源，使作業車間的輸入與輸出維持良好的動態平衡，同時還可以提高生產效率，確保車間可以準確及時地生產[7]。

車間調度問題根據不同分類準則可分為多種不同類型：

（1）根據生產系統的結構與規模進行分類，車間調度問題可以分為單車間調度問題與多車間結合調度問題。若產品相對單一，則僅需要單個車間就可以實現生產加工；若產品需要多種類的子產品進行組合，則需要多個單車間整合為多車間進行相應的生產加工。

（2）根據生產方式進行分類[8]，結合生產貨物的保密性、生產速度及生產企業的規模，車間調度問題可分為開放式實時調度與封閉式延時調度。對于開放式車間，其運作方式是“按需進行現場生產”，所有的工業產品均在開放式車間的現場進行實時生產。所有客戶企業的需求訂單均會在生產完成后直接進行運輸并送達目的地，這時車間現場不會出現產品堆積。而對于封閉式車間，其面向的主要是中小客戶企業以及大客戶企業的零散訂單，這使車間現場生產出的產品不會直接向外運輸，而是暫時存放于車間中，等待客戶來提貨。考慮到場地成本，車間管理層需要對封閉式車間的流水線產量進行控制。

（3）根據生產加工特點進行分類，考慮不同的生產需求和產品的不同性質，可以將作業車間的調度問題分為動態調度與靜態調度。對于靜態調度，其原產品輸入、流水線加工和成品包裝等流程是固定的，從而導致產品后期的輸出方式也是固定的，且信息在調動中不會有任何改變。而對于動態調度，為滿足客戶的產品需求，需對生產流程做出相應的“動態改變”，即在作業車間的實際調度中，車間具體的分配計劃和相關調度數據大都會進行改變。

（4）依據生產環境分類，考慮企業的地理位置和人文環境，可以將作業車間調度問題分為：有向性調度與無向性調度。在加工生產的過程中，有向性調度的信息是靜止不動的，也就是說產品的生產流程保持不變且持續穩定，其調度方案的可優化性較高；無向性調度是指在產品的生產輸出過程中，產品倉庫分配、產品類型等信息會受到諸多因素的影響，較難解決。

上述車間調度問題存在以下特點：

（1）煩瑣性。車間調度的流程較為煩瑣，將車間調度看成是一個大的整體，各個小分支系統間有著不可分割的聯系。在實際的生產過程中，所有車間都需要各流水線相互配合。目前，對于某一產品的生產，若車間流水線的分配不合理則會導致生產效率低下。

（2）不確定性。不確定性是指車間生產過程中存在的不穩定因素，如設備毫無預兆地發生故障、工件需要最快速度進行插入、要求交貨時間提前等突發情況。處理任務的不確定因素是不可預測的，需要做好應對問題的準備，相關機器的關鍵信息不確定、工件數量不確定、過程消息不確定等都屬于問題信息的關鍵。

（3）多因素約束。對于所有的車間調度問題，都需要考慮客戶需求、生產時間、生產效益及客戶滿意度等多方面的約束條件。

1.2 人工蜂群算法在作業車間實時調度中的運用

在人工蜂群算法中，求出和的流程算法和現實生活里蜜蜂尋找食物源有較多對應點。在人工蜂群算法中，一個食物源（蜜源）可以對應不同的可能解。而對人工蜂群（可行解）來說，結合其生物特性，需要不斷地進行覓食行為，這是一個持續并發過程，人工蜂對更美味食物源不斷地刷新以解決問題的方案需求。蜜蜂行為與算法求解對應關系表如表1所示，由表1可以看出，在傳統的人工蜂群算法中，蜜源位置表示這個式子的可行性算法，在某個位置上的食物源質量完全能夠合理地概括為這個解的匹配適應數值。

表1 蜜蜂行為與算法求解對應關系表

在生物世界中，依據任務分工，一個完整的蜂群中分為雇傭蜂與非雇傭峰兩類。而在人工蜂群算法亦存在不同任務類型的蜜蜂，且進行的所有生物行為都是為了尋求最優解，傳統的人工蜂群算法流程如圖1所示。

圖1 傳統的人工蜂群算法流程圖

領頭蜂在食物來源更新后保留了更優質的食物源，其他的蜜蜂獲得食物源訊息后，會根據“食物源信息”，以一定的概率迅速靠近新食物源，具體概率公式如式（1）所示。

2 人工蜂群算法求解作業車間調度問題的改進

對式（1）進行更新，更新方式如下：

式中r是 [-1,1]區間的隨機值，且不同于r的解，表示蜜蜂下一時刻飛行的方向，表示蜜蜂此時的位置。以這種方式更新解決，方案還是會一直依賴于舊的解決辦法。如此以往，不管是解決連續變量，還是解集的創新性和內容豐富性都會降低。此外，現如今學術界中對于車間調度問題的分析以及處理辦法基本上是相同的，還沒有徹底更換流程框架的處理辦法。大體的求解思想是將其車間的多個單一且弱相關的問題看作為一個離散組合。再通過“分而治之”的辦法進行一一求解，最后進行一定的組合分析，近似來代替全局問題。

對于車間的實時調度問題，需將問題變量進行“離散化”，使更多可行解有機會參與下一次的“迭代過程”，而不是只針對“父代”進行“子代的替換更新”。依據傳統的GA遺傳算法將“數據離散化”并進行有效更新換代。此外，對產生異化的操作和交叉進行的操作進行改善，以優化鄰域搜索范圍和力度，使求解的結構領域更廣。在人工蜂群算法中，通過對領頭蜂和跟隨蜂的尋優過程進行“類似染色體交叉與變異”等行為，可以更符合解決離散求解的車間調度。把改善過的變異操作和交叉操作使用在計算方法的指引和隨從階段，可以使指引和隨從的蜜蜂在搜索過程中范圍寬廣，食物來源也更多，解的質量也相對較好。改進方法是否成功與改變解的變動范圍有著次相關關系。因此，對解空間中所有可行解范圍的合理擴大，可以加快算法的收斂速度，同時取得最優解所需時長越短。

基于以上設計，構建改進后的算法流程如下：

①構造合適的度函數：完工時間作為可變化的量，搭建出與完工時間相反的數值；

②代碼：代碼按工序排列；

③設置算法參數：種群規模NP，最大迭代數maxCyde，蜜源搜索限制和maxMutationNum，并初始化數量；

④雇傭蜂：使用改進的變異算子更新解集并保持解集；

⑤跟隨蜂：使用改良過的交叉算法對解的子集進行下一步更新，并提前一步保留解的子集；

⑥偵察蜂：構建一個新解法，持續算法的不斷創新；

⑦若是算法停下，回到最優質的解；否則跳轉到步驟④重新開始。

此外，需要預備多套搜索方案加強領頭蜂與跟隨蜂的搜索能力。同時，還需擴增可行解的方位，故代碼必須達到結構的多種類和可變化。

實際生產中，企業合理的作業車間調度，不僅可以節約大量的人力資源，還可以節約因產品堆放帶來的場地費用和產品保護費用。因此車間的實際調度算法需有較低的時間復雜度、較強的健壯性和可行性。筆者提出的基于自適應改進的人工蜂群算法，借助了列維飛行可以有效解決企業作業車間的實時調度問題。一方面，該算法吸收了傳統人工蜂群算法的優點，另一方面，結合遺傳算法中“交叉與變異”行為的特點，可以使求出的解更優。

3 實驗數據分析

實際參與實驗的數據為某公司的流水線生產安排，具體如表2所示。為保護客戶隱私，客戶以編號形式替代其真實姓名，所有客戶公司的產品以周為單位進行劃分批量生產。

表2 公司各產品訂單

部分訂單可從庫存中直接發貨，剩余庫存數量可以滿足訂單需求。經過實地調查，解決了過程（產品在沖壓車間的生產過程）和處理時間（不考慮操作者的熟練程度）的影響，選取的3種產品的生產工藝及所用工時信息如表3所示。

表3 各產品生產工藝及所用工時

對該公司的作業車間數據進行預處理后，進行“數據改變”，使數據轉換成符合算法的數據類型，并對作業車間的實時調度進行優化，最后結合企業的實際情況，生成完整的調度方案。與原始調度的計算方法相對比效果會好很多。表3中，原始調度的完成時間大約為400 min，改進后完成時間大約為230 min。故筆者所提出的算法模型可提升企業作業車間的調度效率。部分調度安排如表4所示。

表4 部分產品調度安排表

所提出的基于自適應改進的人工蜂群算法模型一方面可以加快車間的生產速度，該調度算法可以在很大程度上削弱生產流程里的時間延遲，削弱同等數量件數的加工時長，從而提升車間加工的能力。系統生成的方案調度對開工和完工的時間更為準確，可使車間快速生產。另一方面，提升生產數據管理水平。以往車間生產的數值依賴紙質書寫記錄，部門共享信息非常緩慢。本文提出的生產大數據管理模塊將生產大數據保留在電腦中，并與各個部門共享。第一時間向調度人員轉述出車間的生產信息，進而保證車間的實際效益。

4 結語

近年來，車間調度問題受到企業的重視。群蜂計算法運用在車間調度管理中決定了企業的競爭力。基于人工蜂群算法的理論及其在作業車間調度問題中的運營，結合遺傳算法中的變異操作和交叉操作，使得可行解的空間范圍得到擴大，同時加快了食物源的更新速度，并將兩種改進的操作運用到人工蜂群算法中，提升了算法后期收斂的速度。