姚遠(yuǎn)遠(yuǎn)，葉春明

上海理工大學(xué) 管理學(xué)院，上海 200093

1 引言

作業(yè)車間調(diào)度問題（Job-shop Scheduling Problem，JSP）是許多實(shí)際生產(chǎn)調(diào)度問題的簡(jiǎn)化模型，具有廣泛應(yīng)用背景，譬如生產(chǎn)制造、交通規(guī)劃、郵電通信、大規(guī)模集成電路設(shè)計(jì)等問題。作為一類滿足任務(wù)配置和順序約束要求的資源分配問題，JSP已被證明是一個(gè)典型的NP-hard問題[1]，它的求解難度遠(yuǎn)大于流水線調(diào)度問題，針對(duì)其算法的研究一直是學(xué)術(shù)界和工程界共同關(guān)注的重要課題。目前，制造業(yè)的競(jìng)爭(zhēng)日益激烈，制造企業(yè)正朝著有不同完工時(shí)間和產(chǎn)品要求的多類型、小批量的生產(chǎn)模式發(fā)展。如何利用現(xiàn)有資源，滿足加工任務(wù)所需各種約束，使所有任務(wù)能盡量按時(shí)完成，即如何有效地解決JSP，成為一個(gè)十分現(xiàn)實(shí)和迫切的問題。高效調(diào)度算法，可以大大提高生產(chǎn)效益和資源利用率，從而增強(qiáng)企業(yè)的競(jìng)爭(zhēng)能力，因此對(duì)JSP的研究有非常重要的理論和實(shí)用價(jià)值。

目前關(guān)于高效算法的研究與設(shè)計(jì)仍然是生產(chǎn)調(diào)度領(lǐng)域的重要研究?jī)?nèi)容，鑒于作業(yè)車間調(diào)度問題的復(fù)雜性，通常研究該問題的方法可分為三種類型：精確方法、啟發(fā)式算法和現(xiàn)代元啟發(fā)式算法。具體包括列舉法（如分支定界策略）、基于優(yōu)先規(guī)則的構(gòu)造性啟發(fā)式方法、移動(dòng)瓶頸法、神經(jīng)網(wǎng)絡(luò)方法、Lagrangian松弛法、遺傳算法、模擬退火、禁忌搜索、蟻群算法、粒子群算法、螢火蟲算法以及各種混合調(diào)度算法等。其中仿生智能群算優(yōu)化算法由于能夠在較短時(shí)間內(nèi)獲得較高質(zhì)量的解，廣泛用于求解各種生產(chǎn)調(diào)度問題，成為復(fù)雜優(yōu)化問題的有效解決途徑和國(guó)際研究熱點(diǎn)。

2009年，劍橋大學(xué)Yang和拉曼工程學(xué)院Deb提出了一種新型現(xiàn)代元啟發(fā)式算法——布谷鳥搜索（Cuckoo Search，CS）算法[2]，該算法基于某些布谷鳥種類的巢寄生（brood parasitism）繁育行為和鳥類、果蠅等的萊維飛行（Lévy flight）行為特征提出，具有控制參數(shù)少和能夠有效保持局部搜索和全局搜索之間平衡兩個(gè)優(yōu)點(diǎn)，已有研究表明該算法性能優(yōu)于粒子群算法和遺傳算法。目前，利用布谷鳥搜索算法求解優(yōu)化問題的研究還處于初步階段，其主要用于解決工程設(shè)計(jì)優(yōu)化問題[3-4]。最近，Yang和Deb[5]又提出一種多目標(biāo)布谷鳥搜索算法解決工程設(shè)計(jì)優(yōu)化問題?？v觀目前國(guó)內(nèi)外關(guān)于CS算法的研究成果，多集中于對(duì)連續(xù)優(yōu)化問題的研究，然而應(yīng)用CS算法解決離散問題的研究非常少見，僅有少數(shù)幾篇，如Ouyang Xinxin等[6]提出一種離散布谷鳥搜索算法解決球面旅行商問題，Burnwal等[7]提出基于布谷鳥搜索的方法解決柔性制造系統(tǒng)的調(diào)度優(yōu)化問題，其目標(biāo)函數(shù)是最小化延期懲罰成本和最大化機(jī)器時(shí)間利用率，但是還未見到采用該算法進(jìn)行作業(yè)調(diào)度問題的研究。因此，本文將嘗試應(yīng)用CS算法解決作業(yè)車間調(diào)度問題。

