[發明專利]考慮訂單插單的高端裝備研制過程多項目重調度方法及系統

有效

• 申請號: 202110310620.5
• 申請日: 2021-03-23
• 公開（公告）號: CN112884370B
• 公開（公告）日: 2022-10-28
• 發明（設計）人: 劉心報;裴軍;饒陳潔;程浩;范新中;周志平;崔龍慶;錢曉飛;陸少軍
• 申請（專利權）人: 合肥工業大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q50/04;G06N3/00
• 代理公司: 合肥市浩智運專利代理事務所(普通合伙) 34124
• 代理人: 張景云

1.考慮訂單插單的高端裝備研制過程多項目重調度方法，其特征在于：包括以下步驟：

S1、獲取多項目訂單數據，所述多項目訂單數據包括原計劃訂單數據和插單訂單數據，所述插單訂單數據至少包括：插單訂單的交貨日期、插單客戶的等級；基于多項目訂單數據初始化禁忌搜索算法的輸入參數；設定禁忌搜索算法的執行參數；

S2、將所有工作按基礎時間非遞增進行排序，得到一個經過排序后的工作集合，根據工作集合，找出各個工作的緊前工作集合Prev(j)和緊后工作集合Next(j)；其中j表示工作；

S3、基于所述輸入參數和所述執行參數生成初始解，將初始解作為當前解X_s和當前全局最優解X_best；

S4、基于所述緊前工作集合Prev(j)和所述緊后工作集合Next(j)對當前解X_s的進行解碼，基于解碼后的當前解X_s和預設的規則庫產生鄰域解集N(X_s)，計算鄰域解集內個體的適應度值，選出候選解集List(X_s)，所述預設的規則庫根據插單訂單的交貨日期設置；

S5、選出List(X_s)中適應度值最小的個體作為的最優個體Y；

S6、判斷最優個體Y的適應度值是否小于全局最優解X_best，若小于X_best，則將Y賦值給X_best，更新當前解X_s，將Y賦值給X_s，更新禁忌表TBList，否則執行步驟S7；

S7、判斷步驟S5獲得的最優個體Y是否在禁忌表TBList中，若是把List(X_s)中的個體Y移出該集合，更新候選解集List(X_s)，并返回步驟S6；否則根據當前解X_s更新禁忌表TSList；

S8、更新當前解，則把Y賦值給X_s；

S9、將I+1賦值給I，判斷I≤I_max是否成立，若成立則返回步驟S4；否則算法執行結束，輸出最優解X_best，根據最優解X_best得到最優調度方案；

所述步驟S1中的輸入參數包括：

工作數量N+M、資源數量K、完成工作j需要的基本時間T_j、資源k完成工作j需要時間t_jk、各個資源的能力值c_k、原計劃的交貨日期的最早值dt_E、最晚值dt_L、插單訂單的交貨日期dt_V、工作的位置序號Pos_j、分配給工作的資源序號Res_j和插單客戶的等級變量α；

所述步驟S3具體為：

S301、定義變量j＝1；

S302、判斷α與α_H、α_G、α_L的關系，若α＝α_H，則執行S303；若α＝α_G，則執行S307；若α＝α_L，則執行S310；其中：α表示插單客戶的等級，α_H表示高水平客戶、α_G表示一般水平客戶、α_L表示低水平客戶；

S303、找出工作j可用的資源集合R(T_j)，R(T_j)＝{R_j1，...，R_jb，...，R_jB}，其中B為工作j可用的資源數量，判斷j是否為插單訂單工作，若是執行S304，否則執行S305；

S304、隨機產生1個在[0，|B/3|]范圍內的隨機數，記為rand，把R_rand賦值給Res_j，把j賦值給Pos_j，其中|B/3|為大于|B/3|小于(|B/3|+1)的整數；

S305、隨機產生1個在[0，B-1]范圍內的隨機數，記為rand，把R_rand賦值給Res_j，把j賦值給Pos_j；

S306、x_j＝{Res_j，Pos_j}，Res_j表示工作j使用的資源，Pos_j表示工作j在工作集合中所處的位置，執行S314；

S307、找出工作j可用的資源集合R(T_j)，R(T_j)＝{R_j1，...，R_jb，...，R_jB}，其中B為工作j可用的資源數量；

S308、隨機產生1個在[0，B-1]范圍內的隨機數，記為rand，把R_rand賦值給Res_j，把j賦值給Pos_j；

