[發明專利]一種基于多代理機制的智能排產設計方法和裝置

有效

• 申請號: 202110291862.4
• 申請日: 2021-03-18
• 公開（公告）號: CN113033987B
• 公開（公告）日: 2023-09-12
• 發明（設計）人: 胡中驥;李向才;鐘鑫
• 申請（專利權）人: 佳禾智能科技股份有限公司
• 主分類號: G06Q10/0631
• 分類號: G06Q10/0631;G06Q50/04
• 代理公司: 東莞市創益維捷知識產權代理事務所(普通合伙) 44944
• 代理人: 李澤清

1.一種基于多代理機制的智能排產設計方法，其特征在于，包括：

基于多代理排產算法的實現，所述基于多代理排產算法的實現用于結合制造企業現有排產情況，設置約束條件作為排產的基礎信息，包括如下步驟：

步驟S1、產線數量約束：假定制造企業有N個車間，M條產線；

步驟S2、產品和產線對應關系，通過矩陣方式描述；

步驟S3、產線產能根據產線對應的產品任務而言，在產線基礎信息的標準工時處定義；

步驟S4、工藝路線約束；

步驟S5、產線日歷是否上班及上班時長約束；

代理Agent的設置，所述代理的設置用于對各代理屬性進行定義，并設置任務代理和資源代理的動作規則，資源代理能夠接收任務的工序對其一個或幾個時間段的占用申請，接到申請后，如果某時間段能滿足工序的時間要求，則根據自身的占用情況進行判斷和匹配；

任務目標，排產和動態調度支持三大目標，即最短生產時間、產品最小庫存、最大資源平衡為調度目標；

排產計算前準備，所述排產計算前準備用于對滿足約束條件的各個代理按照設置約定規則進行數據處理；

智能排產計算，所述智能排產計算用于對于各任務目標，每個任務按照其目標不同采用不同的排產基準確定策略、進行資源申請，這個由智能排產算法進行計算得出；

排產計算前準備與智能排產計算使用的算法包括：簡單任務的多代理算法、復雜任務的多代理機制算法、采用算法庫的方式根據不同情況進行組合的算法、原子算法1：蟻群算法+原子算法2：禁忌搜索算法；

選擇的算法為原子算法1：蟻群算法+原子算法2：禁忌搜索算法：

假定有3個工件，3臺機器的排產問題如下：

n：工件總數，即n＝3；

m：機器總數，即m＝3；

Ω：總的機器集；

i，e：機器序號，i，e＝1，2，3；

j，k：工件序號，j，k＝1，2，3；

hj，第j個工件的工序總數；

l，工具序號，l＝1，2，3，…，hj；

Ω_jh：第j個工件的第h道工序的可選加工機器集；

M_jh：第j個工件的第h道工序的可選加工機器數；

O_jh：第j個工件的第h道工序；

M_ijh：第j個工件的第h道工序在機器i上加工；

p_ijh：第j個工件的第h道工序在機器i上的加工時間；

s_jh：第j個工件的第h道工序加工開始時間；

c_jh：第j個工件的第h道工序的加工完成時間；

L：一個正數；

d_j：第j個工件的交貨期；

C_j：第j個工件的完成時間；

C_max：最大完工時間；

x_ijh＝1，工序O_jh選擇機器i；x_ijh＝0，工序O_jh未選擇機器i；

y_ijhkl＝1，工序O_ijh先于O_ikl加工；y_ijhkl＝0，工序O_ijh未先于O_ikl加工；根據以上定義，可知道排產受到下列約束；

約束1：每個工件的先后順序約束：

S_jh+x_ijh*p_ijh≤c_jh

c_ijh≤S_j(h+1)

式中：i＝1，2，3；j＝1，2，3；h＝1，2，3…，hj

約束2：每個工件的完工時間約束，即每個工件的完工時間不能超過總的完工時間；

約束3：同一時刻同一臺機器只能加工一道工序；

S_jh+p_ijh≤S_kl+(1-y_ijhkl)

c_jh≤S_j(h+1)+L(1-y_iklj(h+1))

約束4：機器約束，同一時間同一道工序只能且僅能被一臺機器加工；

約束5：每一臺機器存在循環操作；

約束6：各個參數變量必須是正數；

s_jh≥0，c_jh≥0

作為評價指標的目標函數，目標函數為使得最大完工時間最小，如下：

f＝min(maxC_j)，1≤j≤n

對于組合算法：原子算法1：蟻群算法+原子算法2：禁忌搜索算法設計如下：

w：螞蟻數量；

N：算法迭代次數；

τ_i，j(t)：t時刻工序i和工序j路徑上的信息素濃度；

τ₀：各工序節點間信息素的初始濃度；

ρ：信息素揮發銀子，其中0≤ρ＜1；

Δτ_i，j(t)，本輪迭代中在工序i和工序j的路徑間灑下的信息素增量；

γ_i，j(t)，t時刻螞蟻從工序i轉移到工序j的啟發式；

α：信息素權重系數；

β：啟發式權重系數；

t時刻螞蟻從工序i轉移到工序j的概率；

螞蟻x從工序i時的禁忌池，記錄了螞蟻x選擇工序i時間走過的所有工序；

螞蟻x從工序i時的可選池，記錄了螞蟻x完成工序i時下一步可選的工序；由于工件的工序間存在順序約束，除工件的起始工序外，所有工序都必須等待前置工序完成后方可進行加工，因此可選池中包含的節點只能時禁忌池中的后續節點；

信息素更新的公式如下：

τ_i，j(t+1)＝(1-ρ)τ_i，j(t)+Δτ_i，j(t)

其中為本次迭代蟻群x在工序i和工序j之間灑下的信息素濃度增量，定義為如果螞蟻x經過路徑(i，j)，其信息素增量為螞蟻x經過的總長度的倒數，意味著螞蟻經過的總長度越長，則在該路徑上的信息素增加值越低；

螞蟻x從工序i轉移到工序j的概率計算公式可以進行任意構造，為具有下面兩個特性的函數：

a.螞蟻x從工序i到工序j的路徑上的信息素越大，越大；

b.螞蟻從工序i到工序j的機器設備上的處理時間越短，越大；

則上面算法的步驟如下：

步驟1：初始化，定義螞蟻數量，初始信息素濃度，優化目標為最大完工時間最小化，最大迭代次數N_max，當前迭代次數N，為每只螞蟻設置禁忌池和可選池；

步驟2：增加迭代次數N＝N+1，本輪循環前，螞蟻根據狀態轉移概率公式從可選池中選擇下一個加工的工序，選擇完成后，將該工序加入到禁忌池中，同時將后續工序添加到可選池中；

步驟3：信息素更新，當螞蟻完成所有工序的遍歷，即可選池為空時，按照信息素更新公式對螞蟻的搜索路徑進行信息素更新，當所有螞蟻完成搜索后，從中篩選除本輪最佳路徑并與全局最優路徑進行對比，若前者更優，則進行替換；

步驟4：輸出全局最優解，包括各設備上的加工序列以及序列上各工序的預計開始時間和結束時間。