基于模擬退火遺傳算法的紡紗車間調(diào)度系統(tǒng)

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

(東華大學(xué) 機(jī)械工程學(xué)院，上海 201620)

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

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

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

綜上所述，目前國內(nèi)外對AGV生產(chǎn)車間協(xié)同調(diào)度方法的研究主要是采用智能優(yōu)化算法進(jìn)行求解，但由于目標(biāo)函數(shù)不一致以及初始解的產(chǎn)生不一樣，從而導(dǎo)致各種研究方法難以得到廣泛的應(yīng)用。基于批處理機(jī)的AGV紡紗車間主要生產(chǎn)瓶頸在于多種約束條件下的多目標(biāo)優(yōu)化問題，因?yàn)楹蠥GV的紡紗車間環(huán)境復(fù)雜，干擾因素眾多，且各種因素相互制約，不僅要考慮AGV與紡紗設(shè)備的協(xié)同關(guān)系，還要考慮AGV與物料的協(xié)同問題，因此中間的很多工藝流程需要憑人工經(jīng)驗(yàn)，從而導(dǎo)致基于批處理機(jī)的AGV紡紗車間調(diào)度模型構(gòu)建難，同時也需要采用高效的求解算法提升調(diào)度效率。

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

1 問題描述及建模

1.1 問題描述

傳統(tǒng)的紡紗車間調(diào)度問題主要考慮流水生產(chǎn)線和各條筒的加工狀態(tài)。帶有AGV的紡紗車間的生產(chǎn)流程主要分為3個階段，如圖1所示。

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

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

圖1 環(huán)錠紡生產(chǎn)工藝流程Fig.1 Production process of ring spinning

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

通過以上分析，紡紗車間中的AGV在進(jìn)行物料搬運(yùn)時會面臨與紡紗設(shè)備協(xié)調(diào)的問題，尤其是當(dāng)有多個紡紗設(shè)備同時生產(chǎn)即進(jìn)行批處理時，就會產(chǎn)生AGV與批處理紡紗設(shè)備之間的協(xié)同調(diào)度問題。該問題可以描述為多種條筒通過AGV小車搬運(yùn)，在相同批處理紡紗設(shè)備組成的平行機(jī)系統(tǒng)中的AGV協(xié)同調(diào)度問題。其中批處理調(diào)度又分為組批和AGV協(xié)同調(diào)度2個步驟，組批即將條筒按照一定的規(guī)則和數(shù)量分批次進(jìn)行加工，AGV協(xié)同調(diào)度就是通過AGV將分批好的條筒搬運(yùn)至設(shè)定好的批處理機(jī)器上進(jìn)行后續(xù)的加工。

1.2 基本定義與假設(shè)

為簡化AGV與紡紗機(jī)器作業(yè)協(xié)同調(diào)度問題的模型，本文做出以下合理的形式化假設(shè)與定義:

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

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

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

5)只有同一種類產(chǎn)品的條筒才可以組成批次進(jìn)行加工,一個批次中條筒的數(shù)量不能超過批處理紡紗設(shè)備的最大容量；因?yàn)榇旨喌墓に囂匦?，對于m臺相同的粗紗機(jī)，每臺粗紗機(jī)存在多個錠位，且每個錠位需對應(yīng)多個條筒；

6)一臺機(jī)器同一時刻只能加工一批條筒, 加工時間與該批條筒的數(shù)量無關(guān),只與條筒對應(yīng)的產(chǎn)品種類有關(guān)；

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

1.3 問題建模

1.3.1 目標(biāo)函數(shù)

AGV紡紗車間協(xié)同調(diào)度模型的目標(biāo)函數(shù)為：

f1=min(max(Tb))

(1)

1.3.2 約束條件

與其他傳統(tǒng)車間調(diào)度的另一重要區(qū)別在于，AGV與紡紗設(shè)備協(xié)同批處理作業(yè)車間調(diào)度不僅要考慮工藝路線約束和加工資源約束，此外還要考慮AGV小車資源和批處理的約束，為此建立以下4個約束條件：

1)工藝約束。

cn+1-tn+1-tq≥cn

(2)

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

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

(3)

3)AGV資源約束。

(4)

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

4)批處理約束。該約束表示在有批處理加工階段，應(yīng)確保此加工階段同一批內(nèi)的條筒連續(xù)進(jìn)行加工，即同一批內(nèi)相鄰2條筒之間不允許有空閑時間，其約束表達(dá)式為：

tn+1-tn=0

(5)

2 模擬退火遺傳算法的設(shè)計

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

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

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

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

3 仿真實(shí)驗(yàn)與評估

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

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

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

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

表1 設(shè)備利用率Tab.1 Equipment Utilization %

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

4 結(jié) 論

本研究針對采用自動引導(dǎo)運(yùn)輸車(AGV)的環(huán)錠紡紗車間生產(chǎn)設(shè)備與AGV協(xié)同調(diào)度問題，建立了多種約束條件下調(diào)度模型并通過仿真實(shí)驗(yàn)驗(yàn)證了該算法效率，主要結(jié)論如下：

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

2)設(shè)計了基于模擬退火遺傳算法的調(diào)度模型求解算法，克服了傳統(tǒng)遺傳算法易得到局部最優(yōu)解和過早收斂的問題，該算法在提高基于批處理機(jī)的AGV紡紗車間調(diào)度系統(tǒng)效率的同時，還可提高生產(chǎn)車間設(shè)備的利用率。

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