S309、x_j＝{Res_j，Pos_j}，Res_j表示工作j使用的資源，Pos_j表示工作j在工作集合中所處的位置；執行S314；

S310、找出工作j可用的資源集合R(T_j)，R(T_j)＝{R_j1，...，R_jb，...，R_jB}，其中B為工作j可用的資源數量；判斷j是否為插單訂單工作，若是執行S311，否則執行S312；

S311、隨機產生1個在[|2*B/3|，B-1]范圍內的隨機數，記為rand，把R_rand賦值給Res_j，把j賦值給Pos_j，其中|2*B/3|為大于|2*B/3|小于(|2*B/3|+1)的整數；

S312、隨機產生1個在[0，|2*B/3|]范圍內的隨機數，記為rand，把R_rand賦值給Res_j，把j賦值給Pos_j，其中|2*B/3|為大于|2*B/3|小于(|2*B/3|+1)的整數；

S313、x_j＝{Res_j，Pos_j}，Res_j表示工作j使用的資源，Pos_j表示工作j在工作集合中所處的位置；執行S314；

S314、把j+1賦值給j，判斷j≤N+M是否成立，若不成立，則返回S302；否則，以X＝{x₁，...，x_j，...，x_N+M}作為初始解，將初始解作為當前解X_s和當前全局最優解X_best；

所述步驟S4具體為：

S401、根據串行調度機制對當前解X_s正向進行解碼，解碼的過程中得到各個工作的開始時間BT_j和工作的結束時間ET_j，并標記有資源沖突的工作；

S402、根據串行調度機制對當前解X_s反向進行解碼，解碼的過程中會得到各個工作的最遲開始時間rBT_j和工作的最遲結束時間rET_j；

S404、根據正向解碼和反向解碼得出的四個時間計算出該工作的總時差、關鍵工作，根據標記的資源沖突工作可以得到各資源的沖突工作集合

S405、由初始解X_s根據預設的規則庫和插單客戶的等級獲得由W個個體組成的產生鄰域解集，記為N(X_s)＝{X₁，...，X_j，...，X_W}，其中X_j表示鄰域解中的第j個個體；

S406、在候選解集中考慮Q個個體，候選解集記為List(X_s)，在N(X_s)中選出質量較好的Q個不同個體，并把選出的個體賦值給List(X_s)；

所述步驟S405具體包括：

S405a、當α＝α_H時，若L_F＜L_min，執行調度規則1，然后執行步驟S405d；若L_F＞L_max，執行調度規則3，然后執行步驟S405d；若L_min＜L_F＜L_max，執行調度規則2，然后執行步驟S405d；其中：L_F表示插單訂單的拖延時間；L_min為原訂單的最小拖延時間，拖延時間＝完工時間-交貨時間，L_max為原訂單的最大拖延時間；

S405b、當α＝α_G時，若L_F＜L_min，執行調度規則2，然后執行步驟S405d；若L_F＞L_max，執行調度規則4，然后執行步驟S405d：若L_min＜L_F＜L_max，執行調度規則3，然后執行步驟S405d；

S405c、當α＝α_L時，若L_F＜L_min，執行調度規則3，然后執行步驟S405d；若L_F＞L_max，執行調度規則5，然后執行步驟S405d；若L_min＜L_F＜L_max，執行調度規則4，然后執行步驟S405d；

S405d、把j+1賦值給j，判斷j≤N+M是否成立，若成立則返回步驟S405a，否則執行步驟S405e；

S405e、隨機產生2個在[0，H-1]范圍內的隨機數，分別記為i₁和i₂，i₁和i₂不相同，j_k1和j_k2分別為R_c(R_k)對應位置的工作，H為使用沖突資源R_k時產生的沖突工作數量；

S405f、當α＝α_H時，若j_k1和j_k2均為原工作或均為插單訂單工作，將兩個工作中大的Pos值賦給總時差小的工作，否則將兩個工作Pos值大的賦給插單訂單工作；當α＝α_L時，若j_k1和j_k2均為原工作或均為插單訂單工作，將兩個工作中大的Pos值賦給總時差小的工作，否則將兩個工作Pos值大的賦給原工作；當α＝α_G時，將兩個工作中大的Pos值賦給總時差小的工作；

S405g、把k+1賦值給k，判斷k≤K是否成立，若成立則返回步驟S405e，否則執行步驟S405h；K為沖突源的個數；

