[發(fā)明專利]一種求解作業(yè)車間調(diào)度問題的混合粒子群算法

在審

• 申請(qǐng)?zhí)枺?/td>: 201610054893.7
• 申請(qǐng)日: 2016-01-27
• 公開（公告）號(hào): CN106611213A
• 公開（公告）日: 2017-05-03
• 發(fā)明（設(shè)計(jì)）人: 黃超杰;胡成華
• 申請(qǐng)（專利權(quán)）人: 四川用聯(lián)信息技術(shù)有限公司
• 主分類號(hào): G06N3/00
• 分類號(hào): G06N3/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

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

本發(fā)明涉及計(jì)算機(jī)執(zhí)行制造系統(tǒng)領(lǐng)域，具體地涉及用算法解決作業(yè)車間調(diào)度的組合優(yōu)化問題。

背景技術(shù)

制造系統(tǒng)的調(diào)度已廣泛研究了超過半個(gè)世紀(jì)，各種研究成果被提出。一些作業(yè)車間調(diào)度問題(JSP)的研究包括：工作分解，任務(wù)搶占，多執(zhí)行模式，非統(tǒng)一資源的可用性。其中，如何能讓JSP的完工時(shí)間最小，是研究的重點(diǎn)，亦是難點(diǎn)。且JSP是一種多級(jí)調(diào)度問題，是一個(gè)NP-hard問題。解決JSP復(fù)雜性包括兩個(gè)方面，一個(gè)是編碼，另一個(gè)是算法的選擇。

許多算法和方法被提出用于解決JSP。大致有以下四類：(1)數(shù)學(xué)規(guī)劃，包括整數(shù)規(guī)劃；(2)評(píng)級(jí)/線性規(guī)劃，包括分支界定法(B&B)、基于模型的優(yōu)化；(3)模糊決策和多屬性決策的辦法，包括人工神經(jīng)網(wǎng)絡(luò)(ANN)、基于知識(shí)的系統(tǒng)(KBS)；(4)優(yōu)化方法和人工智能技術(shù)，包括禁忌搜索(TS)、遺傳算法(GA)、粒子群優(yōu)化(PSO)，模擬退火(SA)、蟻群優(yōu)化(ACO)等。

粒子群算法(Particle Swarm Optimization，PSO)是一種全局搜索的群體智能算法。它原理簡(jiǎn)單，算法實(shí)現(xiàn)也相對(duì)容易，運(yùn)行效率高。但是，粒子群算法容易陷入局部極小，并且搜索精度也不高。

模擬退火算法(Simulated Annealing，SA)是從物理退火過程的啟發(fā)中提出的一種單點(diǎn)搜索算法，該算法成功應(yīng)用于組合優(yōu)化問題。它具有跳出局部最優(yōu)和搜索精度高的優(yōu)點(diǎn)。

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

針對(duì)現(xiàn)有技術(shù)中存在的上述不足之處，本發(fā)明提出了一個(gè)結(jié)合SA算子的混合PSO算法。

本發(fā)明的目的則是克服現(xiàn)有技術(shù)中存在的：迭代局部搜索容易陷入局部最優(yōu)；搜索空間將產(chǎn)生近似解，而不是精確解；隨著問題規(guī)模的擴(kuò)大，搜索時(shí)間顯著提高的問題。

本發(fā)明為實(shí)現(xiàn)上述目的所采用的技術(shù)方案是：一種求解作業(yè)車間調(diào)度問題的 混合粒子群算法，該算法的實(shí)施過程如下：

步驟1：初始化算法參數(shù),包括PSO粒子的數(shù)目、位置和速度等信息。

步驟2：執(zhí)行改進(jìn)的PSO算法并更新粒子的位置和速度轉(zhuǎn)移。

步驟3：執(zhí)行模擬退火算子并更新粒子信息。

步驟4：執(zhí)行干擾算子，如果循環(huán)中全局最優(yōu)解保持不變，保留原始粒子信

息，并生成一個(gè)隨機(jī)粒子。

步驟5：判斷是否到達(dá)停止條件，是則返回最優(yōu)解，否則返回步驟2。

本發(fā)明的有益效果是：1.增加干擾算子使搜索避免陷入局部最優(yōu)；2.增加了粒子的多樣性，提高了尋找最優(yōu)解的概率；3.快速收斂，顯著減少了搜索時(shí)間。4.結(jié)合退火算子產(chǎn)生全局最優(yōu)解。

附圖說明

圖1為該混合粒子群算法流程圖。

圖2為PSO算法流程圖

圖3為編碼排列示例圖。

圖4為SA算子流程圖。

圖5為干擾算子示意圖。

具體實(shí)施方式

本發(fā)明的目的是使JSP中完工時(shí)間最小，因此本發(fā)明利用模擬退火算法(SA)具有跳出局部最優(yōu)和搜索精度高的優(yōu)點(diǎn)，將模擬退火算法與粒子群算法結(jié)合，不僅增加了粒子的多樣性，提高了尋找最優(yōu)解的概率，而且使各種粒子可以找到至少兩個(gè)局部最優(yōu)解，再結(jié)合退火算子在找到的多個(gè)局部最優(yōu)解中，產(chǎn)生全局最優(yōu)解。同時(shí)，該混合PSO算法由于粒子的特性而快速收斂，顯著減少了搜索時(shí)間。

作業(yè)車間調(diào)度問題(JSP)可以描述為假設(shè)存在n個(gè)工件{J_i|(i＝1，2，…，n)}在m臺(tái)機(jī)器{M_k(k＝1，2，...，m)}上加工，O_ik表示工件J_{在設(shè)備Mk上加工的工序。首先確定每個(gè)工件的具體操作和給出每個(gè)序列的數(shù)據(jù)。本發(fā)明預(yù)先建立了一些假設(shè)：(1)每個(gè)工件的處理序列已被確定；(2)各機(jī)器至多在同一時(shí)刻處理一個(gè)工件，并且一旦開始工作就不能被終止(3)工件相互獨(dú)立，即每個(gè)工件可以以任何順序進(jìn)行處理；(4)所有工件都是在時(shí)刻0等待被處理。}

下面，結(jié)合圖1-圖5對(duì)本發(fā)明詳細(xì)說明。

一種求解作業(yè)車間調(diào)度問題的混合粒子群算法，其具體執(zhí)行步驟結(jié)合圖5如下：

步驟1：初始化算法參數(shù),包括PSO粒子的數(shù)目、位置和速度等信息。

步驟1.1：確定粒子的數(shù)目，并按照編碼排列規(guī)則初始化其位置和速度。

步驟1.2：確定變量，包括PSO更新方程的參數(shù)，如ω，c₁，c₂；模擬退火