[發明專利]一種基于改進遺傳算法的柔性作業車間調度方法

有效

• 申請號: 202110037735.1
• 申請日: 2021-01-12
• 公開（公告）號: CN113610233B
• 公開（公告）日: 2023-08-15
• 發明（設計）人: 王玉芳;葛嘉榮;繆昇;馬銘陽
• 申請（專利權）人: 南京信息工程大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q10/04;G06Q50/04;G06N3/12
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 田凌濤

1.一種基于改進遺傳算法的柔性作業車間調度方法，其特征在于，包括以下步驟：

步驟1、建立柔性作業車間調度的模型；

步驟2、確定模型的約束條件；

步驟3、按照先驗知識進行種群初始化，采用并行雙鏈式編碼，根據柔性作業車間調度的兩個子問題：機器選擇和工序排列，進行編碼；

步驟4、使用最優插入法對每個個體進行適應度計算，通過錦標賽選擇法選擇出要進行后續操作的種群；

步驟5、對工序編碼層采用IPOX交叉法，對機器選擇編碼層采用多點交叉法；

步驟6、對工序編碼層進行局部搜索，對機器選擇編碼層進行多重變異操作；

步驟7、對新一代的種群根據適應度進行排序，保留當代的最優解；

步驟8、判斷是否滿足終止條件，終止條件為是否達到最大迭代次數gen，若滿足執行步驟九，否則，返回步驟4；

步驟9、輸出最優結果，并給出相關的收斂曲線和調度甘特圖；

步驟4中，使用最優插入法對每個個體進行適應度計算，通過錦標賽選擇法選擇出要進行后續操作的種群，具體步驟如下：

隨著工件加工數量的積累，各機器上會出現加工空閑，造成機器負載率的降低的同時，也加大了最大完成時間，故而采用最優插入法來提高求解質量；

步驟4.1、在滿足機器約束和工件約束的情況下，將當前加工工序插入到一個與它加工時間最接近的空閑時間段里；

通過錦標賽選擇法選出后續操作的種群，其步驟如下：

步驟4.2、從當前種群中隨機選擇若干個個體；

步驟4.3、對選擇的個體進行適應度計算，將適應度最高的個體插入到新種群中；

步驟4.4、重復上述步驟直到新種群中的個體數量等于舊種群；

在步驟6中，對工序編碼層進行局部搜索，對機器選擇編碼層進行多重變異操作；具體步驟如下：

對機器選擇編碼層進行多重變異操作步驟如下：

步驟6.1、隨機選擇一個父代個體father1；

步驟6.2、隨機從n個工件中選擇若干個工件

步驟6.3、從被選中的每一個工件隨機選擇一道工序；

步驟6.4、未被選中的father1基因保持原位不動，對選中的部分進行枚舉排序，得到一組新染色體；

步驟6.5、對新得出的染色體組進行適應度計算，如果存在適應度大于father1的新個體child1，則替換father1；否則，不做任何操作；

對工序編碼層進行局部搜索步驟如下：

步驟6.6、隨機選擇一個父代個體father1；

步驟6.7、判斷是否滿足變異概率，如果滿足，執行步驟6.8，否則，返回步驟6.6；

步驟6.8、隨機選擇一個與當前機器不同的機器加工，如果只有一臺機器可供選擇，則不執行任何操作；

步驟6.9、father1中與數組L為1對應位置的工序選擇加工時間最短的機器進行加工；

步驟6.10、將得到的子代個體childl替換種群的father1，數組L表示由隨機所產生的0、1組成的數組。

2.根據權利要求1所述的一種基于改進遺傳算法的柔性作業車間調度方法，其特征在于：在步驟1中，建立柔性作業車間調度的模型，具體步驟如下：

步驟1.1、建立數學模型，以最大完成時間最小為目標函數：f＝min{max?C_i}，其中C_i表示工件i的完成時間，i＝1，2，3，...，n；n是待加工工件的數量。