S405h、把l+1賦值給l，判斷l≤W是否成立，若成立則返回步驟S405a；否則執行步驟S406；

所述調度規則1為：

第1步：根據原始調度序列，得到資源的沖突任務集合關鍵任務集合以及計算每個任務的總時差；

第2步：插單訂單任務的資源在范圍隨機生成，L_MAX的項目的任務的資源在范圍內隨機生成，其他任務的資源在范圍內生成；其中，為工作j可使用的資源集合的數目；

第3步：任意從資源的任務沖突集合內選取兩個任務，根據任務所屬的訂單的等級交換pos值，等級較高的任務得到較大的pos值，若任務等級相同，則按照任務的總時差排序，總時差較小的任務得到較大的pos值；

所述調度規則2為：

第1步：根據原始調度序列，得到資源的沖突任務集合關鍵任務集合以及計算每個任務的總時差；

第2步：所有任務的資源在范圍內隨機生成；

第3步：任意從資源的任務沖突集合內選取兩個任務，根據任務所屬的訂單的等級交換pos值，等級較高的任務得到較大的pos值，若任務等級相同，則按照任務的總時差排序，總時差較小的任務得到較大的pos值；

所述調度規則3為：

第1步：根據原始調度序列，得到資源的沖突任務集合關鍵任務集合以及計算每個任務的總時差；

第2步：插單訂單任務的資源在范圍隨機生成，L_MAX的項目的任務的資源在范圍內隨機生成，其他任務的資源在范圍內生成；其中，和對和向上取整；

第3步：任意從資源的任務沖突集合內選取兩個任務，根據任務所屬的訂單的等級交換pos值，等級較高的任務得到較大的pos值，若任務等級相同，則按照任務的總時差排序，總時差較小的任務得到較大的pos值；

所述調度規則4為：

第1步：根據原始調度序列，得到資源的沖突任務集合關鍵任務集合以及計算每個任務的總時差；

第2步：L_MIN的項目的任務的資源在范圍隨機生成，L_MAX的項目的任務的資源在范圍內隨機生成，其他任務的資源在范圍內生成；其中，和對和向上取整；

第3步：任意從資源的任務沖突集合內選取兩個任務，根據任務所屬的訂單的等級交換pos值，等級較高的任務得到較大的pos值，若任務等級相同，則按照任務的總時差排序，總時差較小的任務得到較大的pos值；

所述調度規則5為：

第1步：根據原始調度序列，得到資源的沖突任務集合關鍵任務集合以及計算每個任務的總時差；

第2步：L_MIN的項目的任務的資源在范圍隨機生成，新訂單的任務的資源在范圍內隨機生成，其他任務的資源在范圍內生成；其中，和對和向上取整；

第3步：任意從資源的任務沖突集合內選取兩個任務，根據任務所屬的訂單的等級交換pos值，等級較高的任務得到較大的pos值，若任務等級相同，則按照任務的總時差排序，總時差較小的任務得到較大的pos值；

所述步驟S406具體包括：

S406a、定義變量p＝1；

S406b、階段p存在一個不完全計劃集合S_p和一個滿足緊前關系約束的可行工作集合D_p；

S406c、找出滿足緊前關系約束的可行工作集合D_p；

S406d、選出D_p中pos值最大的一個工作j，找出工作j的緊前工作集合為Prev(j)，緊后工作集合為Next(j)；

S406e、工作j的開始時間為BT_j，結束時間為ET_j，其中BT_j＝max{max{Prev(ET_j)}，UT_k}，ET_j＝BT_j+t_jk，t_jk＝T_j/c_k，max{Prev(ET_j)}為該工作所有緊前工作的完成時間ET_j的最大值，UT_k為該工作資源可用時間的最早可行時間，T_j為完成該工作的基礎時間，c_k為資源k的能力值；

S406f、將該工作移除D_p，加入到S_p中；

S406g、把p+1賦值給p，若p≤N+M成立，執行步驟S406b；否則執行步驟S406h；

S406h、當p＝N+M時，得到各個工作的完成時間集合ET，ET＝{ET₁，...，ET_N+M}，選出其中最大的元素，并把該元素賦值給T_max，即T_max＝max ET，得到各個插單訂單工作的完成時間選出其中最大的元素，并把該元素賦值給T_2max，即T_2max＝maxET₂；

S406i、定義變量f，f＝T_max+max{0，T_2max-T₂}，其中T₂表示插單訂單的交貨時間，把f作為個體的適應度值。