[發(fā)明專利]一種基于禁忌搜索遺傳算法的車間柔性作業(yè)調(diào)度方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202110841603.4
• 申請(qǐng)日: 2021-07-26
• 公開（公告）號(hào): CN115700647A
• 公開（公告）日: 2023-02-07
• 發(fā)明（設(shè)計(jì)）人: 胡毅;吳文江;李廉頗;周正;于皓宇;張曦陽(yáng)
• 申請(qǐng)（專利權(quán)）人: 沈陽(yáng)中科數(shù)控技術(shù)股份有限公司
• 主分類號(hào): G06Q10/0631
• 分類號(hào): G06Q10/0631;G06Q10/0633;G06N3/126;G06Q50/04
• 代理公司: 沈陽(yáng)科苑專利商標(biāo)代理有限公司 21002
• 代理人: 王倩

本發(fā)明涉及結(jié)合局部禁忌搜索策略和遺傳算法的調(diào)度優(yōu)化領(lǐng)域，具體說(shuō)是一種基于禁忌搜索遺傳算法的車間柔性作業(yè)調(diào)度方法。以最大完工時(shí)間為優(yōu)化目標(biāo)，用來(lái)生成車間柔性作業(yè)調(diào)度方案和提高生產(chǎn)效率。本發(fā)明分為兩個(gè)部分：全局搜索階段將遺傳算法的基本要素分為染色體編碼解碼、初始化種群、設(shè)置迭代遺傳算子和種群約束規(guī)則，在種群空間快速并行搜索，得到均勻分布的可行解；在局部禁忌搜索階段建立禁忌表、設(shè)置禁忌搜索長(zhǎng)度等條件，進(jìn)行局部?jī)?yōu)化解的迭代搜索，使算法擺除重復(fù)工作，避免過(guò)早陷入鄰域最優(yōu)解。本方法結(jié)合了遺傳算法和禁忌搜索的優(yōu)點(diǎn)，提高了種群空間的搜索效率，能夠在規(guī)定迭代次數(shù)內(nèi)優(yōu)化最大完工時(shí)間，可用于指導(dǎo)柔性作業(yè)車間生產(chǎn)。

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

本發(fā)明涉及結(jié)合局部禁忌搜索策略和遺傳算法的調(diào)度優(yōu)化領(lǐng)域，具體說(shuō)是一種基于禁忌搜索遺傳算法的車間柔性作業(yè)調(diào)度方法。

背景技術(shù)

車間生產(chǎn)調(diào)度技術(shù)是制造系統(tǒng)的基礎(chǔ)，其針對(duì)一項(xiàng)可分解的工作，在滿足工藝路線、交貨期等約束條件的前提下，進(jìn)行資源分配，下達(dá)生產(chǎn)指令并安排生產(chǎn)方案，以獲取產(chǎn)品成本最優(yōu)。目前解決柔性車間作業(yè)調(diào)度有兩種技術(shù)方案：一種是最優(yōu)化方法，枚舉遍歷解空間，得到精確的全局最優(yōu)解，耗時(shí)長(zhǎng)且只適用于小規(guī)模調(diào)度問(wèn)題；另一種是近似方法，雖然不能保證是最優(yōu)解，但在滿足對(duì)可行解的約束條件下，可以快速地找到調(diào)度方法，適合實(shí)際調(diào)度問(wèn)題的求解。由于精確枚舉存在耗時(shí)長(zhǎng)的缺點(diǎn)而近似方法卻能在合理時(shí)間內(nèi)求得滿意解，故通常采用后一種技術(shù)方案解決柔性調(diào)度問(wèn)題。在近似方法中，利用迭代求解計(jì)算的技術(shù)方案應(yīng)用廣泛，迭代算法可分為兩類：進(jìn)化算法和局部搜索算法。進(jìn)化算法包括遺傳算法、粒子群算法、蟻群算法等，局部搜索算法由啟發(fā)式算法變化而來(lái)，包括模擬退火算法和禁忌搜索算法等。

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

為了實(shí)現(xiàn)在規(guī)定迭代次數(shù)內(nèi)優(yōu)化最大完工時(shí)間，解決傳統(tǒng)遺傳算法局部搜索能力較差，且容易早熟收斂的缺點(diǎn)，本發(fā)明按照迭代求解和局部搜索相結(jié)合的思路，采用遺傳算法和禁忌搜索相結(jié)合的方法，以最大完工時(shí)間為優(yōu)化目標(biāo)，對(duì)染色體進(jìn)行分段編碼，經(jīng)交叉變異操作后對(duì)全局空間搜索；然后在局部空間設(shè)置禁忌表和禁忌長(zhǎng)度，避免在解空間內(nèi)重復(fù)搜索，同時(shí)接受次優(yōu)解，防止算法過(guò)早的陷入局部最優(yōu)解導(dǎo)致早熟，以此提升了算法的搜索能力和魯棒性。

本發(fā)明為實(shí)現(xiàn)上述目的所采用的技術(shù)方案是：

一種基于禁忌搜索遺傳算法的車間柔性作業(yè)調(diào)度方法，包括以下步驟：

全局搜索：將任意一種車間柔性作業(yè)的調(diào)度方案作為一條染色體，對(duì)每條染色體分別進(jìn)行種群編碼，并對(duì)編碼后的染色體進(jìn)行交叉操作和變異操作，得到最終表示工序排序的變異編碼的染色體種群；

局部禁忌搜索：基于染色體種群中的染色體構(gòu)建柔性調(diào)度方案析取圖模型，尋找關(guān)鍵路徑，在關(guān)鍵路徑上對(duì)工序進(jìn)行刪除和插入操作，完成對(duì)局部區(qū)域的一次搜索，為局部搜索設(shè)置禁忌表和禁忌長(zhǎng)度，尋找滿足禁忌表和禁忌長(zhǎng)度的所有染色體，完成車間柔性作業(yè)的調(diào)度方案的優(yōu)化。

所述種群編碼為分段編碼形式，第一段為機(jī)床選擇編碼，第二段為工序編碼；所述機(jī)床選擇編碼給每個(gè)工件的每個(gè)工序指定機(jī)床，所述工序編碼在機(jī)床選擇編碼的前提下，指定每一個(gè)機(jī)床的加工的工序順序。

所述機(jī)床選擇編碼具體為：根據(jù)柔性工作調(diào)度表，得到某一工件的某一工序?qū)?yīng)的可選加工機(jī)床的集合，在集合中選擇一臺(tái)機(jī)床作為完成該工序使用的機(jī)床，對(duì)其進(jìn)行編碼a，其編碼含義為：某一工序在可選加工機(jī)床的集合中選擇了第a臺(tái)機(jī)床，機(jī)床選擇編碼的長(zhǎng)度為所有工件工序的數(shù)目總和。