[發明專利]一種基于改進的水波優化算法的可并行裝配線平衡方法

有效

• 申請號: 202110093837.5
• 申請日: 2021-01-22
• 公開（公告）號: CN112686474B
• 公開（公告）日: 2022-04-22
• 發明（設計）人: 張梅;鄧率航;陳澤同;郭紅霞;吳玉香;朱金輝
• 申請（專利權）人: 華南理工大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/04;G06N3/12;G06K9/62
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 何淑珍;江裕強

1.一種基于改進的水波優化算法的可并行裝配線平衡方法，其特征在于，包括以下步驟：

S1、收集數據；

S2、初始化水波優化算法的參數；

S3、計算工序的后續時間和緊后工序數量，并且以這兩個信息為啟發式信息初始化種群；

S4、使用適應度值函數f(X)計算種群中所有染色體個體的適應度值，并且記錄適應度值最高的染色體個體為X_best；計算所有染色體個體的適應度值時，計算適應度值f(X)需要將染色體X解碼為可并行裝配線的一個調度方案，然后計算調度方案中所用到的工作站數量和所用的工人人數，工作站數量越少或者工人人數越少的染色體個體有更高的適應度值，適應度值函數的公式如下：

f(X)＝UB-(w₁*NS+w₂*NW)

其中w₁，w₂分別是工作站數量和工人數量的加權系數；NS是染色體個體X解碼為調度方案中所用到的工作站數量；NW是染色體個體X解碼為調度方案中所用到的工人總人數；UB是w₁*NS+w₂*NW的上限，UB取為即工序數量n和所有工序需要的人數加權和；

解碼采用貪心算法，貪心策略為：如果當前工作站有足夠的工人使得當前工序能夠完成，那么將當前工序分配到當前工作站；否則，新增一個工人再重新分配，如果工作站上因為空間限制無法新增工人，就新增一個工作站再重新分配；具體的解碼的過程如下：

S4.1、初始化解碼過程中的參數，即設工作站的數量NS＝1，當前工作站上的工人人數NP＝0，工人總人數為NW＝0，當前工作站上的工人集合P為空集，設隊列Q為一個空隊列；將染色體個體X上所有的工序按照在染色體個體上出現的順序加入隊列Q中，工序的允許開工時刻t_si為0，其中i表示工序在染色體中的順序編號，i＝1，2，…，n；

S4.2、判斷工序是否全部完成分配，即如果隊列Q為空，輸出工作站數量NS和工人總人數NW，結束解碼過程，否則執行步驟S4.3；

S4.3、讀取隊列Q中當前工序的信息，即從隊列Q頭部出隊一個元素，定義其為當前工序O_cur，讀取該工序需要的裝配工人數信息p_cur，裝配時間信息t_cur，允許開工時刻t_si；

S4.4、分配當前工序O_cur的裝配工人，即在集合P中的所有工人的空閑時間段中，找出在時間段[t_a，t_b]中有p_cur個工人是空閑的，t_a≥t_si，t_b＝t_a+t_cur；如果能找到p_cur個工人在時間段[t_a，t_b]上是空閑的，則指派p_cur個工人在時間段[t_a，t_b]上去加工工序O_cur，并執行S4.6；如果不能找到p_cur個工人在時間段[t_a，t_b]上是空閑的，則執行步驟S4.5；

S4.5、如果當前工作站的工人數NP＜P_max，則增加一個沒有被指派任務的工人到當前工作站上，同時將該工人加入集合P，使NP＝NP+1，執行步驟S4.4；否則，增加一個工作站，使NS＝NS+1，NW＝NW+NP，NP＝0，將集合P設為空集，同時將隊列中所有的工序的允許開工時刻t_si重新設置為0，執行步驟S4.4；

S4.6、如果工序O_cur的所有緊后工序o_i的允許開工時刻t_si小于t_b，則將該緊后工序的允許開工時刻t_si設置為t_b，執行步驟S4.2；否則保持t_si不變，執行步驟S4.2；

S5、更新種群中的所有染色體個體；

S6、判斷是否達到算法結束條件，如果達到，將最優染色體個體X_best解碼為一個調度方案，使用該調度方案調整實際裝配線，結束整個過程，否則，將當前迭代次數加1并返回步驟S5。