[發明專利]一種改進的布谷鳥搜索算法解決作業車間調度問題

在審

• 申請號: 201610309164.1
• 申請日: 2016-05-11
• 公開（公告）號: CN106611276A
• 公開（公告）日: 2017-05-03
• 發明（設計）人: 姜艾佳;胡成華
• 申請（專利權）人: 四川用聯信息技術有限公司
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06N3/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種改進的布谷鳥搜索算法解決作業車間調度問題，該算法涉及作業車間調度技術領域，其特征是：該算法的步驟如下：

步驟1：初始化算法基本參數：設置鳥窩個數（工件數量）N,宿主發現外來鳥蛋的概率Pa（作業搶占概率），以及最大迭代次數MaxT或搜索精度：

其中，n為第L優先級的鳥巢（工件）數量；

步驟2：初始化鳥窩位置（工件加工完成時間）：根據訂單周期，訂單收益R，工件加工時間長度三個方面來確定鳥窩初始位置，具體方式如下：

其中，R為完成該訂單所獲收益，no為訂單o的工件數量；

步驟3：確定編碼規則：按照編碼規則將鳥窩位置（完成時間）轉換為工序排列，采用基于工序的編碼規則編碼，即染色體由個基因組成，他們表示一個工序的排列，在這個工序排列中每個工件號最多出現m次，其染色體是由一個二維空間點（x,y）表示，即第x個訂單的第y個工件；例如，的實例，染色體序列為（1,1）（1,2）（2,1）（1,1）（3,1）（3,1）（3,3）（3,2）（1,2）（1,2）（1,1）（1,4），那么，它對應的工件加工序列為：

其中，表示第t個訂單的第i個工件的第j道工序，j表示工件i出現的次數，因此，上面例子的染色體序列表達的意思是先加工順序為：第1個訂單的第1個工件的第1道工序，加工第1個訂單第2個工件的第1道工序，在加工第2個訂單第1個工件的第1道工序，加工第1 個訂單第1個工件的第2道工序，以此類推，最后加工第1個訂單第4個工件的第1道工序，因此在解碼時就可以按照工件的出現順序轉化為一個調度方案；

步驟4：計算目標函數值：計算各鳥窩位置對應的目標函數值，并獲得當前最優鳥窩位置，具體實現為：

目標函數：

（1）

約束條件：

其中，式（1）表示目標函數，即完成時間（Makespan）；式（2）表示工藝約束條件決定的每個工件的操作的先后順序；式（3）表示加工每個工件的每臺機器的先后順序；式（4）表示完工時間變量約束條件；式（5）表示變量可能的取值大小，式（6）表示第o個訂單的所有工件最大完成時間小于訂單周期的時間約束；上述公式中所涉及的符號定義含義如下：分別為第o個訂單（或階數）中的第i個工件在機器k上的完成時間點和加工時間長度；M是一個足夠大的整數； 分別為指示系數和指示變量，其含義為：

步驟5：更新鳥窩位置：

（1）一種情況：如果沒有新的鳥窩出現（鳥窩數量沒有增加（沒有新的訂單的出現））：開始迭代，保留上代最優鳥窩位置不變，更新鳥窩位置（即全局搜索），從而隨機產生下一代鳥窩，并評估位置更新后每個鳥窩的目標函數值，記錄當前最優鳥窩位置，具體實施方案如下數學公式所示：

（9）

其中，表示第i只布谷鳥在第t代的鳥窩位置（在車間調度問題中用表示），是步長大小參數，一般取，參數S是隨機游動的步長，計算公式如下：

（10）

其中，

（11）

（12）

在局部搜索時對每一鳥窩位置按條件進行更新：用一個隨機數Ra作為鳥窩主人發現外來鳥蛋的概率并與Pa進行比較，若Ra>Pa，則隨機改變鳥窩位置，否則保持原來位置不變,并計算位置移動后每個鳥窩的目標函數值，記錄當前最優鳥窩位置，用如下0-1規劃模型表示：

（13）

（2）另一種情況：如果有新的鳥窩出現（有新的訂單出現），鳥窩數量增加，即：N+H，H為新增的鳥窩數量，同時，判斷是否為緊急訂單：是，則做緊急訂單處理操作，把該訂單的工件設置為所需加工的工序的優先級，不是緊急訂單，則不做緊急處理；

緊急訂單處理操作如下：

計算緊急系數，緊急系數越大的訂單緊急程度越大，越需要得到優先處理，緊急系數的計算如下：

其中，為訂單o的估計完成時間，其計算方式為：

其中，，實數，R為完成該訂單所獲收益，no為訂單o的工件數量；

當有鳥窩數量減少（有訂單還沒加工完就被迫撤離）的時候，直接定義N=N-Z，其中，Z為減少的鳥窩數量，算法依舊依照上述算法執行；

步驟6：當到達最大搜索次數或滿足搜索精度時轉入步驟7，否則，轉步驟4進行下一次搜索；

步驟7：輸出最優調度值和對應的調度方案（染色體序列）。

2.根據權利要求1所述的一種改進的布谷鳥搜索算法解決作業車間調度問題，其特征是：本算法突破了布谷鳥算法的三個假設條件之一：鳥窩數量不變，在考慮鳥窩數量增加的基礎上，考慮了鳥窩數量減少的情況，使算法的應用范圍更廣，并且本算法確定了訂單估計完成時間的計算方法。