[發(fā)明專利]一種改進(jìn)的柔性流水車(chē)間調(diào)度問(wèn)題的求解算法

在審

• 申請(qǐng)?zhí)枺?/td>: 201610890838.1
• 申請(qǐng)日: 2016-10-12
• 公開(kāi)（公告）號(hào): CN106611288A
• 公開(kāi)（公告）日: 2017-05-03
• 發(fā)明（設(shè)計(jì)）人: 范勇;胡成華
• 申請(qǐng)（專利權(quán)）人: 四川用聯(lián)信息技術(shù)有限公司
• 主分類(lèi)號(hào): G06Q10/06
• 分類(lèi)號(hào): G06Q10/06
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

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

本發(fā)明涉及作業(yè)車(chē)間調(diào)度領(lǐng)域。

背景技術(shù)

柔性流水車(chē)間調(diào)度問(wèn)題(Flexible Flow Shop Scheduling Problem，F(xiàn)FSP)是大量實(shí)際生產(chǎn)線調(diào)度問(wèn)題最常用的簡(jiǎn)化模型，是一類(lèi)重要的組合優(yōu)化問(wèn)題，已經(jīng)成為先進(jìn)制造技術(shù)實(shí)踐的關(guān)鍵。FFSP已經(jīng)被證明是一個(gè)NP難問(wèn)題，是學(xué)術(shù)界與工程界共同關(guān)注的課題。因此，對(duì)FFSP的研究具有重要的理論意義和應(yīng)用價(jià)值。

目前求解FFSP的主要方法有遺傳算法、粒子群算法、免疫克隆選擇算法#蟻群算法等，有方法采用構(gòu)造型啟發(fā)方式算法產(chǎn)生初始種群，并結(jié)合遺傳算法進(jìn)行全局搜索；還有采用遺傳算法對(duì)柔性流水車(chē)間調(diào)度問(wèn)題進(jìn)行求解和采用粒子群優(yōu)化算法針對(duì)混合約束柔性流水車(chē)間調(diào)度問(wèn)題進(jìn)行了求解；采用隨機(jī)生成所有工序順序和機(jī)器的順序的方法擴(kuò)大初始解的空間，主要解決了機(jī)器選擇結(jié)果依賴于工。但是沒(méi)有考慮機(jī)器選擇對(duì)排序調(diào)度結(jié)果的影響。

FFSP可以描述為：待加工的工件集合J＝{J₁，J₂，...J_i，...J_n}，(n為工件的個(gè)數(shù)，i∈[1，n])，機(jī)器集合為M＝｛M₁，M₂，...M_j，...M_m}(j∈[1，m])，其中λ表示工序數(shù)，S_j表示第j道工序上總機(jī)器數(shù)，m為機(jī)器數(shù)量。每個(gè)工件需要在m個(gè)并行的調(diào)度子系統(tǒng)中(m臺(tái)機(jī)器上)選擇一個(gè)進(jìn)行加工，且滿足如下的約束條件：

1)每個(gè)工件可以在不同的機(jī)器上加工；

2)每個(gè)工件一旦開(kāi)始加工就不能中斷；

3)每臺(tái)機(jī)器M_j同時(shí)只能加工一個(gè)工件J_i，每個(gè)工件J_i同時(shí)只能被一臺(tái)機(jī)器M_j加工；

4)工件的準(zhǔn)備時(shí)間和移動(dòng)時(shí)間包含在加工時(shí)間內(nèi)；

5)允許工序之間存在等待，允許機(jī)器在工件未到達(dá)時(shí)閑置。

FFSP的優(yōu)化目標(biāo)是要找出這個(gè)工件的一個(gè)加工順序，使其總完工時(shí)間最小。下面給出計(jì)算工件總完工時(shí)間的計(jì)算方法：

式中：

為第i臺(tái)機(jī)器上最后完工工件的完工時(shí)間；C_max為最后完工工件的完工時(shí)間，即排序的總時(shí)間。FFSP的優(yōu)化性能指標(biāo)為總加工費(fèi)用的值最小，調(diào)度的目標(biāo)是求解n個(gè)任務(wù)的最優(yōu)加工順序，使總完工時(shí)間C_max最小，為達(dá)到上述需求，本發(fā)明提供了一種改進(jìn)的柔性流水車(chē)間調(diào)度問(wèn)題的求解算法。

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

針對(duì)上述文獻(xiàn)研究成果存在的不足，本發(fā)明提供了一種改進(jìn)的柔性流水車(chē)間調(diào)度問(wèn)題的求解算法。

為了解決上述不足，本發(fā)明是通過(guò)以下技術(shù)方案實(shí)現(xiàn)的：

步驟1：FSSP算法定義和流程

步驟2:：重新定義粒子速度和位置的相關(guān)算子，通過(guò)分析初始機(jī)器選擇與調(diào)度總完工時(shí)間的關(guān)系，首次提出一種基于NEH算法的最短用時(shí)分解策略算法

步驟3：引入編碼矩陣和解碼矩陣來(lái)表示工件、機(jī)器以及調(diào)度之間的關(guān)系

步驟4：利用改進(jìn)離散粒子群算法進(jìn)行全局優(yōu)化

本發(fā)明有益效果是：

本算法的優(yōu)勢(shì)在于提高了粒子種群初始解的質(zhì)量，縮短粒子找到最優(yōu)解的時(shí)間；同時(shí)采用呈指數(shù)遞減的慣性權(quán)重方式，有效地避免粒子早熟收斂，增強(qiáng)了粒子前期的全局搜索能力。

附圖說(shuō)明

附圖1 FFSP的整體框架

附圖2求解FFSP的算法流程

具體實(shí)施方式

步驟1：FSSP算法定義和流程，其具體描述如下：

步驟1.1)FSSP算法定義

1)置換序列：粒子的位置為X，置換序列(i，j)的操作位交換X中第i個(gè)元素和第j個(gè)元素。

2)加法算子把后一個(gè)速度的置換序列加入到前一個(gè)速度或位置的置換序列列表的末尾。例如：假設(shè)那么

3)減法算子減法操作為粒子的全局最優(yōu)解減去粒子的個(gè)體位置或者粒子個(gè)體最優(yōu)解位置減去粒子個(gè)體位置，結(jié)果為置換序列。例如:假設(shè)A＝(3,1,2,4,5,6)，B＝(1,2,4,3,6,5)，由于A(1)＝B(4)＝3，第一個(gè)交換序列就為(1,4)，也就是說(shuō)減法結(jié)果第一個(gè)位置上為4，以此類(lèi)推，那么