本文分析了布谷鳥搜索算法的優(yōu)化機(jī)理，在此基礎(chǔ)上應(yīng)用該算法求解作業(yè)車間調(diào)度的最小化最大完工時(shí)間問題，并介紹了具體的編碼方式和求解作業(yè)車間調(diào)度問題的算法流程，通過仿真實(shí)例驗(yàn)證了算法的正確性和有效性，并對(duì)其在離散組合優(yōu)化領(lǐng)域的優(yōu)化性能進(jìn)行評(píng)估。本文對(duì)生產(chǎn)調(diào)度問題高效調(diào)度算法的研究，有利于企業(yè)在生產(chǎn)過程中進(jìn)行合理有效地組織與安排，大大提高生產(chǎn)效益和資源利用率，提升生產(chǎn)系統(tǒng)的操作最優(yōu)性，并獲得顯著經(jīng)濟(jì)效益。

2 作業(yè)車間調(diào)度問題的數(shù)學(xué)描述

作為一類典型的加工調(diào)度問題，Job-shop調(diào)度問題可描述為[8]：n個(gè)工件在m臺(tái)機(jī)器上加工，Oij表示第i個(gè)工件在第j臺(tái)機(jī)器上的操作，相應(yīng)的操作時(shí)間Tij為已知，事先給定各工件在各機(jī)器上的加工次序（稱為技術(shù)約束條件），要求確定與技術(shù)約束條件相容的各機(jī)器上所有工件的加工次序，使加工性能指標(biāo)達(dá)到最優(yōu)。除技術(shù)約束外，通常還假定每一時(shí)刻每臺(tái)機(jī)器只能加工一個(gè)工件，且每個(gè)工件只能被一臺(tái)機(jī)器所加工，同時(shí)加工過程為不間斷，機(jī)器間緩沖區(qū)容量為無限。若各工件的技術(shù)約束條件相同，一個(gè)Job-shop問題就轉(zhuǎn)化為較簡(jiǎn)單的Flow-shop問題。當(dāng)各機(jī)器上各工件的加工次序也相同，則問題可進(jìn)一步轉(zhuǎn)化為置換Flow-shop問題。

作業(yè)車間調(diào)度問題的求解遠(yuǎn)復(fù)雜于流水線調(diào)度問題，主要原因可歸納為如下幾點(diǎn)：（1）由于調(diào)度解的編碼很復(fù)雜，使搜索操作難以達(dá)到高效的設(shè)計(jì)效果；（2）大量的調(diào)度解，在不考慮可行性的情況下，n個(gè)工件m臺(tái)機(jī)器的問題包含(n!)m種不同的排列；（3）工藝技術(shù)約束條件使得必須考慮解的可行性；（4）調(diào)度解的性能指標(biāo)計(jì)算需要耗費(fèi)大量時(shí)間，一次性能評(píng)價(jià)相當(dāng)于一個(gè)離散時(shí)間的仿真過程；（5）缺少搜索空間的結(jié)構(gòu)信息，通常存在多個(gè)分布無規(guī)則的局部極小解，最優(yōu)解往往被大量相鄰極小解所包圍。

關(guān)于JSP的求解往往要考慮生產(chǎn)調(diào)度實(shí)際期望達(dá)到的優(yōu)化指標(biāo)，問題的目標(biāo)函數(shù)是這些優(yōu)化指標(biāo)的抽象表示，JSP模型的目標(biāo)函數(shù)隨著企業(yè)所重點(diǎn)考慮因素的不同而改變。通常JSP所考慮的優(yōu)化目標(biāo)有三種[9]：任務(wù)的最大完工時(shí)間最短、任務(wù)的總的拖期最短和任務(wù)的提前/拖期懲罰代價(jià)最小。本文所考慮的優(yōu)化目標(biāo)是任務(wù)的最大完工時(shí)間最短，即完成所有任務(wù)所需的時(shí)間最短，對(duì)該指標(biāo)的優(yōu)化有利于提高單位時(shí)間內(nèi)設(shè)備的利用率，從而提高生產(chǎn)的實(shí)際效率。常見的作業(yè)車間調(diào)度問題基本數(shù)學(xué)模型有三種[9]：整數(shù)規(guī)劃模型、線性規(guī)劃模型和析取圖模型。本文采用Bake[10]給出的JSP整數(shù)規(guī)劃模型，n/m/G/Cmax調(diào)度問題的數(shù)學(xué)模型描述如下：

