粒子群遺傳算法在盤卷精整系統(tǒng)調(diào)度中的應(yīng)用

吳翔

盤卷精整系統(tǒng)是典型的柔性制造系統(tǒng)，工藝段較多、回路控制復(fù)雜、有較多生產(chǎn)約束。本文提出采用粒子群遺傳算法求解盤卷精整系統(tǒng)的調(diào)度策略問題。通過Matlab平臺設(shè)計(jì)了基于粒子群遺傳算法的盤卷精整系統(tǒng)仿真器。通過實(shí)例測試，證明了粒子群遺傳算法適用于盤卷精整系統(tǒng)的求解，具有高效率及高穩(wěn)定性。

【關(guān)鍵詞】柔性制造系統(tǒng) 盤卷精整系統(tǒng) 粒子群遺傳算法 Matlab仿真

高速線材是鋼鐵企業(yè)中附加值較高的產(chǎn)品，廣泛應(yīng)用于路橋、基建與房地產(chǎn)建設(shè)。高速線材的生產(chǎn)工藝可以分為軋制段與精整段。軋制段工藝比較獨(dú)立，設(shè)備通常都是由前至后排布，鋼材在設(shè)備間高速通過，完成軋制工藝。精整段工藝位于軋制段之后，舊的工藝為單一環(huán)路布置，處理設(shè)備依次分布在環(huán)形輸送線上，卷芯架或C型勾輸送鋼材在設(shè)備間流轉(zhuǎn)。舊工藝原理簡單、效率低，不適用于多品種、混合生產(chǎn)。近年來，業(yè)界提出多環(huán)路的盤卷精整系統(tǒng)布局，設(shè)備分布于不同的環(huán)路上，環(huán)路之間可以相互流轉(zhuǎn)。多環(huán)路盤卷精整系統(tǒng)滿足鋼鐵企業(yè)多品種、混合生產(chǎn)的需求，在增加產(chǎn)能的同時(shí)，提高設(shè)備利用率。而多環(huán)路盤卷精整系統(tǒng)是典型的柔性制造系統(tǒng)，具有處理工序多、輸送路徑多、轉(zhuǎn)運(yùn)靈活、控制策略復(fù)雜等特點(diǎn)。

由于多環(huán)路盤卷精整系統(tǒng)的這些特點(diǎn)，該類系統(tǒng)的調(diào)度問題體現(xiàn)出極高的復(fù)雜性，引起了學(xué)界的重視。學(xué)術(shù)界提出了很多不同方法。黃學(xué)文在《用蟻群算法集成求解多加工路線柔性車間調(diào)度問題》中提出用蟻群算法來求解調(diào)度問題，算法較新穎，結(jié)果也不錯(cuò)。張靜在《混合粒子群算法求解多目標(biāo)柔性作業(yè)車間調(diào)度問題》中提出混合粒子群算法，效率較高，有一定參考意義。近年來啟發(fā)式算法在該領(lǐng)域內(nèi)有很大發(fā)展.其中粒子群算法具有編碼容易實(shí)現(xiàn)、代際間存在記憶能力等優(yōu)點(diǎn)。但缺點(diǎn)是算法不穩(wěn)定容易過早收斂。遺傳算法具有運(yùn)算并行性好、編碼相對簡單，但缺點(diǎn)是收斂速度慢，效率低，容易陷入局部最優(yōu)。本文提出將粒子群算法與遺傳算法相結(jié)合，組合為粒子群遺傳算法，并將其應(yīng)用于盤卷精整系統(tǒng)的調(diào)度控制問題。

1 盤卷精整系統(tǒng)的數(shù)學(xué)模型

1.1 盤卷精整段生產(chǎn)工藝與流程

