[發明專利]一種基于模仿學習的任務調度方法及其模型訓練方法

在審

• 申請號: 202210680738.1
• 申請日: 2022-06-16
• 公開（公告）號: CN115061795A
• 公開（公告）日: 2022-09-16
• 發明（設計）人: 李隆康;吳保元
• 申請（專利權）人: 深圳市大數據研究院;香港中文大學（深圳）
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06K9/62;G06N3/04;G06N3/08
• 代理公司: 西安迪業欣知識產權代理事務所(普通合伙) 61278
• 代理人: 校麗麗

本發明公開了一種基于模仿學習的任務調度方法及其模型訓練方法，屬于任務調度技術領域，能夠解決現有在解決排列流水車間調度問題時，難以同時滿足求解精度和計算效率要求的問題。所述方法包括：S1、獲取訓練作業樣本的特征向量；S2、利用模仿學習方法對訓練作業樣本的特征向量進行學習，得到訓練作業樣本的標準調度序列；S3、利用訓練作業樣本的特征向量和標準調度序列訓練策略網絡，得到任務調度模型。本發明用于任務調度。

技術領域

本發明涉及一種基于模仿學習的任務調度方法及其模型訓練方法，屬于任務調度技術領域。

背景技術

排列流水車間調度問題旨在尋找作業的最優置換，在制造系統中具有廣泛應用。在排列流水車間調度問題中，一臺機器(Machine)對應一項操作(Operation)，該調度問題嚴格要求所有作業(Job)都按照相同的操作順序進行處理。通常，任務調度的目標是找到作業的最佳排列，從而使得總制造時長(Make span)實現最小化。總制造時長描述了調度一系列作業時，從第一個任務開始到最后一個任務結束的總處理時間。當調度任務中只有一臺機器時，這個排列流水車間調度問題可以被輕松解決。但是對于一個多作業(n＝2)且多機器(m＝2)的調度任務來說，該任務的可行解的數量應該是作業數的階乘(n！)。據此，排列流水車間調度問題可以被視為具有NP-hard屬性的組合優化問題，該問題在多項式時間內很難解決。

近年來，機器學習已廣泛應用于組合優化問題。其中一種流行的模型就是指針網絡(Pointer Network)，它使用長短期記憶門機制(Long Short-Term Memory，簡稱LSTM)作為編碼器，使用注意力機制(Mechanism)作為解碼器。指針網絡可以將一個小的預訓練模型泛化到任意大的檢測實例。當前，用于解決調度問題的最先進的基于學習的方法，就是使用指針網絡并通過強化學習來訓練該網絡。除了基于學習的方法外，還有用于求解調度的傳統優化算法，包括數學模型和啟發式算法。數學模型是保證獲得最優解的精確方法。然而，由于調度問題的NP-hard性質，利用數學模型求解需要大量時間。而啟發式算法雖然在有限的時間內可以獲得可行的解決方案，但仍然難以同時滿足求解精度和計算效率的要求。

發明內容

本發明提供了一種基于模仿學習的任務調度方法及其模型訓練方法，能夠解決現有在解決排列流水車間調度問題時，難以同時滿足求解精度和計算效率要求的問題。

一方面，本發明提供了一種基于模仿學習的任務調度模型訓練方法，所述方法包括：

S1、獲取訓練作業樣本的特征向量；

S2、利用模仿學習方法對所述訓練作業樣本的特征向量進行學習，得到所述訓練作業樣本的標準調度序列；

S3、利用所述訓練作業樣本的特征向量和標準調度序列訓練策略網絡，得到任務調度模型。

可選的，所述S3具體包括：

S31、將所述訓練作業樣本的特征向量輸入所述策略網絡的編碼器中，獲得所述訓練作業樣本的節點向量；

S32、將所述訓練作業樣本的節點向量輸入所述策略網絡的解碼器中，獲得所述訓練作業樣本的初始調度序列；

S33、利用所述訓練作業樣本的標準調度序列和初始調度序列訓練策略網絡，得到任務調度模型。

可選的，所述模仿學習方法為行為克隆算法。

可選的，所述行為克隆算法為NEH啟發式算法。

可選的，所述編碼器為基于圖神經網絡的編碼器。

可選的，所述圖神經網絡為門控圖卷積網絡。

可選的，所述解碼器為基于注意力機制的解碼器。

可選的，所述任務調度模型的損失函數為交叉熵損失函數。