[發明專利]一種混合粒子群禁忌搜索算法求解作業車間調度問題

在審

• 申請號: 201610009782.4
• 申請日: 2016-01-08
• 公開（公告）號: CN106611231A
• 公開（公告）日: 2017-05-03
• 發明（設計）人: 湯琴;胡成華
• 申請（專利權）人: 四川用聯信息技術有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/04;G06N3/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種混合粒子群禁忌搜索算法求解作業車間調度問題，該算法將TSAB禁忌搜索算法與改進的粒子群算法結合，其特征在于：該算法的實現流程如下：

設種群規模為S，粒子用 表示，最大迭代次數為MAXITER，全局最優解為G_best，局部最優解為P_best

步驟1：初始化種群S，t=0，隨機初始；

步驟2：判斷是否達到最大迭代次數MAXITER,是則返回最優解g_best結束程序，否則執行下一步驟；

步驟3：如果i=1到種群規模S，循環步驟4到步驟12；

步驟4：使用實整數編碼機制將PSO的實數解轉化為TSAB的整數解 ；

步驟5：通過使用簡單的TSAB禁忌搜索和評估函數f（）更新潛在整數解；

步驟6：使用實整數解碼機制，將TSAB禁忌搜索的整數解轉化為PSO的實數解；

步驟7：更新和g_best；

步驟8：如果更新了，執行步驟9；否則執行步驟11；

步驟9：在和g_best之間使用局部搜索策略，進行精確搜索；

步驟10：采用實整數解碼機制更新和g_best；

步驟11：更新；

步驟12：如果的絕對值大于1，隨機產生一個（0,1）之間的，否則執行步驟3；

步驟13：返回g_best，結束。

2.根據權利要求1所述的一種混合粒子群禁忌搜索算法求解作業車間調度問題，其特征是：所述步驟5簡單的TSAB禁忌搜索描述如下：

（1）、初始解：本算法TSAB的初始解由改進的PSO提供；

（2）、鄰域結構：TSAB的鄰域定義為互換一臺設備上相鄰兩道工序，鄰域結構直接影響TSAB局部搜索的能力；

（3）、禁忌表：TSAB的解通過禁忌表的記憶結構確定是否承認新的鄰域，禁忌表由maxt個最近出現的解組成，如果一個潛在解出現在禁忌表，它不會被重拜訪直到它達到過期點。

3.根據權利要求1所述的一種混合粒子群禁忌搜索算法求解作業車間調度問題，其特征是：所述步驟4使用實整數編碼機制將PSO的實數解轉化為TSAB的整數解，其詳細過程如下：

設一個n個工件m臺設備的作業車間調度問題，搜索空間有n*m個維度，一個粒子的第d個維度表示為表示一道工序的權重，在實整數編碼機制中，按升序排序，使用一個整數序列記錄這些有序的數；每一個工件由幾道工序組成，通過向上取整將整數轉換為工件指數，從左至右依次掃描這個工件指數置換，將其轉換為一個可行的工序順序，再通過式（2）： ， 轉換成滿足TSAB要求的工序在設備上的加工順序。

4.根據權利要求1所述的一種混合粒子群禁忌搜索算法求解作業車間調度問題，其特征是：所述步驟6禁忌搜索之后需要將整數解解碼為實數解以進行粒子群優化，實整數解碼方法的過程描述如下：

（1）令B為一個調度方案解，映射TSAB的一個n*m的向量解N到一個m*n的矩陣M，M中的元素表示設備i上第j道工序的工件指數，我們用F記錄M中第一列每一臺設備上的工序，S記錄F中對應的一個工件的工序序列號；

（2）K=1：長度（F）

如果F(k)的前一道屬于某個工件的工序已經被調度，找到F中與F(k)具有相同的工件指數，將他們存儲到向量C；

（3）找到向量C中在S中值最小的工序d，表示一個工件中加工優先級最高的工序，附加這個工序到B，從F和C中刪除d，然后將設備i上這道工序的下一道工序附加給F；

（4）基于更新的F更新S；

（5）F非空返回第（2）步；

（6）使用B為序列號將PSO的初始連續解按照升序排序。

5.根據權利要求1所述的一種混合粒子群禁忌搜索算法求解作業車間調度問題，其特征是：所述步驟9在和g_best之間使用局部搜索策略，進行精確搜索，搜索步驟如下：

（1）記錄第i個個體粒子獲得的最優潛在方案，記錄種群獲得的最優潛在方案；

（2）Z=1：長度（

如果,找到，一步一步將移向，對于每一個可行的加工順序，計算并記錄總完工時間；

（3）找到最小的，更新和。