[發明專利]一種基于遺傳算法的多資源并行任務高級計劃排程方法

有效

• 申請號: 202110008188.4
• 申請日: 2021-01-05
• 公開（公告）號: CN113139710B
• 公開（公告）日: 2022-03-08
• 發明（設計）人: 董洪亮;張鋒
• 申請（專利權）人: 中國電子科技集團公司第二十九研究所
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q10/10;G06N3/12
• 代理公司: 成都九鼎天元知識產權代理有限公司 51214
• 代理人: 賈年龍

1.一種基于遺傳算法的多資源并行任務高級計劃排程方法，其特征在于，包括以下步驟：

步驟1、獲取所有待排程任務對應的工序運行邏輯、執行周期、資源需求和資源庫；其中，資源需求包括儀器、工位和人員，資源庫包括儀器庫、工位庫和人員庫；

步驟2、根據工序運行邏輯生成鄰接矩陣Sim；

步驟3、確定多資源并行任務高級計劃排程的約束條件，構建高級計劃排程約束表達式；

步驟4、進行染色體編碼，并隨機產生一定規模的初始種群，令n＝1；

步驟5、從種群中選取一條染色體，根據染色體的編碼信息，按照鄰接矩陣Sim的解析流程，得到多資源并行任務的待執行工序順序；

步驟6、按照資源需求邏輯依次為待執行工序分配資源，分別記錄各個任務的執行總時間；

步驟7、判斷n是否滿足閾值條件，若不滿足，則n＝n+1，執行下一步；否則跳轉至步驟13；

步驟8、按照遺傳算法進化規則，構建種群目標函數F(i)，依據基于排序的適應度分配方法為每條染色體分配適應度值；

步驟9、采用輪盤賭的選擇策略，從種群中隨機選取設定比例的染色體進入下一步遺傳操作；

步驟10、從篩選出的染色體中每兩條為一組，作為父代染色體，判斷是否滿足交叉條件，若滿足，則進行交叉；否則對下一組染色體進行判斷，直至遍歷完成，構成新的子代種群，執行下一步；

步驟11、在子代種群中逐條遍歷染色體，判斷是否滿足變異條件，若滿足，則進行變異；否則判斷下一條染色體是否滿足變異條件，遍歷完成構成新的子代種群，執行下一步；

步驟12、判斷子代種群染色體與初始種群染色體個數差值h，從父代中選取適應度值高的h條染色體作為最優個體，不進行遺傳操作，直接加入到新種群當中，轉到步驟5；

步驟13、輸出種群最優解，解碼輸出每道工序對應的人員、儀器、工位、開始結束時間，多資源并行任務高級計劃排程結束。

2.根據權利要求1所述的基于遺傳算法的多資源并行任務高級計劃排程方法，其特征在于，所述步驟2中鄰接矩陣Sim生成過程如下：

步驟2.1、獲取工序運行邏輯關系表，設工序個數為k，從表中提取出工序號、輸出工序和輸入工序構成新的二維字符串矩陣；

步驟2.2、將二維字符串矩陣轉換成被計算機識別的數值矩陣形成一個新的矩陣E(k，3)；

步驟2.3、生成一個k+1行、k列的零矩陣Sim，令j＝1；

步驟2.4、判斷所有工序是否循環完畢，如果是，則鄰接矩陣生成完畢，否則，判斷輸入工序是否為空，如果是，則將Sim第一行對應工序列賦值為1，否則，進入步驟2.5；

步驟2.5、判斷輸出工序是否為空，如果是，則j＝j+1，進入步驟2.4，否則將Sim對應j+1行的輸出工序列賦值為1，j＝j+1，進入步驟2.4。

3.根據權利要求2所述的基于遺傳算法的多資源并行任務高級計劃排程方法，其特征在于，所述步驟3構建高級計劃排程約束表達式如下：

a.同一個人員在同一時刻最多執行一道工序；

b.同一個人員必須當前工序執行結束才能執行下一工序；

c.相同任務下的工序間具有緊前約束關系，即同一任務緊前工序執行結束才可以執行下一道工序；

d.所有工序在額定時間內完成；

其中，表示在人員O的操作下，任務I_c工序J_f的執行時間；表示在人員O的操作下，任務I_c工序J_f的開始時間；T_cf表示任務I_c工序J_f的額定執行時間；T表示時間的集合；表示決策變量，表示在t時刻，任務I_c工序J_f由人員O來執行，則否則