[發明專利]一種基于供需關系的制造服務自適應調度方法

有效

• 申請號: 202110535529.3
• 申請日: 2021-05-17
• 公開（公告）號: CN113240287B
• 公開（公告）日: 2022-08-05
• 發明（設計）人: 程穎;任嘉偉;陶飛;張永平
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q50/04;G06Q10/04;G06N3/00;G06N3/12
• 代理公司: 北京科迪生專利代理有限責任公司 11251
• 代理人: 張乾楨;江亞平

1.一種基于供需關系的制造服務自適應調度方法，其特征在于包括步驟如下：

步驟1：解析制造服務供需關系，并基于供需關系構建制造服務調度問題模型；在生產制造的過程中，通過信息化的手段或預測的方式獲取制造服務系統中的供需狀態；構建基于供需關系的任務與資源模型；根據一段時間內N個調度任務T_n,n＝1,2,3...,N，調度任務的屬性包括任務到達時間，任務截止時間，任務所需服務種類及數量，以及服務工序，W_m個制造服務資源M^w,w＝1,2,3...,W_m，制造服務資源的屬性包括資源的種類及數量構建模型；

步驟2：對系統負載狀態及余度進行動態評估；計算調度任務負載時，考慮到任務的數量、任務所需資源及任務的緊迫性；同時，通過計算當前可調用資源種類與數量，考慮資源的稀缺性與重要性，得出當前系統可調用資源的服務能力；然后，通過比較系統負載狀態及系統可用服務能力動態地評估系統的余度；

步驟3：根據供需波動對動態調度情境進行識別；考慮到制造服務系統供需的波動性與不確定性，制定基于供需波動的動態調度情境識別方法，考慮一段時間內供需關系的變化特征，并根據不同特征設計制定不同的調度情境，從而根據不同的供需關系特征識別不同的調度情境；

步驟4：基于不同的調度情境與系統狀態，制定自適應調度規則；對于動態調度問題，結合不同調度情景分別制定自適應調度規則或調度閾值，當系統狀態滿足重調度觸發條件時，觸發一次重調度流程，對當前系統中還未執行的任務進行調度；

步驟5：調度方案的生成與執行；首先，以最短延遲時間及最大平臺穩定性的目標函數，以資源數量，工藝順序為約束條件，構建調度問題的模型；其次，基于智能求解算法包括粒子群算法，遺傳算法，進化算法之一的方法對問題進行求解；最后，按照求解的方案執行直到下一次重調度觸發，并重復步驟2-5的流程，直至所有任務均完成執行；

所述步驟1具體包括：

(1.1.)針對一段時間內的N個調度任務T_n,n＝1,2,3...,N，描述其主要屬性，其中任務的到達時間表示為T_arrive_n，任務的截止時間表示為T_due_n，同時，這些任務還將按照其任務需求分別分解為需要多個服務協作完成的子任務集，其中每個任務被分解為K_m,m＝1,2,3,...,M個子任務，其中sT_{n_k},k＝1,2,3,...,K_m，表示調度任務T_n的子任務集，表示每個子任務的所需每種服務資源的數量；對于調度系統內的M種服務資源，每種資源的數量表示為W_m,n＝1,2,3...,M，其中每個服務的執行時間表示為Mw_execute^m_w；

(1.2.)對于任務執行過程，ⁱT_start_n表示任務在調度方案中的開始時間，sT_start_{n_k}與sT_finish_{n_k}表示相應子任務的開始時間與結束時間，T_finish_n表示任務在實際執行的完成時間，^tsT_left_{n_k}表示子任務在執行過程中的剩余時間，表示相應的服務執行對應任務的剩余時間；

(1.3.)描述調度系統的任務執行情況，引入相應參數，對于調度任務T_n，^tX_n表示任務的到達情況，若已經到達則^tX_n＝1，否則^tX_n＝0，^tY_n表示任務的完成情況，若已經完成則^tY_n＝1，否則^tY_n＝0，^tZ_n表示任務的執行情況，若正在執行則^tZ_n＝1，否則^tZ_n＝0；對于相應的子任務，^ty_{n_k}表示子任務的完成情況，若已經完成則^ty_{n_k}＝1，否則^ty_{n_k}＝0，^tz_{n_k}表示子任務的執行情況，若正在執行則^tz_{n_k}＝1，否則^tz_{n_k}＝0；對于系統服務資源，表示資源的占用情況，若正在被相應服務占用則否則

