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

在審

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

所屬領域

本發明涉及作業車間調度技術領域。

背景技術

作業車間調度問題(Job-shop Scheduling Problem)是許多實際生產調度問題的簡化模型，具有廣泛的應用背景，譬如生產制造、交通規則、郵電通信、大規模集成電路設計等問題。作為一類滿足任務配置和順序約束要求的分配問題，JSP已被證明是一個典型的NP_hard問題，它的求解難度圓圓大于流水線調度問題。針對解決作業車間調度問題的算法一直是學術界和工程界共同關注的重要課題。

現有很多算法被用于解決JSP問題，包括遺傳算法、粒子群算法等，但沒有一種算法能夠直接將車間作業的屬性作為參數，最終得到一組明了的作業車間中生產調度方案解的算法。

布谷鳥搜索(Cuckoo Search,CS)算法是一種新的現代啟發式算法，由劍橋大學Yang和拉曼工程學院Deb于2009年提出的。該算法基于某些布谷鳥種類的巢寄生繁育行為和鳥類、果蠅等的萊維飛行(Levy flight)行為特征提出。布谷鳥搜索算法是模擬布谷鳥為尋找合適的產卵的鳥窩而隨機游走的尋窩過程。在這個宿主的選擇過程中，布谷鳥在繁殖期尋找與孵化期和育雛其相似的雛鳥食性基本相同、卵形與顏色易仿的宿主。多數情況下，宿主一旦識別出寄生卵，就將寄生卵扔出或棄巢，在其他地方另建新巢。而布谷鳥在下一次選擇宿主的時候也會放棄該鳥巢而重新選擇。為了便于模擬布谷鳥的尋窩方式，Yang和Deb提出了一下3個假設：(1)布谷鳥一次只產一個蛋，并隨機選擇鳥窩位置進行孵化；(2)在隨機選擇的一組鳥窩中，最好的鳥窩位置將被保留到下一代；(3)可利用宿主的鳥窩數量n是固定的，宿主發現一個外來鳥蛋的概率為Pa。Pa可以近似看作n個位置較差的鳥窩被隨機產生的幾個新鳥窩替換的概率，通常設Pa為一個固定值。

傳統的布谷鳥算法具有很好的全局最優搜索能力，算法參數少易于實現，但是該算法搜索速度不夠快，計算精度不夠高，算法應用范圍不夠大，搜索活力不足。

發明內容

針對現有技術中存在的上述不足，本發明要解決的技術問題是提供一種改進的布谷鳥搜索算法解決作業車間調度問題。

本發明的目的是克服現有技術中存在的：傳統的布谷鳥搜索算法假設條件多，搜索速度不夠快，計算精度不夠高，算法應用范圍也不夠大，以及沒有一種算法能夠直觀地給出作業車間調度方案的算法。

本發明要實現的目標是：最小化最大完工時間。

本發明為實現上述目的所采用的技術方案是：一種改進的布谷鳥搜索算法解決作業車間調度問題。該算法的具體步驟如下：

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

步驟2：初始化鳥窩位置(工件加工完成時間)：根據訂單周期T_o，訂單收益R，工件加工時間長度三個方面來確定鳥窩初始位置；

步驟3：確定編碼規則：按照編碼規則將鳥窩位置(完成時間)轉換為工序排列；

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

步驟5：更新鳥窩位置：考慮了鳥窩數量變化的情況。增加，減少，以及增加的工件訂單是否為緊急訂單的情況；

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

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

本發明的有益效果是：

1、確定了布谷鳥算法中外來鳥蛋的計算方式，精確高效，使算法更加適用于實際生產環境中。

2、對于布谷鳥搜索算法在車間調度問題中的應用上，確定了鳥窩的初始位置的計算方式，使算法結果更加精確，同時計算方法簡單，方便高效，實用性高。

3、突破了布谷鳥算法的三個假設條件之一：鳥窩數量不變。本發明在考慮鳥窩數量增加的基礎上，考慮了鳥窩數量減少的情況，使算法的應用范圍更廣。

4、確定了訂單估計完成時間的計算方法。

附圖說明

一種改進布谷鳥搜索算法的基本流程圖

具體實施方式

為了使本發明的目的、技術方案及發明內容更加清楚，以下結合附圖詳細說明。

步驟1：初始化算法基本參數：設置鳥窩個數(工件數量)N,宿主發現外來

鳥蛋的概率Pa(作業搶占概率)，以及最大迭代次數MaxT或搜索精度ε：

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