其中，式（1）表示目標(biāo)函數(shù)，即Makespan；式（2）表示工藝約束條件決定的每個(gè)工件的操作先后順序；式（3）表示加工每個(gè)工件的每臺(tái)機(jī)器的先后順序；式（4）表示完工時(shí)間變量約束條件；式（5）表示指示變量可能的取值大小。上述公式中所涉及的符號(hào)含義如下：Cik和pik分別為工件i在機(jī)器k上的完成時(shí)間和加工時(shí)間；M是一個(gè)足夠大的正數(shù)；aihk和xijk分別為指示系數(shù)和指示變量，其含義為：

3 布谷鳥搜索算法的優(yōu)化機(jī)理

3.1 算法仿生原理

在自然界中，布谷鳥通過巢寄生的行為方式進(jìn)行繁育，巢寄生是一種鳥類將卵產(chǎn)在其他鳥的鳥巢中，由其他鳥（義親）代為孵化和育雛的一種特殊的繁殖行為。其優(yōu)點(diǎn)是最大限度地提高鳥類成功繁殖的能力。在宿主的選擇上，布谷鳥在繁殖期尋找與孵化期和育雛期相似、雛鳥食性基本相同、卵形與顏色易仿的宿主，多為雀形目鳥類。而且它每飛到一個(gè)巢窩里只產(chǎn)一個(gè)卵，布谷鳥在產(chǎn)卵前常把宿主一枚卵移走，或全部推出巢外，迫使宿主重新產(chǎn)卵，來增加其卵被孵化的概率。巢寄生行為對(duì)宿主種群的影響大小不一，多數(shù)情況都會(huì)使宿主鳥繁殖率下降。為了繁衍宿主鳥也進(jìn)化出一套反寄生行為，宿主一旦識(shí)別出寄生卵，就將其扔出或棄巢，在其他地方另建新巢。巢寄生的協(xié)同進(jìn)化表現(xiàn)在長(zhǎng)期的適應(yīng)選擇中，寄生卵的大小、顏色、卵斑等特征都與其特定的宿主相似，這有利于降低其卵被拋棄的可能性從而提高繁殖率[11]。

在自然界中，很多動(dòng)物以隨機(jī)或者類似隨機(jī)的方式覓食。通常動(dòng)物的覓食路徑實(shí)際上是一個(gè)隨機(jī)游動(dòng)的過程，隨機(jī)游動(dòng)是粒子的下一個(gè)位置只依賴于當(dāng)前位置和轉(zhuǎn)移概率的一個(gè)馬氏鏈。不同研究已表明很多動(dòng)物和昆蟲的飛行行為表現(xiàn)出萊維飛行的典型特征[12]。萊維飛行屬于隨機(jī)游動(dòng)的一種，在萊維飛行中步長(zhǎng)分布滿足一個(gè)厚尾的穩(wěn)定分布，由萊維飛行產(chǎn)生的隨機(jī)步長(zhǎng)時(shí)大時(shí)小，在搜索過程中，大的步長(zhǎng)易于搜索全局最優(yōu)，小的步長(zhǎng)有助于提高搜索精度。目前萊維飛行行為已被用于優(yōu)化和最優(yōu)搜索領(lǐng)域，在智能優(yōu)化算法中采用萊維飛行，能擴(kuò)大搜索范圍、增加種群多樣性，更容易跳出局部最優(yōu)點(diǎn)[13]。另外研究還表明在不確定環(huán)境中萊維飛行可以最大化資源搜索效率。

3.2 算法的數(shù)學(xué)描述與分析

