[發明專利]基于改進禁忌搜索算法的生產運輸協同調度方法及系統

有效

• 申請號: 201710813169.2
• 申請日: 2017-09-11
• 公開（公告）號: CN107392402B
• 公開（公告）日: 2018-08-31
• 發明（設計）人: 裴軍;宋慶儒;劉心報;陸少軍;張強;范雯娟;孔敏
• 申請（專利權）人: 合肥工業大學
• 主分類號: G06F17/00
• 分類號: G06F17/00;G06Q10/04;G06Q10/06;G06Q50/04
• 代理公司: 北京路浩知識產權代理有限公司 11002
• 代理人: 王瑩;余罡

1.一種基于改進禁忌搜索算法的生產運輸協同調度方法，其特征在于，包括：

S1、將工件集合J＝{J₁,...,J_i,...,J_n}中所有工件按基本加工時間非遞增進行排序，得到經過排序后的工件集合J'＝{J′₁,...,J′_i,...,J'_n}；其中J_i表示工件集合中第i個工件，J′_i表示排序后工件集合中第i個工件；

S2、根據工件集合J'，在現存的批中選出能容納第一個未分配的工件的所有批，從已選出的批中獲取剩余空間最小的批，將J'中第一個未分配的工件放置于最終選出的批中，并將該工件從工件列表中刪除；

S3、重復步驟S2，直至工件集J'中所有工件都分配到相應的批中，從而形成批集合記為B＝{b₁,...,b_d,...,b_l}；其中b_d表示第d個批次，l表示批次的數量；

S4、初始化算法的輸入參數，所述輸入參數包括工件數量n，工件尺寸s，工件基本加工時間p，加工機器數量m，工件到達加工機器所需時間r，每個批次所能容納的最大工件數量C和處理速度v，工件從各加工機器運輸到客戶所需的時間T；

S5、設定算法的執行參數，所述執行參數包括最大迭代次數I_max，當前迭代次數I＝1，交叉概率CR，算法初始解X_s＝{x₁,...,x_d,...,x_l}，其中x_d表示第d個批次被分配到第x_d個機器，全局最優解X_best＝X_s；

S6、根據初始解X_s產生鄰域解集N(X_s)，對N(X_s)中的個體進行更新，確定候選解集List(X_s)；

S7、判斷List(X_s)是否為空集，若為空集則執行步驟S12；否則選出List(X_s)中的最優個體Y；

S8、判斷個體Y是否優于全局最優解X_best，若優于X_best，則將Y賦值給X_best，并執行步驟S11；否則執行步驟S9；

S9、判斷步驟S7獲得的個體Y是否符合禁忌表TSList中的禁忌規則，若符合則執行步驟S10；否則執行步驟S11；

S10、更新候選解集List(X_s)，把List(X_s)中的個體Y移出該集合，并返回步驟S7；

S11、判斷是否獲得新個體Y，若個體Y更新，則把Y賦值給X_s；

S12、根據初始解X_s更新禁忌表TSList；

S13、將I+1賦值給I，判斷I≤I_max是否成立，若成立則返回步驟S6；否則算法執行結束，輸出最優解X_best適應度值，工件集中工件的組批方案以及工件批在各加工機器上的分配方案；

所述步驟S5中設定算法初始解X_s＝{x₁,...,x_d,...,x_l}，包括：

步驟S51：將批集合B＝{b₁,...,b_d,...,b_l}中所有的批按其加工長度非遞增進行排序，形成經過排序后的批集合記為B'＝{b′₁,...,b'_d,...,b′_l}；

步驟S52：將機器按其加工速度非遞增進行排序，得到經過排序后的機器集合M＝{M₁,...,M_k,...,M_m}，M_k表示加工處理速度處于第k位且編號為M_k的加工機器；

步驟S53：定義變量d＝1，k＝1；

步驟S54：則把M_k賦值給x_d；

步驟S55：將k+1賦值給k，判斷k≤m是否成立，若成立，則執行步驟S56；否則，令k＝1并執行步驟S56；

步驟S56：把d+1賦值給d，判斷d≤l是否成立，若成立，則返回步驟S54；否則，以X＝{x₁,...,x_d,...,x_l}作為初始解X_s。