基于模擬退火遺傳算法的紡紗車間調度系統

鄭小虎，鮑勁松，馬清文，周 衡，張良山

(東華大學 機械工程學院，上海 201620)

環錠紡紗是主要的紡紗方法，其具有流程長，生產速度高，設備多，布局復雜等特點。近年來，紡紗行業由勞動密集型產業漸漸地向自動化、智能化方向轉型，但是部分典型工藝仍然難以實現自動化生產。比如在并條車間，預并到并條工序之間需要依靠人來搬運條筒。引入自動引導運輸車(AGV)代替人工進行搬運是環錠紡智能工廠建設的重要手段，但引入AGV后會帶來新的生產調度問題，例如需要考慮AGV與生產設備的任務匹配、AGV的運輸時間分配等。通過制訂合理的多AGV調度計劃，可為提高企業的生產效率，降低企業生產成本提供有力支撐[1-2]。

針對AGV集成調度問題，有研究提出了一種用于求解AGV與設備集成的車間調度問題的改進花授粉算法，采用基于主成分分析法提出新的變異算子以增強算法對解空間的感知能力和跳出局部極值的能力，但該方法未考慮設備利用率[3]；為研究AGV最優調度方案和最佳AGV數量，建立使用AGV搬運的柔性車間調度模型，有學者提出了基于搬運工序、機床和AGV分配的粒子編碼方式，并結合遺傳算法和新的粒子群算法進行求解，達到最優效果[4]。

自動化環錠紡紗車間屬于多工序、多流程的流水作業車間，多個工序存在并行機，并且為紡不同成分的紗線有時會同時執行多個工藝。根據這一特點，可以將紡紗車間調度看成是混合流水車間的調度問題。和一般流水車間調度問題相比較，混合流水車間的調度問題(HFSP)要顯得更加的復雜，它是工件的排序與設備的分配問題組合[5]。HFSP是并行機的調度問題與流水車間的調度問題的結合，現已被證明是一個NP難(NP-Hard)的問題[6]。尤其是在考慮了多AGV調度問題的時候，求解難度更大。因此，如何建立合理的調度模型，并提升模型求解效率是實現紡紗車間高效運行的理論基礎。多種算法都在求解中得到應用。有研究在采用多目標離散灰狼優化算法，同時考慮最大完工時間和設備負載建立了焊接調度問題的混合整數規劃模型[7]；在研究并行批處理機的組批調度問題時，可將車間能耗考慮進來并以最小化最大完工時間為目標函數建立調度模型，而組批階段采用基于FFLPT(first-fit longest processing time)和BFLPT(best-fit longest processing time)的啟發式規則，最后在調度階段采用帶鄰域搜索的粒子群-遺傳混合算法對模型進行求解[8]；數學優化算法(TLBO算法)也可以用于求解多種車間調度問題，與其他算法對比證明，TLBO能有效求解小規模和大規模車間調度優化問題[9]；針對條筒的動態到達特性導致組批困難問題,可采用混合型蟻群算法加BATC算法對批次進行調度，以解決多產品并行批處理機調度問題[10]。針對AGV在車間裝載零件過程的路徑優化問題以及多AGV在路口避碰的調度問題，有研究采用改進蟻群算法建立以多AGV完成任務行駛路徑最短為目標函數的數學模型，并對模型進行求解[11]。目前研究含AGV的制造車間調度問題大部分集中在解決AGV的路徑規劃、任務分配等問題時將AGV運輸與生產設備調度分開考慮，但AGV的運輸任務與設備的加工任務之間的相互影響是該類調度問題的主要考量因素。

綜上所述，目前國內外對AGV生產車間協同調度方法的研究主要是采用智能優化算法進行求解，但由于目標函數不一致以及初始解的產生不一樣，從而導致各種研究方法難以得到廣泛的應用。基于批處理機的AGV紡紗車間主要生產瓶頸在于多種約束條件下的多目標優化問題，因為含有AGV的紡紗車間環境復雜，干擾因素眾多，且各種因素相互制約，不僅要考慮AGV與紡紗設備的協同關系，還要考慮AGV與物料的協同問題，因此中間的很多工藝流程需要憑人工經驗，從而導致基于批處理機的AGV紡紗車間調度模型構建難，同時也需要采用高效的求解算法提升調度效率。