CS算法是一種隨機(jī)全局搜索算法，像GA、PSO一樣，CS是基于群體的優(yōu)化算法，在自然界中，布谷鳥以隨機(jī)或是類似隨機(jī)的方式尋找適合自己產(chǎn)蛋的鳥窩位置，為了便于模擬布谷鳥的尋窩方式，Yang和Deb提出了以下3個(gè)假設(shè)[2]：（1）布谷鳥一次只產(chǎn)一個(gè)蛋，并隨機(jī)選擇鳥窩位置進(jìn)行孵化；（2）在隨機(jī)選擇的一組鳥窩中，最好的鳥窩將會(huì)被保留到下一代；（3）可利用的宿主鳥窩數(shù)量n是固定的，宿主發(fā)現(xiàn)一個(gè)外來鳥蛋的概率為Pa∈[0，1]。Pa可以近似看作n個(gè)位置較差的鳥窩被隨機(jī)產(chǎn)生的幾個(gè)新鳥窩替換的概率，通常設(shè)Pa為一個(gè)固定值，本文取Pa=0.25。基于以上3條假設(shè)，布谷鳥搜索算法的基本步驟如下所示。

式中表示第i只布谷鳥在第t代的鳥窩位置，α＞0是步長(zhǎng)大小參數(shù)，與所研究問題范圍有關(guān)，此處取α=0.1可以使算法更高效。參數(shù)S是隨機(jī)游動(dòng)的步長(zhǎng)，本文采用Mantegna算法執(zhí)行萊維飛行[14]，步長(zhǎng)S計(jì)算公式如下：

其中，β是一個(gè)[1，2]之間的參數(shù)，此處取β=1.5，u和v服從正態(tài)分布如下所示：

其中

在局部搜索階段，用隨機(jī)游動(dòng)（點(diǎn)和矩陣的乘積：隨機(jī)步長(zhǎng)大小×概率矩陣）產(chǎn)生的新鳥窩替代位置較差部分的鳥窩，用參數(shù)Pa表示位置較差鳥窩被發(fā)現(xiàn)的概率，每一鳥窩按條件更新位置，如下概率矩陣所示：

其中，隨機(jī)數(shù)Ra∈[0，1]，表示鳥窩主人發(fā)現(xiàn)外來鳥蛋的概率，Pi，j表示第i個(gè)鳥窩的第j維變量被發(fā)現(xiàn)的概率。具體操作如下程序所示（K是一個(gè)n行1列的矩陣，元素取值為1或0，取決于隨機(jī)值Ra是否大于Pa，當(dāng)元素取0時(shí)，下面公式運(yùn)算時(shí)，鳥窩位置不移動(dòng)，相當(dāng)于乘零；當(dāng)元素取1時(shí)，移動(dòng)鳥窩位置）：

4 基于布谷鳥搜索算法的作業(yè)車間調(diào)度問題求解

4.1 編碼方式

本文在求解JSP問題時(shí)采用基于工序的編碼規(guī)則，即染色體由n×m個(gè)基因組成，它們表示一個(gè)工序的排列，在這個(gè)工序排列中每個(gè)工件號(hào)均出現(xiàn)且只能出現(xiàn)m次。例如4工件×3機(jī)器的示例，其染色體是121334412234。因此它對(duì)應(yīng)的工序加工序列為：

其中Ji，j表示第i個(gè)工件的第j道工序，j表示工件i出現(xiàn)的次數(shù)。因此表達(dá)的意思為先加工第1個(gè)工件的第1道工序，再加工第2個(gè)工件的第1道工序，再加工第1個(gè)工件的第2道工序，再加工第3個(gè)工件的第1道工序，依此類推，最后加工第4個(gè)工件的第3道工序。因此在解碼時(shí)就可以按照工件的出現(xiàn)順序轉(zhuǎn)化為一個(gè)調(diào)度方案。

4.2 算法流程

綜上所述，求解作業(yè)車間調(diào)度問題的布谷鳥搜索算法流程如下（見圖1）：

（1）初始化算法基本參數(shù)：設(shè)置鳥窩個(gè)數(shù)n、宿主發(fā)現(xiàn)外來鳥蛋的概率Pa，以及最大迭代次數(shù)MaxT或搜索精度ε。

（2）隨機(jī)初始化鳥窩位置，按照4.1節(jié)所述基于工序的編碼規(guī)則將鳥窩位置轉(zhuǎn)換為工序排列，計(jì)算各鳥窩位置對(duì)應(yīng)的目標(biāo)函數(shù)值（本文目標(biāo)函數(shù)為minCmax，根據(jù)公式（1）～（7）），并獲得當(dāng)前最優(yōu)鳥窩位置。

