[發明專利]一種基于動態約束矩陣的粒子群調度方法

有效

• 申請號: 201910732911.6
• 申請日: 2019-08-09
• 公開（公告）號: CN110533301B
• 公開（公告）日: 2022-08-23
• 發明（設計）人: 史彥軍;胡芳億;潘耀輝;沈衛明
• 申請（專利權）人: 大連理工大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06N3/00
• 代理公司: 大連理工大學專利中心 21200
• 代理人: 溫福雪;侯明遠

1.一種基于AGV約束矩陣的粒子群調度方法，其特征在于，步驟如下：

第一步：多約束模型建立

工位有N個工件調度任務；工件調度任務的執行有先后順序，一共有N個調度任務，任務i，j分別代表N個任務中的任意任務，任務j的緊前任務集合表示為P_j，每一個任務有多種執行模式來完成工件調度任務，執行模式集合表示為M_j＝{1，2，3，...，|M_j|}，其中|M_j|表示任務j的總模式數；

有K種類型的AGV，AGV集合表示為R＝{R₁，R₂，...，R_K}，其中R_k為第k種型號AGV的數量；

任務j在執行模式M_j下所消耗的第k種AGV的數量為r_jmk，所消耗時間為t_jm；生產調度問題的目標是通過確定任務執行順序Y＝{Y₁，...，Y_N}，相應的執行模式M＝{M₁，...，M_N}，以及任務開始時間S＝{S₁，...，S_N}；使得在滿足多種約束的情況下，達到任務總消耗時間最小的優化目標；

f(x)＝max(f₁，...，f_N) (2.1)

其中，f_j為第j個任務的完成時間，j＝1，...，N；x_jm為二值標量，任務j執行模式m時為1；

式(2.1)為目標函數，實現完成AGV消耗的總時間最??；

式(2.2)表示AGV進行工件調度時，一個任務只能由一種模式完成；

式(2.3)保證了任務之間的優先關系，表示AGV進行任意工件調度任務必須在其所有的緊前調度任務結束之后才能開始；

式(2.4)中At為時間段[t-1，t]內正在執行的任務集合，該式保證單位時間內使用的AGV數量不超過其總量；

第二步：求解模型

2.1構建動態約束矩陣

對于順序約束，采用N×N的二維動態矩陣表示各個工件調度任務之間的約束關系；

當任務i是任務j的緊前任務，則矩陣的第i行第j列賦值為1，否則為0；順序約束矩陣是動態變化的，當第i列元素之和為0，說明任務i沒有緊前任務或者緊前任務已經被安排，任務i此時能被執行；為防止已經執行的任務i被重復選中，第i列中的所有元素全部賦值為1；而且當任務i執行完畢，則第i行除第i列元素全部賦值為0，表示其后續任務的緊前任務約束解除；

對于資源約束，采用K×Z的二維動態矩陣表示不同類型AGV實時可用數量，Z值為每個任務完成時間相加之和；矩陣中的每個元素代表生產調度過程每種類型的AGV在相應時間段的可用數量，其中r_kq表示第k種類型AGV在時間T＝q-1至T＝q間剩余可用量，其中，q＝1，...，Z；

2.2種群初始化

種群初始化涉及粒子的編碼和解碼操作；種群粒子集合為C，迭代更新次數為t_max；

2.2.1編碼

編碼為了初始化和更新粒子群，使每個粒子以2×N維向量X_c(t)＝{y_c1(t)，...，y_cN(t)，m_c1(t)，...，m_cN(t)}表示，該向量表示一種任務調度方案，這種編碼方式滿足公式(2.2)；其中，前N維的數值代表對應任務的優先級，c表示為第c個粒子，t表示第t次更新迭代；初始化時隨機產生[0，1]之間的實數，通過比較優先級值的大小，決定任務執行的優先順序，優先級值大的任務將優先執行；后N維表示對應任務的執行模式，初始化時隨機產生不大于任務模式個數的正整數；

2.2.2解碼

解碼為了求解每個粒子代表的任務調度方案和公式(2.1)所對應的目標函數；其中調度方案包括任務執行順序、任務執行模式和任務最早開始的可行時間；從X_c(t)＝{y_c1(t)，...，y_cN(t)，m_c1(t)，...，m_cN(t)}中選擇可執行任務中優先級y_ci(t)最高的任務i以及對應的任務模式m_ci(t)，通過公式(2.3)計算該任務所有緊前任務的最遲完成時間當做該任務的最早開始時間，通過遍歷求得每個任務的執行時間；最后通過公式(2.1)計算每個粒子對應的目標函數值；

2.3粒子更新

粒子更新首先要通過比較每個粒子對應的目標函數值獲得粒子歷史最優位置和粒子種群最優位置X^G(t)；

對X_c(t)＝{y_c1(t)，...，y_cN(t)，m_c1(t)，...，m_cN(t)}，改進的粒子更新規則分為兩部分：

第一部分是對粒子前N位優先級值的更新，優先級值通過公式(3.1)更新速度V_c(t)，通過公式(3.2)更新優先級值X_c(t)；

X_c(t+1)＝X_c(t)+V_c(t+1) (3.2)

其中：w為對自身當前信息的依賴，c₁為對自身經驗的依賴，c₂為對社群信息的依賴情況，rand為[0，1]之間的隨機數；

另一部分是對粒子后N位模式值的更新，對X_c(t)的每位，以θ∈[0，1]的概率用相應的值進行替換；再對X_c(t)以μ∈[0，1]的概率用X^G(t)進行替換；

2.4變異

為了避免陷入局部最優，粒子更新完后以γ∈[0，1]的概率對每位用符合取值范圍的隨機數進行替換。