[發明專利]面向動態到達任務的在線調度方法

有效

• 申請號: 202010102951.5
• 申請日: 2020-02-19
• 公開（公告）號: CN111260254B
• 公開（公告）日: 2022-07-26
• 發明（設計）人: 張忠山;王濤;沈大勇;宋彥杰;陳宇寧;何磊;陳盈果;劉曉路;呂濟民
• 申請（專利權）人: 中國人民解放軍國防科技大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06
• 代理公司: 長沙國科天河知識產權代理有限公司 43225
• 代理人: 董惠文

1.一種面向動態到達任務的在線調度方法，其特征在于，包括以下步驟：

步驟1：在系統運行時間范圍內，將系統運行過程分為多個運行階段，在每個運行階段中有系統執行的任務序列，相鄰運行階段之間不存在交叉的任務；

步驟2：將所述每個運行階段分為穩定運行階段和決策調度階段，在所述穩定運行階段，系統執行上一運行階段中決策調度階段決策的任務序列，在所述決策調度階段，將在當前運行階段處于穩定運行階段中系統收集到的新測控任務請求，插入到下一穩定運行階段的原任務序列中形成新任務序列，并對新任務序列進行調整；

步驟3：在下一穩定運行階段執行調整后的所述新任務序列，完成動態到達任務的在線調度；所述決策調度階段包括預調度階段和調度階段，在所述預調度階段對前一個穩定運行階段中系統收集到的新測控任務請求進行預處理，在所述調度階段，將經過預處理的新測控任務插入到下一穩定運行階段的任務序列中形成新的任務序列，并對新任務序列進行調整；所述將經過預處理的新測控任務插入到下一穩定運行階段的任務序列中形成新的任務序列的方法是快速插入方法；所述快速插入方法是：

步驟2.1：在所述運行階段時間范圍內，判斷新測控任務是否可以插入到下一穩定運行階段的任務序列中，如果可以直接插入則將新測控任務插入到原任務序列中形成新的任務序列后輸出；

步驟2.2：如果不能直接插入，則將任務序列中所有持續時間短于新測控任務的任務，按照持續時間長短從小到大進行排列，依次累加直至多個任務持續時間和超過新測控任務的持續時間，將此時累加的多個任務的重要性程度求和，并將多個任務的重要性程度求和結果作為所述新測控任務的最小重要程度和；

步驟2.3：比較新測控任務的最小重要程度和與超過新測控任務持續時間的最短原任務重要性程度，選擇值較小的作為被替換任務，將被替換的任務放入被刪除的任務集合；

如果被替換的任務為超過新任務持續時間的最短原任務，則轉步驟2.4；

如果被替換的任務為計算新測控任務的最小重要程度和的多個任務，則轉步驟2.5；

步驟2.4：將超過新任務持續時間的最短原任務的開始時間作為新測控任務的開始時間；

步驟2.5：將多個任務中處在最前位置的任務開始時間作為新測控任務的開始時間，按照滿足最小間隔時間要求順序移動序列內排在新測控任務之后的原有任務。

2.根據權利要求1所述的方法，其特征在于，步驟2中對新任務序列進行調整的方法是鄰域搜索方法。

3.根據權利要求2所述的方法，其特征在于，所述鄰域搜索方法為：

1)鄰域搜索算法待優化的任務集合包括兩部分，一部分是從任務序列中刪除被替換的任務構成需要修復的任務集合另一部分是已插入新任務后的任務序列

2)依次將待修復集合中的任務從前至后嘗試插入任務序列為中，若能插入則得到新任務序列的執行方案，計算該新任務序列的目標函數值，比較該新任務序列的目標函數值與當前鄰域搜索過程最優函數值，如果新任務執行方案的目標函數值高于鄰域搜索過程當前最優函數值，則將當前的任務插入新任務序列并保存；否則，繼續搜索下一個插入位置；

3)在完成將待修復集合中的所有任務搜索后，輸出任務序列作為最終的任務執行方案。

4.根據權利要求1所述的方法，其特征在于：步驟2.1中，如果存在多個可以插入的位置，則將任務插入到第一個可以執行任務的位置。

5.根據權利要求1-4中任一項所述的方法，其特征在于，相鄰運行階段之間設置觸發條件，滿足觸發條件時衛星測控系統將從一個運行階段轉入另一個運行階段。

6.一種計算機設備，包括存儲器和處理器，所述存儲器存儲有計算機程序，其特征在于，所述處理器執行所述計算機程序時實現權利要求1至5中任一項所述方法的步驟。

7.一種計算機可讀存儲介質，其上存儲有計算機程序，其特征在于，所述計算機程序被處理器執行時實現權利要求1至5中任一項所述的方法的步驟。