本文針對基于并行機的AGV環錠紡紗車間協同調度問題，在考慮AGV與生產物料、AGV與紡紗設備之間的協同關系基礎上，將影響紡紗車間協同調度的主要因素和企業目標相結合，建立了AGV紡紗車間協同調度模型，并運用智能算法對多種約束條件下的模型進行求解，從而提高基于批處理機的AGV紡紗車間整體生產效率，促進企業更加合理配置資源，提高企業競爭力。

1 問題描述及建模

1.1 問題描述

傳統的紡紗車間調度問題主要考慮流水生產線和各條筒的加工狀態。帶有AGV的紡紗車間的生產流程主要分為3個階段，如圖1所示。

1)對棉、滌綸2種棉包進行抓包、清梳聯等工序。該階段均為自動化流水生產線，前一道工序與后一道工序之間無需通過AGV小車進行運輸，也無需考慮條筒的批處理。

2)精梳、并條、混合等工序，其中棉經過精梳、預并、條并卷、精梳等工序，滌綸經過滌并工序，當棉與滌綸都完成了上述工序后，即可按照一定的比例進行混合，混合后的產品即為棉/滌混紡纖維。

圖1 環錠紡生產工藝流程Fig.1 Production process of ring spinning

3)粗細絡和打包入庫工序。該階段需經歷粗紗、細紗、絡筒等6道工序，這些工序均為自動化流水生產線完成，只有在粗紗前，需要通過AGV小車將階段二混合后的棉/滌混紡條子搬運到粗紗機進行批處理。

通過以上分析，紡紗車間中的AGV在進行物料搬運時會面臨與紡紗設備協調的問題，尤其是當有多個紡紗設備同時生產即進行批處理時，就會產生AGV與批處理紡紗設備之間的協同調度問題。該問題可以描述為多種條筒通過AGV小車搬運，在相同批處理紡紗設備組成的平行機系統中的AGV協同調度問題。其中批處理調度又分為組批和AGV協同調度2個步驟，組批即將條筒按照一定的規則和數量分批次進行加工，AGV協同調度就是通過AGV將分批好的條筒搬運至設定好的批處理機器上進行后續的加工。

1.2 基本定義與假設

為簡化AGV與紡紗機器作業協同調度問題的模型，本文做出以下合理的形式化假設與定義:

2)有m個相同的批處理粗紗機，m=1, 2,3,…,m。粗紗機可以對上述的p種產品進行加工，且p種產品中的一個條筒在紡紗設備上的加工次數不大于1；

3)有q臺AGV小車，q=1,2, 3,…,q。AGV 可進行自主路徑規劃和導航，搬運中不同的AGV互不干擾，1臺AGV同一時刻只能運送1個條筒，且AGV運送條筒的過程中不會發生故障、電量不足等其他情況導致搬運延時的現象；

4)在同一臺紡紗設備上只有上一批條筒加工完之后，才可開始下一批條筒的加工，也即只能在設備空閑且能正常使用時才能接受加工任務(資源不能沖突)，在加工批處理過程中不允許中斷(不允許搶占)；

5)只有同一種類產品的條筒才可以組成批次進行加工,一個批次中條筒的數量不能超過批處理紡紗設備的最大容量；因為粗紗的工藝特性，對于m臺相同的粗紗機，每臺粗紗機存在多個錠位，且每個錠位需對應多個條筒；

6)一臺機器同一時刻只能加工一批條筒, 加工時間與該批條筒的數量無關,只與條筒對應的產品種類有關；

8)零時刻，所有批處理紡紗設備和AGV小車無故障，都可用。

1.3 問題建模