（3）開始迭代，保留上代最優(yōu)鳥窩位置不變，按位置更新公式（8）通過萊維飛行對(duì)其他所有鳥窩位置進(jìn)行更新（即全局搜索），從而隨機(jī)產(chǎn)生下一代鳥窩，并評(píng)估位置更新后每個(gè)鳥窩的目標(biāo)函數(shù)值，記錄當(dāng)前最優(yōu)鳥窩位置。在這一階段中，具體通過公式（9）～（11）采用Mantegna算法執(zhí)行萊維飛行。

（4）在局部搜索時(shí)對(duì)每一鳥窩位置按條件進(jìn)行更新：用一個(gè)隨機(jī)數(shù)Ra作為鳥窩主人發(fā)現(xiàn)外來鳥蛋的概率并與Pa進(jìn)行比較，若Ra＞Pa，則隨機(jī)改變鳥窩位置，否則保持原來位置不變（根據(jù)公式（12）進(jìn)行判斷），并計(jì)算位置移動(dòng)后每個(gè)鳥窩的目標(biāo)函數(shù)值，記錄當(dāng)前最優(yōu)鳥窩位置。

（5）比較本次迭代和上一次迭代鳥窩位置的最優(yōu)值，如果新的最優(yōu)值小于原最優(yōu)值，則把新的最優(yōu)值賦予當(dāng)前最優(yōu)鳥窩位置的目標(biāo)函數(shù)值。

（6）當(dāng)達(dá)到最大搜索次數(shù)或滿足搜索精度時(shí)轉(zhuǎn)入（7），否則，轉(zhuǎn)（3）進(jìn)行下一次搜索。

（7）輸出最優(yōu)調(diào)度值和對(duì)應(yīng)的調(diào)度解方案。

5 仿真實(shí)驗(yàn)

圖1 CS算法流程圖

鑒于JSP的重要性和代表性，許多研究工作者設(shè)計(jì)了若干典型問題（benchmarks），用以測(cè)試和比較不同方法的優(yōu)化性能，典型的Job-shop調(diào)度問題有FT類、LA類、ABZ類、ORB類、SWV類、YN類、TD類和DMU類等，其中以FT類、LA類和TD類調(diào)度問題的研究居多。LA類問題由Lawrence（1984）給出，包括40個(gè)典型問題，命名為L(zhǎng)A1～LA40，對(duì)應(yīng)8個(gè)不同規(guī)模，每一規(guī)模包含 5個(gè)問題，分別為10×5，15×5，20×5，10×10，15×10，20×10，30×10，15×15。為了便于比較并驗(yàn)證布谷鳥搜算算法（CS）求解JSP的性能，本研究隨機(jī)選取LA類10個(gè)基準(zhǔn)問題作為算例進(jìn)行仿真測(cè)試，并與基本粒子群算法（Basic Particle Swarm Optimization，BPSO）和螢火蟲算法（Firefly Algorithm，F(xiàn)A）所得結(jié)果進(jìn)行比較。

實(shí)驗(yàn)仿真環(huán)境為：操作系統(tǒng)Windows 7，處理器主頻2.30 GHz，CPU Intel?CoreTMi3-2350M，和內(nèi)存4 GB，采用MATLAB R2010a實(shí)現(xiàn)算法編程。算法參數(shù)設(shè)置如下：布谷鳥搜索算法中，鳥巢個(gè)數(shù)n=30，宿主發(fā)現(xiàn)外來鳥蛋的概率Pa=0.25；螢火蟲算法中，螢火蟲數(shù)n=30，光強(qiáng)吸引系數(shù)γ=1.0，最大吸引度β0=1.0，步長(zhǎng)因子α=0.2；基本粒子群算法中，粒子數(shù)n=30，學(xué)習(xí)因子c1=0.8，c2=1.2，慣性權(quán)重w=0.5。最大迭代次數(shù)均為MaxT=300，每種算法均獨(dú)立運(yùn)行30次，測(cè)試結(jié)果如表1所示。

