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

在審

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

本發(fā)明公開了一種縮短應急響應時間的雙平行機調(diào)度方法，具體步驟如下：步驟1，任務預處理：步驟2，對任意調(diào)度方案根據(jù)任務服務時段特征將其劃分為三個集合：考慮任一調(diào)度方案E，將所有任務分為三個集合；步驟3，通過分析各調(diào)度方案下完工時間間隔的取值界定最大完工時間間隔IC_max的理論最小值；步驟4，采用錯位規(guī)則結(jié)合最大完工時間間隔的理論最小值給出任務的調(diào)度方案；步驟5，按照步驟4分配方案執(zhí)行日常任務的服務活動，當有緊急任務在執(zhí)行步驟4調(diào)度方案的過程中到達，則在應急響應時間內(nèi)啟動服務緊急任務。本發(fā)明的調(diào)度方法無需事先研判緊急任務的可能到達時間，處理方式簡單，降低緊急響應的管理復雜性及管理成本。

技術領域

本發(fā)明涉及任務調(diào)度領域，具體為一種縮短應急響應時間的雙平行機調(diào)度方法。

背景技術

調(diào)度技術在生產(chǎn)運作、醫(yī)療服務等領域一直有著廣泛的應用。現(xiàn)有的調(diào)度方法技術往往聚焦于管理者對日常作業(yè)任務的加工、服務進行合理安排，以追求服務成本或利潤的最優(yōu)性。如今，客戶至上與實時作業(yè)管理是生產(chǎn)服務的要求特征，在日常運作管理過程中突發(fā)出現(xiàn)緊急任務需求是一種新常態(tài)。如何及時響應緊急任務而又不中斷當前運行中的任務以有效控制響應成本，這是當前作業(yè)管理中的一個重要訴求。已有的調(diào)度方法通常為緊急任務到達之后的事后重調(diào)度，響應方式被動，要么響應緊急任務的時間長，要么因中斷當前任務導致響應成本高，響應效果不好。

發(fā)明內(nèi)容

針對上述存在的技術不足，本發(fā)明的目的是提供一種縮短應急響應時間的雙平行機調(diào)度方法，其對日常任務進行事前調(diào)度設計，調(diào)度方案具有響應速度快且成本低的特點。

為解決上述技術問題，本發(fā)明采用如下技術方案：

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

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

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

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

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

步驟4，采用錯位規(guī)則結(jié)合最大完工時間間隔的理論最小值給出任務的調(diào)度方案：分配任務至兩臺平行機，將任務序列中最長的任務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調(diào)度方案的過程中到達，則在應急響應時間內(nèi)啟動服務緊急任務；