1.3.1 目標函數

AGV紡紗車間協同調度模型的目標函數為：

f1=min(max(Tb))

(1)

1.3.2 約束條件

與其他傳統車間調度的另一重要區別在于，AGV與紡紗設備協同批處理作業車間調度不僅要考慮工藝路線約束和加工資源約束，此外還要考慮AGV小車資源和批處理的約束，為此建立以下4個約束條件：

1)工藝約束。

cn+1-tn+1-tq≥cn

(2)

式中：cn+1和tn+1分別表示條筒n+1的加工完成時間和工序完成時間；cn表示條筒n的加工完成時間；tq表示 AGV把條筒n從上一道工序運送到下一道工序的時間。

2)加工設備資源約束。對于都要在設備m上加工2批相鄰條筒n和n+1，若n先n+1加工，加工設備資源約束表示如下：

(3)

3)AGV資源約束。

(4)

式中：q表示AGV序號；ci表示AGV運送第i個任務完成時間；ti+1表示第i+1運送任務所需時間，它等于AGV路徑規劃算法得出的路徑長度除以AGV速度。

4)批處理約束。該約束表示在有批處理加工階段，應確保此加工階段同一批內的條筒連續進行加工，即同一批內相鄰2條筒之間不允許有空閑時間，其約束表達式為：

tn+1-tn=0

(5)

2 模擬退火遺傳算法的設計

遺傳算法具有適用性強、良好的并行處理能力以及運行效率高等優點，但也存在易過早收斂于局部最優解的缺點。造成算法過早收斂主要是因為伴隨著種群不斷進化，種群中有可能會出現少數個體的適應度值遠遠超過其他個體，這些個體在選擇交叉等遺傳操作具有很強的優勢，會使種群喪失多樣式。因此，本文選擇將遺傳算法和模擬退火算法結合，模擬退火遺傳算法(SA-GA)在優化操作、原理等方面融合了模擬退火算法(SA)和遺傳算法(GA)各自的特點，使得優化過程的搜索行為更加完善，增強了全局搜索以及局部搜索能力，而且能有效控制收斂過快現象的出現，理論上能較好解決車間調度問題[11]，因此，本文考慮將模擬退火和遺傳算法進行結合的模擬退火遺傳算法，克服遺傳算法易得到局部最優解和過早收斂的問題，在提高基于批處理機的AGV紡紗車間調度系統生產效率的同時，提高生產車間設備的利用率，實現最大化企業利潤。模擬退火遺傳算法的設計步驟如下。

1)編碼與解碼。本文采用正整數編碼方式，對批處理的設備和AGV進行編碼，構成染色體的基因值，利用前文介紹的約束條件產生初始染色體作為初始解。解碼的過程是先將染色體轉化為1個有序的操作表，然后按照約束條件對各個批處理設備和AGV逐一進行篩選，從而產生調度方案。

2)確定目標函數。目標函數采取最小化最大完工時間，批處理設備平均利用率以及設備利用率(包括AGV)，設備利用率越高，通過最小化最大完工時間的多目標優化策略，使目標函數更接近實際AGV紡紗車間的需求。

3)遺傳操作。選擇步驟：對于在滿足約束條件下的解，采用精英保留策略與比例選擇方法使得適應性高的個體以更大的概率遺傳下去，從而能夠提高算法的效率。交叉步驟：對于選擇步驟后的個體之間隨機進行交叉操作并保留滿足約束條件的個體。變異步驟：采用互換操作，隨機使上一步解中的染色體中2個不同地方的基因進行互換。相關參數：設置種群的初始規模，一般取100～200；交叉概率Pc與變異概率Pm；最大迭代次數一般取50～200；SA的初始溫度，通過式t0=-(Cworst-Cbest)/ln(Pr)確定，其中Cbest與Cworst分別為開始群體的最適應和最不適應的目標值，Pr為其相對接受概率。退溫函數，即tk+1=λ×tk。λ為退溫速率；狀態接收函數，就是指通過概率min(1,exp(-Δ/tk))接受新值[12-14]。算法流程：模擬退火遺傳算法流程如圖2所示。

