[發(fā)明專利]一種基于動態(tài)約束矩陣的粒子群調(diào)度方法

有效

• 申請?zhí)枺?/td>: 201910732911.6
• 申請日: 2019-08-09
• 公開（公告）號: CN110533301B
• 公開（公告）日: 2022-08-23
• 發(fā)明（設(shè)計）人: 史彥軍;胡芳億;潘耀輝;沈衛(wèi)明
• 申請（專利權(quán)）人: 大連理工大學(xué)
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06N3/00
• 代理公司: 大連理工大學(xué)專利中心 21200
• 代理人: 溫福雪;侯明遠(yuǎn)

本發(fā)明屬于智能優(yōu)化算法領(lǐng)域，涉及一種基于動態(tài)約束矩陣的粒子群調(diào)度方法。本發(fā)明將生產(chǎn)調(diào)度任務(wù)由多臺不同種類不同數(shù)量的AGV進(jìn)行物料、零件等工件的運輸，加入順序約束、資源約束和多組合模式，抽象出具體模型，根據(jù)生產(chǎn)調(diào)度問題各約束的特征，在原始粒子群算法的基礎(chǔ)上，增加AGV動態(tài)約束矩陣，并更改相應(yīng)的粒子編碼、解碼和更新規(guī)則，使粒子群優(yōu)化算法更加適應(yīng)多約束生產(chǎn)調(diào)度問題的求解。本發(fā)明改進(jìn)了相應(yīng)的粒子編碼、解碼和更新規(guī)則，使粒子群優(yōu)化算法解決生產(chǎn)調(diào)度問題。與常見的懲罰函數(shù)法處理約束辦法相比，收斂速度更快，求得的調(diào)度方案任務(wù)耗時更少。

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

本發(fā)明屬于智能優(yōu)化算法領(lǐng)域，涉及一種基于動態(tài)約束矩陣的粒子群調(diào)度方法。

背景技術(shù)

粒子群優(yōu)化算法是一種基于群體智能的優(yōu)化方法。從隨機初始解出發(fā)，通過迭代追隨每代種群搜索到的最優(yōu)值來尋找全局最優(yōu)解。粒子群諸如因其并行性收斂速度快，超參數(shù)少，基本架構(gòu)簡單容易鑲嵌其它算子等優(yōu)點，是學(xué)術(shù)界、工業(yè)界研究的熱點算法。

近年來，一些學(xué)者將粒子群優(yōu)化算法推廣到約束優(yōu)化領(lǐng)域。關(guān)鍵點在于如何處理好約束，即解的可行性。但目前利用粒子群優(yōu)化算法求解多約束優(yōu)化問題理論成果還不成熟，約束處理辦法主要有兩類，第一類是利用懲罰函數(shù)將約束問題轉(zhuǎn)換成無約束問題，缺點是使目標(biāo)函數(shù)變得復(fù)雜，而且使優(yōu)化過程變得不連續(xù)；第二類是將粒子的搜索空間限制在可行解范圍內(nèi)，缺點是對大多數(shù)約束優(yōu)化問題，初始可行解區(qū)域是很難確定的。

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

本發(fā)明提出了一種基動態(tài)約束矩陣的粒子群調(diào)度方法，通過提出動態(tài)動態(tài)約束矩陣的構(gòu)造方法，并改進(jìn)相應(yīng)的粒子編碼、解碼和更新規(guī)則，使粒子群優(yōu)化算法解決生產(chǎn)調(diào)度問題。

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

一種基于動態(tài)約束矩陣的粒子群調(diào)度方法，步驟如下：

生產(chǎn)調(diào)度任務(wù)由多臺不同種類不同數(shù)量的AGV進(jìn)行物料、零件等工件的運輸，以完成相應(yīng)的生產(chǎn)任務(wù)，由于生產(chǎn)實際的要求，需要考慮下述三個屬性：

(1)順序約束：各調(diào)度任務(wù)之間存在優(yōu)先級，即不同調(diào)度任務(wù)的工件有加工順序關(guān)系；

(2)資源約束：不同類型AGV的數(shù)量是有限的；

(3)多組合模式：調(diào)度任務(wù)可能需要同時使用多臺不同類型的AGV完成調(diào)度，并且可以采用多種AGV組合模式，每種模式完成調(diào)度任務(wù)所花費的 時間可能是不同的。

以完成所有的調(diào)度任務(wù)耗時最短為優(yōu)化目標(biāo)，求出粒子的最優(yōu)值即最優(yōu)的調(diào)度方案。在調(diào)度方案中需要確定每個任務(wù)的執(zhí)行順序、執(zhí)行時間和執(zhí)行模式。

第一步：多約束模型建立

工位有N個工件調(diào)度任務(wù)。工件調(diào)度任務(wù)的執(zhí)行有先后順序，一共有N個調(diào)度任務(wù)，任務(wù)i，j分別代表N個任務(wù)中的任意任務(wù)。設(shè)有順序約束，也就是每個任務(wù)都有自己的緊前任務(wù)，任務(wù)j的緊前任務(wù)集合表示為P_j，只有當(dāng)P_j中的任務(wù)全部完成，任務(wù)j才能開始執(zhí)行。每一個任務(wù)有多種執(zhí)行模式來完成工件調(diào)度任務(wù)，模式集合表示為M_j＝{1，2，3，...，|M_j|}，其中|M_j|表示任務(wù)j的總模式數(shù)。