表1中，BPSO代表基本粒子群算法，F(xiàn)A代表螢火蟲算法，CS是布谷鳥搜索算法。c*為問題已知最優(yōu)值；Δmin為算法運(yùn)行30次得到的最小完工時(shí)間；Δmax為最大完工時(shí)間；Δavg為平均完工時(shí)間；Δstd為完工時(shí)間標(biāo)準(zhǔn)方差（其中Δavg、Δstd為四舍五入后所得結(jié)果）；加粗的數(shù)字代表最優(yōu)值。為比較各算法性能，本文對(duì)隨機(jī)選擇的LA類10個(gè)測(cè)試問題的4項(xiàng)指標(biāo)進(jìn)行衡量。從測(cè)試數(shù)據(jù)可以看出，CS算法的測(cè)試結(jié)果整體上效果優(yōu)于BPSO和FA算法。其中CS算法有7個(gè)問題找到最優(yōu)值，BPSO算法有6個(gè)問題找到最優(yōu)值，F(xiàn)A算法僅有4個(gè)問題找到最優(yōu)值。在獨(dú)立運(yùn)行30次中，CS算法對(duì)LA05、LA06、LA10和 LA14這4個(gè)問題都能達(dá)到100%的尋優(yōu)率，其他兩種算法均未能達(dá)到100%尋優(yōu)率。雖然BPSO尋優(yōu)能力優(yōu)于FA算法，但是魯棒性較差。另外，程序運(yùn)行中還發(fā)現(xiàn)三種算法的運(yùn)行時(shí)間是FA＜CS?BPSO，對(duì)于每一個(gè)算例，F(xiàn)A運(yùn)行耗時(shí)遠(yuǎn)少于其他兩種算法，CS和BPSO的運(yùn)行時(shí)間基本相同。

表1 BPSO、FA和CS三種算法測(cè)試結(jié)果分析 min

圖2 LA01問題三種算法各獨(dú)立運(yùn)行30次的最優(yōu)結(jié)果分布圖

為了更深入分析CS算法解決作業(yè)車間調(diào)度問題的效果，本文重點(diǎn)對(duì)LA01問題具體分析（LA01問題時(shí)間加工矩陣見表2，該問題工藝約束見表3）。圖2是三種算法各獨(dú)立運(yùn)行30次的最優(yōu)結(jié)果分布圖，算法參數(shù)設(shè)置如前面所述，由圖可見，獨(dú)立運(yùn)行30次中，就尋優(yōu)能力而言，CS算法有14次擊中已知最優(yōu)值，BPSO算法僅1次擊中最優(yōu)值，F(xiàn)A算法離最優(yōu)值尚有一段距離。從解的穩(wěn)定性方面考慮，CS算法魯棒性最強(qiáng)，其最壞情況與最好情況差值為20，而BPSO和FA分別為164和67。

表2 LA01問題時(shí)間加工矩陣 min

表3 LA01問題工藝約束

為了驗(yàn)證CS算法的收斂性，基于LA01問題，將CS算法獨(dú)立運(yùn)行10次，每次迭代300代，鳥窩個(gè)數(shù)為30，Pa=0.25，10次獨(dú)立運(yùn)行的最優(yōu)結(jié)果分別是：666、675、672、666、668、678、666、672、678和673，尋優(yōu)曲線見圖3，其中有3次結(jié)果最好，最好情況為666，最壞情況為678，平均值為671.40，標(biāo)準(zhǔn)方差為4.742 2?；贑S算法求解出的LA01問題最優(yōu)解調(diào)度方案見表4。

圖3 基于CS算法的LA01問題運(yùn)行10次尋優(yōu)曲線圖

圖4 CS算法當(dāng)?shù)螖?shù)分別為300和1 000時(shí)最優(yōu)結(jié)果分布

表4 CS算法求解出的LA01問題最優(yōu)解調(diào)度方案