3 仿真實驗與評估

為驗證帶有AGV的紡紗車間協同調度模型及其求解算法，本文以無錫經緯馬山基地環錠紡紗工廠為例，基于上述建立的目標函數，分別使用模擬退火算法、遺傳算法和模擬退火遺傳算法對不同條筒數量進行對比計算，做20次隨機仿真。參數設置：種群初始規模設置為200，最大迭代次數為100，相對接受概率為0.1，交叉概率為0.66，變異概率為0.10，退溫速率為0.9，給定條筒50個，AGV 5臺，為避免偶然誤差，做20次隨機仿真，并求得平均值，得到最優解。表1、2分別示出采用模擬退火算法(SA)、遺傳算法(GA)、模擬退火遺傳算法(SA-GA)后的設備利用率、最大完工時間及其算法處理時間。

從表1可知，給定條筒數50個，在相同的設備環境下，使用模擬退火算法和遺傳算法進行調度求解時，批處理機設備平均利用率分別為52%和50%，AGV設備利用率分別為52%和58%，而在使用了模擬退火遺傳算法進行求解以后，批處理機設備平均利用率和AGV設備利用率分別為64%和69%。結果表明采用模擬退火遺傳算法，批處理機設備平均利用率和AGV設備利用率較其余2種算法至少可提升12%和11%。由此可以看出，基于模擬退火遺傳算法的AGV紡紗車間協同調度模型更能有效的提高批處理設備和AGV的利用率，減少了紡紗車間的資源浪費，從而為降低成本奠定基礎。

從表2可知，當條筒為50個時，在使用模擬退火遺傳算法對本文的調度模型進行求解時，比單獨使用模擬退火和遺傳算法的最大完工時間分別減少了1 162 s和1 619 s，并且算法計算的時間也分別減少了5 s和17 s。這是因為通過合理的調度之后，AGV在運輸的過程中減少了因不合理的協同調度而導致的空閑等待時間。另外，從結果還可以看出，模擬退火遺傳算法的計算效率雖然比模擬退火算法的低，但是仍在同一水平。如果能大大提高可行解的質量，避免遺傳算法過早的收斂而導致局部最優解的情況，還可以進一步提升其計算效率。

綜上所述，基于模擬退火遺傳算法的AGV紡紗車間協同調度方法，不僅考慮了交付期和最大完工時間的關系，同時還考慮了批處理設備和AGV設備的利用率，并且在求解的計算效率上也能滿足相關的要求，這為解決帶有AGV紡紗車間協同調度的問題提供新的思路。

表1 設備利用率Tab.1 Equipment Utilization %

表2 最大完工時間與算法處理時間Tab.2 Maximum completion time and algorithm processing time s

4 結 論

本研究針對采用自動引導運輸車(AGV)的環錠紡紗車間生產設備與AGV協同調度問題，建立了多種約束條件下調度模型并通過仿真實驗驗證了該算法效率，主要結論如下：

1)在考慮工藝、加工設備資源、AGV資源以及批處理4種約束的情況下，建立了滿足最大完工時間最小化以及設備利用率最大化的AGV紡紗車間協同調度模型。

2)設計了基于模擬退火遺傳算法的調度模型求解算法，克服了傳統遺傳算法易得到局部最優解和過早收斂的問題，該算法在提高基于批處理機的AGV紡紗車間調度系統效率的同時，還可提高生產車間設備的利用率。

3)以實際環錠紡紗工廠為對象，對提出的紡紗車間協同調度模型及其算法進行仿真驗證。實驗結果表明，當給定條筒為50個時，基于模擬退火遺傳算法的調度算法要比普通的模擬退火和遺傳算法的最大完工時間分別減少了1 162 s和1 619 s，紡紗車間的設備和AGV的利用率也分別提高了近12%和11%。