[發(fā)明專利]一種縮短應急響應時間的雙平行機調度方法

在審

• 申請?zhí)枺?/td>: 202010940550.7
• 申請日: 2020-09-09
• 公開（公告）號: CN114035910A
• 公開（公告）日: 2022-02-11
• 發(fā)明（設計）人: 鄭斐峰;徐寅峰;劉明;張娥;隋楊
• 申請（專利權）人: 東華大學
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 徐州拉沃智佳知識產權代理有限公司 32455
• 代理人: 朱云麗

1.一種縮短應急響應時間的雙平行機調度方法，其特征在于，具體步驟如下：

步驟1，任務預處理：對所有待分配的加工、服務任務按照處理時間由短到長進行排序；

步驟2，對任意調度方案根據任務服務時段特征將其劃分為三個集合：考慮任一調度方案E，將所有任務分為三個集合：任務集X1包括服務時間被其他任務服務時間包含的任務，任務集X2包括與其他任務服務時間只存在重疊的任務，任務集X3包括既與其他某個任務有重疊又包含至少一個其他任務的任務；

步驟3，通過分析各調度方案下完工時間間隔的取值界定最大完工時間間隔IC_max的理論最小值：對集合X2包含q個任務的調度方案E_q，計算集合X1中的最大任務長度p1、集合X2中的最大任務長度p2、集合X3的任務服務重疊時段的平均長度IC_a；將LB_q定義為p1、p2/2、IC_a三者的最小值；所有可能的q取值，比較其調度方案E_q對應的LB_q值，將最小的LB_q確定為IC_max的最小值LB；

其中，最大完工時間間隔IC_max定義為：將綜合考慮兩臺機器上服務完工時間相鄰的兩個任務對應的完工時間差定義為一個完工時間間隔IC；給定任意一個服務調度方案，所有完工時間間隔的最大值即為最大完工時間間隔IC_max；

步驟4，采用錯位規(guī)則結合最大完工時間間隔的理論最小值給出任務的調度方案：分配任務至兩臺平行機，將任務序列中最長的任務J安排至機器M1，將長度不超過3/2倍LB的剩余任務從大到小分配至機器M2，直至該機器上最后一個任務的完工時間離任務J的完工時間少于3/2倍LB；將序列中最長的剩余任務J’分配至機器M2，并將長度不超過3/2倍LB的剩余任務從大到小分配至機器M1，直至該機器上最后一個任務的完工時間離任務J’的完工時間少于3/2倍LB；重復上述任務分配過程，直至剩余任務序列中不存在或者全部是長度小于3/2倍LB的任務；將剩余的任務按照從長到短順序在兩臺機器上均勻分配；

步驟5，按照步驟4分配方案執(zhí)行日常任務的服務活動，當有緊急任務在執(zhí)行步驟4調度方案的過程中到達，則在應急響應時間內啟動服務緊急任務；

其中，所述應急響應時間為：從零時刻開始計算當前正在運行的兩個任務的完工時間以及相鄰完工時間的間隔，并得到IC_max值，IC_max意味著緊急任務到達后需等待的最長時間，即在最壞情況下的方案應急響應時間。