盤卷精整系統(tǒng)的產(chǎn)品有3種類型：普碳鋼、馬氏體鋼及奧氏體鋼。普碳鋼沒有經(jīng)過任何爐體緩冷，通過轉(zhuǎn)運(yùn)系統(tǒng)直接打捆、稱重，進(jìn)入倉庫。馬氏體鋼需要在鋼體表面生成一層表面晶體，所以在風(fēng)冷段后需經(jīng)過馬氏體緩冷爐，奧氏體鋼則相應(yīng)需要經(jīng)過奧氏體緩冷爐。盤卷精整系統(tǒng)主要生產(chǎn)過程如圖1所示。

從生產(chǎn)過程可以看出，整個(gè)盤卷精整系統(tǒng)有5道工藝流程，第一、第二道工序?yàn)殇摼淼木徖涮幚?，鋼卷的種類決定了前兩道工序的路徑。第三、四、五道工藝流程各有2套設(shè)備，設(shè)備功能相同，可以互用。這里設(shè)定工件總數(shù)為10，相應(yīng)的算例為10X5。按照實(shí)際的生產(chǎn)經(jīng)驗(yàn)、設(shè)計(jì)相應(yīng)工序約束矩陣J10和加工時(shí)間矩陣T10如下：

1.2 模型變量定義

為了更好描述盤卷精整系統(tǒng)的數(shù)學(xué)模型，這里約定模型的變量。如表1所示。

1.3 數(shù)學(xué)模型搭建

盤卷精整系統(tǒng)建模優(yōu)化的目標(biāo)是：在滿足生產(chǎn)約束的條件下確定所有工件的輸送路徑及投入系統(tǒng)的順序，為每臺機(jī)器確定工件的投入加工順序，為每個(gè)工件的每道工序確定加工機(jī)器，最小化盤卷精整系統(tǒng)的生產(chǎn)完工時(shí)間。

出于方便求解，便于建?？紤]。約定模型遵從如下假設(shè)：

（1）所有機(jī)器在t=0時(shí)均是正常可用的，在加工過程中不存在故障導(dǎo)致停機(jī)。

（2）不同工件之間具有相同的優(yōu)先級。

（3）所有工序在不同機(jī)器上均按照時(shí)間約束矩陣執(zhí)行，在加工過程中不存在超時(shí)或提前完成。

（4）所有機(jī)器在生產(chǎn)過程中只能加工一個(gè)工件。

（5）工件的加工過程中不允許中斷，連續(xù)完成該工藝。

（6）所有工件必須按照機(jī)器約束矩陣按照順序加工，在加工過程中不存在改變工序順序或跳過某一工序。

（7）啟動機(jī)器的時(shí)間和切換工序的時(shí)間被忽略。

在符合如上假設(shè)及約束下，建立數(shù)學(xué)模型如下：

1.3.1 數(shù)學(xué)模型的目標(biāo)函數(shù)

2 粒子群遺傳算法求解盤卷精整系統(tǒng)調(diào)度問題

2.1 粒子群遺傳算法的定義與特點(diǎn)

遺傳算法是較早提出，在業(yè)界應(yīng)用廣泛。遺傳算法的優(yōu)勢在于遺傳操作和編碼技術(shù)相對其他算法簡單，個(gè)體之間經(jīng)過交叉、變異和選擇操作后，能夠保留最優(yōu)的基因。但遺傳算法并非完美，也存在不少缺點(diǎn)：當(dāng)問題的規(guī)模較大時(shí)，搜索空間會相應(yīng)增大，算法搜索時(shí)間也會延長。

粒子群算法作為一種新的啟發(fā)式算法，由于其具有簡單的概念、容易編程實(shí)現(xiàn)、運(yùn)行效率高等優(yōu)點(diǎn)。但由于初始粒子群是隨機(jī)產(chǎn)生的，粒子群分布較廣，導(dǎo)致該算法在前期迭代中搜索效率很低。

為了克服粒子群算法和遺傳算法各自的缺點(diǎn)，發(fā)揮各自的長處。本文提出以粒子群算法為框架引入遺傳算法的選擇、交叉、變異等操作的粒子群遺傳算法。新的算法可以防止搜索的過早收斂、跳出局部最優(yōu)，在保證效率的同時(shí)找到更符合期望的最優(yōu)解。

