[發明專利]一種解決柔性車間作業調度的元啟發式搜索方法

在審

• 申請號: 201410653284.4
• 申請日: 2014-11-17
• 公開（公告）號: CN105678623A
• 公開（公告）日: 2016-06-15
• 發明（設計）人: 胡毅;于東;劉韻;羅企;房超;王萌
• 申請（專利權）人: 沈陽高精數控智能技術股份有限公司
• 主分類號: G06Q50/00
• 分類號: G06Q50/00;G06F17/30
• 代理公司: 沈陽科苑專利商標代理有限公司 21002
• 代理人: 許宗富

1.一種解決柔性車間作業調度的元啟發式搜索方法，其特征在于，包括以下步驟：

對作業進行編碼：將每個作業作為一個編碼序列，每個作業的每個工序為編碼序列中的基本元素；

使用四個角色：E、C、S、G來表示；其中E為疑似目標，用以表示可能的最優解；C為決策函數，用以收集信息并作出決策；S為搜索方向；G為搜索函數，負責向可能的目標進行搜索；對各個角色賦予初始值；

根據各個角色的功能和初始值搜索編碼空間，產生新的搜索目標，獲取當前搜索的最優值；

將搜索結果轉換成相應機器上的工序序列。

2.根據權利要求1所述的一種解決柔性車間作業調度的元啟發式搜索方法，其特征在于，所述基本元素為O_ijk，其中i表示作業號，j表示工序號，k表示機器號。

3.根據權利要求1所述的一種解決柔性車間作業調度的元啟發式搜索方法，其特征在于，所述角色C的初始值為參與該算法的CPU數量。

4.根據權利要求1所述的一種解決柔性車間作業調度的元啟發式搜索方法，其特征在于，所述編碼空間為工序的集合，維數為作業中最多的工序數。

5.根據權利要求1所述的一種解決柔性車間作業調度的元啟發式搜索方法，其特征在于，所述角色S為編碼空間內的搜索方向，初始值為S＝log(n*m*max{J_i}_1≤i≤n)，其中，n,m分別代表作業數和機器數，max{J_i}_1≤i≤n代表單位作業最多的工序數，J_i代表第i個作業。

6.根據權利要求1所述的一種解決柔性車間作業調度的元啟發式搜索方法，其特征在于，所述角色G取G＝2*n，其中，n代表作業數。

7.根據權利要求1所述的一種解決柔性車間作業調度的元啟發式搜索方法，其特征在于，所述決策函數為返回S和G上報的信息中較優的解集，所述較優的解集為集合中makespan前S個小的集合，集合中元素數量與s的個數相等；并將解集中最小的S個數的值作為E賦值給S。

8.根據權利要求1所述的一種解決柔性車間作業調度的元啟發式搜索方法，其特征在于，所述搜索函數為以C決策的目標為目標搜索，每次改變一維坐標，直到G與決策函數C傳過來的E的坐標值相等為止。

9.根據權利要求1所述的一種解決柔性車間作業調度的元啟發式搜索方法，其特征在于，所述搜索編碼空間，產生新的搜索方向，獲取當前搜索的最優值，包括以下步驟：

1)角色C將函數值賦值給角色S，或按照一定概率隨機產生新的目標賦值給角色S，即：其中，p＝1、0.9、0.8、…0；初始時設p＝1；

2)角色S將目標賦值給角色C；

3)角色C將疑似目標E賦值給角色G；

4)角色G隨機產生初始序列，接收C傳來的E值，每次只移動一維，如果G的當前值優于E的值，即makespan小于E，則向角色C匯報；

5)返回步驟1)，p減0.1；直到p＝0為止；此時得到的角色C值為當前最優值。

10.根據權利要求1所述的一種解決柔性車間作業調度的元啟發式搜索方法，其特征在于，所述將排序好的序列轉換成機器上的工序序列，具體為：將相應工序所在的機器的先后順序，以及每個作業的工序順序，以及前后工序結束時間的制約關系。