[發明專利]一種改進的柔性流水車間調度問題的求解算法

在審

• 申請號: 201610890838.1
• 申請日: 2016-10-12
• 公開（公告）號: CN106611288A
• 公開（公告）日: 2017-05-03
• 發明（設計）人: 范勇;胡成華
• 申請（專利權）人: 四川用聯信息技術有限公司
• 主分類號: G06Q10/06
• 分類號: G06Q10/06
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種改進的柔性流水車間調度問題的求解算法，本發明涉及作業車間調度領域，其特征是，包括如下步驟：

步驟1：FSSP算法定義和流程，其具體描述如下：

步驟1.1）FSSP算法定義

1）置換序列：粒子的位置為X，置換序列（i，j）的操作位交換X中第i個元素和第j個元素

2）加法算子：把后一個速度的置換序列加入到前一個速度或位置的置換序列列表的末尾，例如：假設，那么

3）減法算子: 減法操作為粒子的全局最優解減去粒子的個體位置或者粒子個體最優解位置減去粒子個體位置，結果為置換序列，例如: 假設A=（3,1,2,4,5,6），B=（1,2,4,3,6,5），由于A（1）=B（4）=3，第一個交換序列就為（1,4），也就是說減法結果第一個位置上為4，以此類推，那么

4）乘法算子：乘法操作為慣性權重乘速度和學習因子、乘速度，運算的結果分別是以、、為概率保留粒子的速度

步驟1.2）FFSP算法流程

包括粒子種群規模，慣性權重因子，學習因子、，工件數量n，機器數量m，存儲工件加工矩陣JobNumber，工件關聯 陣JobRJob，工件總加工時間Totaltime，最大迭代次數T

步驟2:：重新定義粒子速度和位置的相關算子，通過分析初始機器選擇與調度總完工時間的關系，首次提出一種基于NEH算法的最短用時分解策略算法

步驟3：引入編碼矩陣和解碼矩陣來表示工件、機器以及調度之間的關系

步驟4：利用改進離散粒子群算法進行全局優化。

2.根據權利要求1中所述的一種改進的柔性流水車間調度問題的求解算法，其特征是，以上所述步驟2中的具體計算過程如下：

步驟2：重新定義粒子速度和位置的相關算子，通過分析初始機器選擇與調度總完工時間的關系，首次提出一種基于NEH算法的最短用時分解策略算法，其具體計算過程如下：

FFSP調度完工時間的大小取決于工件選擇的加工機器和機器上工序的加工順序，因此提高粒子種群初始解的質量尤為重要，提高初始解的質量可以縮短求解FSSP的時間和增強粒子尋找最優解的性能，按照工件在機器上總加工時間對工件進行降序排列，再依次取出工件進行迭代插入操作，這里，最短用時分解策略思想：將工件在機器上總加工時間按照每道工序進行分解，根據各個工件在每道工序上的總時間進行降序排列，按照每道工序的總時間與鄰近度進行對比并排序，直至對所有工件降序排序完成，其中，鄰近度定義如下：

表示兩道工序加工時間之間的接近程度，鄰近度越小表明越接近，最短用時分解策略算法步驟：

步驟2.1）設置優先級別列表，其中

，p為工序數，為第i道工序的機器個數，M為總機器的個數；同時設置工序數的副本pcopy，令pcopy=p； 設置鄰近度Pro； 計數器 t=1；優先級的設置m=M；

步驟2.2）在第pcopy道工序中，按照工件在機器上加工的總時間，對工件進行降序排列，得到排列序列seq；

步驟2.3）根據seq設置優先級列表S：對seq中第t和t+1兩道工序，比較數值之差，如果大于Pro，則較大數的優先級就設置為m，然后設置m=m-1； 否則，比較該兩道工序的前一道工序，直至得到比較結果；

步驟2.4）判斷 t是否等于M：如果是，則第t道工序的優先級設置為最低1，轉步驟 5；否則，轉步驟3；

步驟2.5）輸出優先級列表S；

步驟2.6）根據規則S動態隨機生成機器鏈。