2.2 粒子群遺傳算法的步驟

粒子群遺傳算法的基本流程如圖2所示。

2.3 粒子群遺傳算法在盤卷精整系統(tǒng)輸送控制策略的仿真

基于Matlab2.4b進(jìn)行算法編寫。針對工件總數(shù)為10的工序約束矩陣J10和加工時(shí)間矩陣T10進(jìn)行仿真，在迭代100次后得到最優(yōu)解收斂曲線如圖3所示。

從圖3可以看出，粒子群遺傳算法在算法迭代3次后就收斂于最優(yōu)解91，即所有工件完成所有工序的最短時(shí)間為91。

為了更好的比較算法性能，用遺傳算法、粒子群算法及粒子群遺傳算法基于工件總數(shù)為10的算例進(jìn)行10次計(jì)算，三種算法的仿真結(jié)果比較如表2。

遺傳算法、粒子群算法及粒子群遺傳算法均可達(dá)到91的最優(yōu)解，說明在問題規(guī)模較小時(shí)，三種算法均具有有效性。平均最少迭代數(shù)上粒子群遺傳算法最小，粒子群次之，遺傳算法最高，說明算法效率上粒子群遺傳算法最好。平均偏差上三種算法均低于3%，但是粒子群遺傳算法平均偏差為0，說明結(jié)果最穩(wěn)定。綜合來看，粒子群遺傳算法既滿足盤卷精整系統(tǒng)的調(diào)度控制問題求解，同時(shí)有更高的穩(wěn)定性。

3 結(jié)束語

針對盤卷精整系統(tǒng)的調(diào)度問題的復(fù)雜性，考慮不同算法的優(yōu)缺點(diǎn)，本文提出將粒子群算法和遺傳算法相結(jié)合，利用粒子群遺傳算法求解盤卷精整系統(tǒng)的調(diào)度策略?？紤]到粒子群算法收斂速度快的優(yōu)點(diǎn)，粒子群遺傳算法前期采用粒子群算法篩選優(yōu)化種群空間。之后植入遺傳算法，在已經(jīng)優(yōu)化過的解空間內(nèi)，利用遺傳算法的變異能力、全局收斂性等優(yōu)點(diǎn)尋找種群的最優(yōu)解。通過不同工件數(shù)量的算例測試，證明本文提出的算法能夠有效地解決盤卷精整系統(tǒng)的調(diào)度問題。

參考文獻(xiàn)

[1]吳正佳，付先旺，望蕓，劉秀鳳.求解FJSP的改進(jìn)元胞粒子群算法[J].三峽大學(xué)學(xué)報(bào)（自然科學(xué)版），2017，39（03）：84-88.

[2]黃學(xué)文，張曉彤，艾亞晴.用蟻群算法集成求解多加工路線柔性車間調(diào)度問題[J/OL].計(jì)算機(jī)集成制造系統(tǒng)，2017.

[3]屈遲文，傅彥銘，羅明山，林承徳，何偉.求解柔性作業(yè)車間調(diào)度問題的鳥群算法[J/OL].計(jì)算機(jī)工程與應(yīng)用，2017.

[4]梁文杰，王桂棠，陳志盛，吳佳毅.基于混合粒子群算法的汽車零件精沖車間調(diào)度研究[J/OL].機(jī)電工程技術(shù)，2017（09）：6-10.

[5]張靜，王萬良，徐新黎，介婧.混合粒子群算法求解多目標(biāo)柔性作業(yè)車間調(diào)調(diào)度度問題[J].控制理論與應(yīng)用，2012，29（06）：715-722.

[6]白起琛.基于混合粒子群算法多目標(biāo)柔性作業(yè)車間調(diào)度問題研究[D].哈爾濱工業(yè)大學(xué)，2010.

[7]Fattahi P，F(xiàn)allahi A （2010） Dynamic scheduling in flexible job shop systems by considering simultaneously efficiency and stability.CIRP J ManufSciTechnol 2（02）：114-123.

作者單位

上海交通大學(xué)自動化系 上海市 200240