[發明專利]基于多色集合的改進遺傳算法求解靜態車間調度的方法

在審

• 申請號: 201810090479.0
• 申請日: 2018-01-30
• 公開（公告）號: CN108364126A
• 公開（公告）日: 2018-08-03
• 發明（設計）人: 欒飛;陳夢瑤;石冰潔;李媛鳴;來春為;傅衛平;祝曉雪;張淼
• 申請（專利權）人: 陜西科技大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06N3/12
• 代理公司: 西安通大專利代理有限責任公司 61200
• 代理人: 徐文權

1.一種基于多色集合的改進遺傳算法求解靜態車間調度的方法，其特征在于，包括以下步驟：

步驟1：獲取車間加工任務、設備和工序的具體信息，使用對色集合理論來描述靜態車間調度任務中待加工工序所受到的工藝與機床的具體約束；

步驟2：確定靜態車間調度的具體約束，用調度約束表達式表示，用“1”和“0”分別表示指標變量x_ihk和指標系數a_ihk；

步驟3：根據具體的加工信息繪制加工任務信息表，進而創建圍道矩陣，來表達調度約束條件；

步驟4：根據工序－機床圍道布爾矩陣，生成工序隱性編碼序列表，由工序隱性編碼序列表，生成工藝-設備的邏輯圍道矩陣[A×F(A)]及其實數圍道矩陣[A×A(F)]；

步驟5：在模型約束下進行隱性染色體編碼；

步驟6：據染色體的隱性編碼信息獲取各工序對應機床所需加工時間，得出各工序的完工時間及機床的釋放時間；步驟7：按照柔性車間調度理論，創建目標函數；

步驟8：將上一代種群中適應度值最好的個體所對應的染色體直接選擇進入下一代種群，再隨機從父代選擇兩個染色體chrom1與chrom2；

步驟9：判斷隨機選擇的兩個父代染色體chrom1與chrom2是否需要交叉，若是則進行下一步，否則保留原染色體；兩個父代染色體進行交叉后的形成兩個子代染色體，分別對應進行適應度值得比較，存優；重復進行此過程，得到最優的染色體編碼序列；

步驟10：模型約束下的變異，采用圍道布爾矩陣來控制變異過程，最后得到更優的新染色體；

步驟11：重復進行選擇、交叉與變異，直至重復次數達到閾值W，記錄當前適應度值；若適應度值隨迭代次數收斂，則終止遺傳算法輸出調度結果，若不收斂，則重復上述所有步驟直到收斂。

2.根據權利要求1所述的基于多色集合的改進遺傳算法求解靜態車間調度的方法，其特征在于，步驟1中具體信息如下：通過N×J×M的FJSP調度問題描述調度任務中待加工工序所受到的工藝約束與機床約束，其中，N為工件的種類，J為對應的最大工序數，M為進行加工的設備數量。

3.根據權利要求2所述的基于多色集合的改進遺傳算法求解靜態車間調度的方法，其特征在于，步驟2中具體約束如下：

2-1)柔性車間靜態調度描述為：

在M臺設備上安排N種工件的加工，每種工件J_j由n_j道工序組成，每道工序均滿足工藝約束，工件的每道工序可由M臺設備中的多臺設備加工，用M_ij表示第j種工件的第i道工序用機器集合O_ijk表示第j種工件的第i道工序用機器k，P_ijk表示第j種工件的第i道工序在第k臺設備上加工需要的時間，即1≤j≤N，1≤i≤n_j，1≤k≤M，忽略生產過程中出現的返工返修和報廢品現象；調度的任務是在M臺設備上安排N種工件的加工任務，同時最優化既定的目標，并滿足以下假設條件：

a、所有工件的工藝計劃是固定不變的，即工序的先后順序不能違背；

b、工序在可供選擇的機器上的加工時間已確定；

c、出現再調度因子時，正在加工的工序不受影響繼續加工，直到本工序完成；

d、每個工件在固定時刻只能在一臺設備上加工；

2-2)根據FJSP調度問題可知，工藝約束為工件的每道工序必須按照設定的工藝順序進行加工；機床約束為各工序只能在設定的機床設備上進行加工；具體表達如下：

C_ik-t_ik+M(1-a_ihk)≥C_ih；i＝1,2,...,n；h,k＝1,2,...,m (3-1)

C_jk-C_ik+M(1-x_ijk)≥P_ik；i,j＝1,2,...,n；k＝1,2,...,m (3-2)

C_ik≥0；i＝1,2,...,n；k＝1,2,...,m (3-3)

式(3-1)表示目標函數，即要求最大完成時間最小化；C_ik表示工件i在設備k上的實際完工時間；t_ik表示工件i在設備k上的理論加工時間；a_ihk表示指標系數；C_ih表示表示工件i在設備h上的實際完工時間；i表示工件序號；n表示共有n件工件；k表示設備的序號；m表示共有m臺設備；

式(3-2)表示工藝約束條件決定的各種工件各操作的先后加工順序，保證每個工件的加工順序滿足預先設定的要求；C_ik表示工件j在設備k上的實際完工時間；x_ijk表示指標變量；p_ik表示工件i在設備k上加工需要的時間；j表示工件序號；

式(3-3)表示加工各個工件工序加工各機器的先后順序，保證每臺設備一次只能加工一個工件，C_ik表示工件i在設備k上的實際完工時間；指標變量x_ihk與指標系數a_ihk的意的義如下：