所述步驟2具體包括：

(2.1.)根據調度任務負載以及系統服務能力狀況，對當前系統狀態進行評估；評價系統任務負載的過程中，考慮到調度任務需求具有動態性特征，因此設定在t時刻系統任務負載C_t的計算公式如式(1)所示，其中N為t時刻到達系統的任務數；

式中^tX_n×(1-^ty_{n_k})×(1-^tz_{n_k})表示，選擇出當前時刻已經到達且還未被執行的任務，通過比較任務的截止時間與預期完成時間表示出了相應任務的緊迫程度，表示對于相應資源的需求量；通過式(1)求得，當前時刻下的任務對每一類資源的需求程度，進而反映當前系統的任務負載；

(2.2.)評價系統服務能力時，根據每種資源的可用數量以及正在被占用服務的預計結束時間，設定在t時刻的系統服務能力S_t的計算方法，如式(2)所示：

式中(1-^tU^m_w)表示當前系統中未被占用的資源，表示系統中正在被占用的資源，表示相應資源完成當前任務所剩余的時間，β為歸一化系數；通過式(2)求得，當前時刻下系統中每一類服務資源的可用性，進而反映出當前系統的服務能力；隨后，通過比較系統服務能力與任務負載，結合調度任務對服務資源的需求，即可求得系統的余度；

所述步驟3具體包括：

對于制造服務調度系統，供需關系通過比值的方式計算分別按照不同類型的資源計算供需關系計算公式；同時，在調度系統任務的執行過程中，選擇在一段時間區間內系統服務能力與任務負載之比的平均值，記作^△tS與^△tC，在一段時間內，系統服務能力與任務負載之比θ的計算公式如式(3)所示：

其中，^△tθ表示一段時間△t內的供需比，^△tS表示△t時間內的系統服務能力，^△tC表示△t時間內的系統任務負載情況，由于^△tS和^△tC均為代表不同種資源的向量形式，取其最小值即可得到制約系統服務能力資源的供需關系，從而代表該段時間內的調度情境；最后，按照專家經驗或通過數據分析即可將供需比^△tθ按照其數值高低設定等級，不同等級即代表不同的調度情境種類；

所述步驟4主要包括：

基于不同的調度情境與系統狀態，制定一套自適應調度規則，用于調度系統的重調度觸發，即當系統供需關系滿足條件時觸發重調度流程；基于步驟3中所構建的多種制造服務調度問題情境，系統的狀態與調度情境得以通過供需關系進行描述，所述調度系統的重調度觸發基于系統服務能力與負載狀態之比的自適應重調度觸發機制，即在系統的實時運行中，通過對系統資源服務能力與任務負載狀態的實時評估來決定是否需要驅動重調度流程，以及在不同的任務情境下設置自適應調度觸發閾值θ′_n，即當^△tθθ_n'時不進行重調度操作，在^△tθ≥θ_n'時驅動重調度流程，自適應調度觸發閾值θ′_n與步驟3中所設定的調度情境種類對應，有多少種調度情境即有多少種自適應調度觸發閾值；

所述步驟5主要包括：

(5.1.)構建以最短延遲時間及最大平臺穩定性為目標的目標函數，

目標函數1：總延遲時間最短

對于調度任務而言，其總延遲時間代表了調度系統的調度優化水平，延遲時間越短表示系統優化的效果越好，如式(4)所示：

目標函數2：平臺穩定性最大

對于調度任務，采用調度任務延遲時間的方差來評價調度的均衡性問題，任務開始時間方差越小，表示系統越均衡，如式(5)所示,其中i表示當前的重調度次數，I表示總重調度次數；

(5.2.)以資源數量，工藝順序為約束條件，構建調度問題的模型

約束條件1：對于任意任務Tn中的每一道工序的實際執行時間等于預期執行時間，如式(6)所示：

約束條件2：同一任務Tn的不同工序間存在先后順序的約束，如式(7)所示：

約束條件3：在任意時刻，對于任意資源m，所有任務所使用的m資源數量之和不得超過m資源的總數，如式(8)所示：

最后，基于以上調度問題模型，采用智能求解算法，以及調度規則對以上問題進行求解，并且按照求解的方案執行直到下一次重調度觸發，并重復步驟2-5的流程，直至所有任務均完成執行。