作業車間調度問題的布谷鳥搜索算法求解

姚遠遠，葉春明

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

1 引言

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

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

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

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

2 作業車間調度問題的數學描述

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

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

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

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

3 布谷鳥搜索算法的優化機理

3.1 算法仿生原理

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

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

3.2 算法的數學描述與分析

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

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

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

其中

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

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

4 基于布谷鳥搜索算法的作業車間調度問題求解

4.1 編碼方式

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

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

4.2 算法流程

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

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

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

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

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

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

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

（7）輸出最優調度值和對應的調度解方案。

5 仿真實驗

圖1 CS算法流程圖

鑒于JSP的重要性和代表性，許多研究工作者設計了若干典型問題（benchmarks），用以測試和比較不同方法的優化性能，典型的Job-shop調度問題有FT類、LA類、ABZ類、ORB類、SWV類、YN類、TD類和DMU類等，其中以FT類、LA類和TD類調度問題的研究居多。LA類問題由Lawrence（1984）給出，包括40個典型問題，命名為LA1～LA40，對應8個不同規模，每一規模包含 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，FA）所得結果進行比較。

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

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

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

圖2 LA01問題三種算法各獨立運行30次的最優結果分布圖

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

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

表3 LA01問題工藝約束

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

圖3 基于CS算法的LA01問題運行10次尋優曲線圖

圖4 CS算法當迭代次數分別為300和1 000時最優結果分布

表4 CS算法求解出的LA01問題最優解調度方案

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

6 結束語

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

[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]王凌.智能優化算法及其應用[M].北京：清華大學出版社，2001：10-100.

[9]羅亞波.作業系統調度優化理論與方法[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.