姚遠遠，葉春明

上海理工大學 管理學院，上海 200093

1 引言

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

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

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

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

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

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

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

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

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

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

3.1 算法仿生原理

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

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

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

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

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

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

其中

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

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

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

4.1 編碼方式

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

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

4.2 算法流程

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

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

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

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

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

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

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

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

5 仿真實驗

圖1 CS算法流程圖

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

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

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

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

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

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

表2 LA01問題時間加工矩陣 min

表3 LA01問題工藝約束

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

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

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

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

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

6 結(jié)束語

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

[9]羅亞波.作業(yè)系統(tǒng)調(diào)度優(yōu)化理論與方法[M].武漢：華中科技大學出版社，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.