[發(fā)明專利]一種基于標(biāo)桿協(xié)同進(jìn)化算法的柔性作業(yè)車間調(diào)度方法

在審

• 申請?zhí)枺?/td>: 202011056374.7
• 申請日: 2020-09-30
• 公開（公告）號: CN112561225A
• 公開（公告）日: 2021-03-26
• 發(fā)明（設(shè)計）人: 劉志峰;汪俊龍;張彩霞;丁國智;張路
• 申請（專利權(quán)）人: 北京工業(yè)大學(xué);北京星航機(jī)電裝備有限公司
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q50/04;G06N3/00
• 代理公司: 北京思海天達(dá)知識產(chǎn)權(quán)代理有限公司 11203
• 代理人: 沈波

本發(fā)明公開了一種基于標(biāo)桿協(xié)同進(jìn)化算法的柔性作業(yè)車間調(diào)度方法，能夠進(jìn)一步提高柔性作業(yè)車間調(diào)度問題的求解精度和計算效率，獲得更優(yōu)質(zhì)的調(diào)度方案。本發(fā)明在通用遺傳算法的框架中，引入了“標(biāo)桿”個體，“標(biāo)桿”與種群相對獨立且協(xié)同開展進(jìn)化，實現(xiàn)了算法的全局搜索和局部搜索的并行，群體進(jìn)化為全局搜索，處理的是大范圍搜索問題，目標(biāo)是搜索當(dāng)前全局較優(yōu)解；標(biāo)桿進(jìn)化，解決的是當(dāng)前最優(yōu)極值局部搜索問題，處理的是小范圍搜索，目標(biāo)是在全局較優(yōu)解中定位全局最優(yōu)解。

技術(shù)領(lǐng)域

本發(fā)明涉及一種作業(yè)車間調(diào)度技術(shù)，尤其是一種柔性車間作業(yè)調(diào)度方法，具體說是一種基于標(biāo)桿協(xié)同進(jìn)化算法的柔性車間調(diào)度方法。

背景技術(shù)

計劃排產(chǎn)是作業(yè)車間生產(chǎn)調(diào)度準(zhǔn)備環(huán)節(jié)中重要的工作。基于現(xiàn)有制造資源和成熟工藝，通過選擇工序加工設(shè)備，安排工序在設(shè)備上的加工順序，獲得設(shè)備級的車間生產(chǎn)作業(yè)計劃，指導(dǎo)后續(xù)的物料準(zhǔn)備、配送、加工等工作，是車間生產(chǎn)活動的依據(jù)。合理的作業(yè)計劃能夠有序的安排作業(yè)活動，盡量減少由于有限資源而產(chǎn)生的資源沖突或者資源浪費。然而，目前大量制造車間，仍然采用較為傳統(tǒng)的人工排產(chǎn)方式，基于計劃員的個人經(jīng)驗進(jìn)行計劃排產(chǎn)。由于車間調(diào)度安排問題是典型的組合優(yōu)化問題，依靠經(jīng)驗的人工排產(chǎn)難以獲得較優(yōu)的排產(chǎn)方案，十分容易導(dǎo)致設(shè)備沖突和設(shè)備空閑的情況出現(xiàn)，導(dǎo)致了大量等待的浪費，降低了生產(chǎn)效率，無法完全發(fā)揮制造系統(tǒng)的生產(chǎn)能力。因此，采用先進(jìn)排產(chǎn)技術(shù)代替人工排產(chǎn)勢在必行。

近年來，工業(yè)智能在生產(chǎn)系統(tǒng)各層級各環(huán)節(jié)具有廣泛的應(yīng)用，如設(shè)備運行優(yōu)化、輔助質(zhì)量分析、不規(guī)則物體分揀等。其中，將工業(yè)智能應(yīng)用于生產(chǎn)調(diào)度也是重要的方向。采用先進(jìn)啟發(fā)式算法代替人工排產(chǎn)，在可接受的時間成本下，獲得最優(yōu)或者相對最優(yōu)的調(diào)度計劃，對提高設(shè)備利用率，減少沖突和空閑，進(jìn)一步釋放產(chǎn)能，降低成本，提高企業(yè)競爭力有著十分重要的現(xiàn)實意義。采用啟發(fā)式算法獲得調(diào)度方案的質(zhì)量，依賴于算法本身的性能。因此，通過開發(fā)性能更優(yōu)，求解效率更高的先進(jìn)啟發(fā)式算法，是獲得更優(yōu)質(zhì)的車間調(diào)度方案的關(guān)鍵。

發(fā)明內(nèi)容

本發(fā)明為一種求解柔性車間調(diào)度問題的標(biāo)桿協(xié)同進(jìn)化算法。該方法通過引入“標(biāo)桿”個體，代表每代種群的通過選擇、交叉和變異進(jìn)化獲得的最優(yōu)個體，再通過“標(biāo)桿”的局部搜索，進(jìn)而在“標(biāo)桿”個體周圍精細(xì)搜索最優(yōu)個體。該方法能夠提高柔性作業(yè)車間調(diào)度問題的求解精度和效率。

本發(fā)明的技術(shù)方案和步驟如下：

步驟1：錄入問題數(shù)據(jù)，包括工件總數(shù)，設(shè)備總數(shù)，工序可選設(shè)備集，和加工時間。

步驟2：設(shè)置算法參數(shù)，包括種群規(guī)模，迭代次數(shù)，交叉概率和變異概率等。

步驟3：標(biāo)桿個體初始化，標(biāo)桿個體負(fù)責(zé)全局極值的局部搜索，因此需要保證初始標(biāo)桿個體的質(zhì)量，能夠加快收斂速度。采用了兩種啟發(fā)式規(guī)則的混合初始化方法，獲得高質(zhì)量的初始標(biāo)桿個體。

1)采用全局選擇策略確定機(jī)器選擇

柔性作業(yè)車間調(diào)度問題需要首先確定工序的機(jī)器安排。采用全局選擇策略，合理在整個調(diào)度周期內(nèi)均衡每臺設(shè)備的任務(wù)負(fù)載，確保任務(wù)分配均衡，獲得相對優(yōu)質(zhì)的機(jī)器分配方案。

2)采用加工時間最短(SPT)啟發(fā)式規(guī)則排列工序

工序安排時，按照每個工件的第一個工序到最后一個工序的順序進(jìn)行安排。不同工件的同一個工序的安排順序，采用SPT啟發(fā)式規(guī)則進(jìn)行確定。確定方法如下：計算每個待安排工序的加工時間，按照加工時間確定安排順序，加工時間越短的，越優(yōu)先安排。工序排序獲取流程如下：

子步驟1：取出所有工件的第一個工序放入待調(diào)度工序集；

子步驟2：如果待調(diào)度工序集中的工序數(shù)量大于1，轉(zhuǎn)子步驟3，否則轉(zhuǎn)子步驟4；

子步驟3：采用SPT規(guī)則對待調(diào)度工序集中的工序進(jìn)行調(diào)度優(yōu)先級排序；