基于自適應(yīng)改進的人工蜂群算法在作業(yè)車間實時調(diào)度中的應(yīng)用

彭璐璐 嚴婷婷

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

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

1 作業(yè)車間實時調(diào)度方法設(shè)計

1.1 車間調(diào)度問題及解決設(shè)計思路

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

車間調(diào)度問題根據(jù)不同分類準則可分為多種不同類型：

（1）根據(jù)生產(chǎn)系統(tǒng)的結(jié)構(gòu)與規(guī)模進行分類，車間調(diào)度問題可以分為單車間調(diào)度問題與多車間結(jié)合調(diào)度問題。若產(chǎn)品相對單一，則僅需要單個車間就可以實現(xiàn)生產(chǎn)加工；若產(chǎn)品需要多種類的子產(chǎn)品進行組合，則需要多個單車間整合為多車間進行相應(yīng)的生產(chǎn)加工。

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

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

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

上述車間調(diào)度問題存在以下特點：

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

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

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

1.2 人工蜂群算法在作業(yè)車間實時調(diào)度中的運用

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

表1 蜜蜂行為與算法求解對應(yīng)關(guān)系表

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

圖1 傳統(tǒng)的人工蜂群算法流程圖

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

2 人工蜂群算法求解作業(yè)車間調(diào)度問題的改進

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

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

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

基于以上設(shè)計，構(gòu)建改進后的算法流程如下：

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

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

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

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

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

⑥偵察蜂：構(gòu)建一個新解法，持續(xù)算法的不斷創(chuàng)新；

⑦若是算法停下，回到最優(yōu)質(zhì)的解；否則跳轉(zhuǎn)到步驟④重新開始。

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

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

3 實驗數(shù)據(jù)分析

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

表2 公司各產(chǎn)品訂單

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

表3 各產(chǎn)品生產(chǎn)工藝及所用工時

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

表4 部分產(chǎn)品調(diào)度安排表

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

4 結(jié)語

近年來，車間調(diào)度問題受到企業(yè)的重視。群蜂計算法運用在車間調(diào)度管理中決定了企業(yè)的競爭力?；谌斯し淙核惴ǖ睦碚摷捌湓谧鳂I(yè)車間調(diào)度問題中的運營，結(jié)合遺傳算法中的變異操作和交叉操作，使得可行解的空間范圍得到擴大，同時加快了食物源的更新速度，并將兩種改進的操作運用到人工蜂群算法中，提升了算法后期收斂的速度。