從表1還可以發(fā)現(xiàn)，三種算法對(duì)于LA17和LA20這種規(guī)模稍大的10工件×10機(jī)器問題似乎無能為力，均不能搜索到最優(yōu)值，但是相比較而言CS算法的尋優(yōu)結(jié)果更接近已知最優(yōu)值。為了測(cè)試參數(shù)設(shè)置對(duì)尋優(yōu)能力的影響，以LA20為例進(jìn)行實(shí)驗(yàn)，分別設(shè)置最大迭代次數(shù)為300和1 000兩種情況，其他參數(shù)保持不變。實(shí)驗(yàn)結(jié)果如圖4所示，由圖可見，當(dāng)?shù)螖?shù)為1 000時(shí)，運(yùn)行結(jié)果普遍好于300次的結(jié)果，但是對(duì)于尋找最優(yōu)值方面見效不大。本文還嘗試了測(cè)試?guó)B窩數(shù)量n對(duì)尋優(yōu)能力的影響，發(fā)現(xiàn)增大鳥窩數(shù)量將大大增加程序運(yùn)行時(shí)間，而且也不一定能獲得更優(yōu)值?？傊?，要解決大規(guī)模的作業(yè)車間作業(yè)調(diào)度問題還需對(duì)布谷鳥搜索算法的優(yōu)化機(jī)理進(jìn)行改進(jìn)，這也是本文進(jìn)一步的研究方向。

6 結(jié)束語

本文采用一種新型的仿生智能群算優(yōu)化算法——布谷鳥搜索算法求解最小化最大完工時(shí)間的作業(yè)車間調(diào)度問題。通過仿真實(shí)驗(yàn)，驗(yàn)證了該算法與基本粒子群算法和螢火蟲算法相比，具有實(shí)驗(yàn)參數(shù)少、收斂速度快、魯棒性強(qiáng)等優(yōu)點(diǎn)。雖然對(duì)于較大規(guī)模的Job-shop生產(chǎn)調(diào)度問題，布谷鳥搜索算法不能搜索到已知最優(yōu)值，但是相比其他兩種算法，更接近最優(yōu)值。表明了布谷鳥搜索算法在解決生產(chǎn)調(diào)度問題中的可行性和有效性，并有著廣泛的應(yīng)用前景。今后CS搜索算法可進(jìn)一步用于研究具有不同約束條件的多目標(biāo)作業(yè)車間調(diào)度問題；也可以將CS算法和其他智能優(yōu)化算法進(jìn)行混合，從而產(chǎn)生更高效的混合優(yōu)化算法。

[1]Garey M R，Johnson D S，Sethi R.The complexity of flowshop and jobshop scheduling[J].Mathematics of Operations Research，1976，1（2）：117-129.

[2]Yang Xinshe，Deb S.Cuckoo search via Lévy flights[C]//2009 World Congress on Nature&Biologically Inspired Computing.New York：IEEE Publications，2009：210-214.

[3]Gandomi A H，Yang Xinshe，Alavi A H.Cuckoo search algorithm：a metaheuristic approach to solve structural optimization problems[J].Engineering with Computers，2013，29（1）：17-35.

[4]Durgun I，Yildiz A R.Structural design optimization of vehicle componentsusing cuckoo search algorithm[J].Materials Testing，2012，54（3）：185-188.

[5]Yang Xinshe，Deb S.Multiobjective cuckoo search for design optimization[J].Computers&Operations Research，2013，40（6）：1616-1624.

[6]Ouyang Xinxin，Zhou Yongquan，Luo Qifang，et al.A novel discrete cuckoo search algorithm for spherical traveling salesman problem[J].Applied Mathematics& Information Sciences，2013，7（2）：777-784.

[7]Burnwal S，Deb S.Scheduling optimization of flexible manufacturing system using cuckoo search-based approach[J].The InternationalJournalofAdvanced Manufacturing Technology，2013，64（5/8）：951-959.

[8]王凌.智能優(yōu)化算法及其應(yīng)用[M].北京：清華大學(xué)出版社，2001：10-100.

[9]羅亞波.作業(yè)系統(tǒng)調(diào)度優(yōu)化理論與方法[M].武漢：華中科技大學(xué)出版社，2011：1-10.

[10]Baker K.Inroduction to sequencing and scheduling[M].New York：John Wiley&Sons，1974：1-15.

[11]Payne R B，Sorenson M D，Klitz K.The cuckoos[M].New York：Oxford University Press，2005：1-20.

[12]Brown C T，Liebovitch L S，Glendon R.Lévy flights in Dobe Ju/'hoansi foraging patterns[J].Hum Ecol，2007，35：129-138.

[13]Shlesinger M F.Search research[J].Nature，2006，443：281-282.

[14]Yang Xinshe.Nature-inspired metaheuristic algorithms[M].2nd ed.Frome：Luniver Press，2010.