工藝規劃與車間調度的智能算法（簡體書）

2015年，國家開始實施《中國制造2025》以全面提升中國制造業的發展水平。智能制造是主攻方向，而制造過程的智能化是實現智能制造的核心技術之一。制造過程的智能工藝規劃與車間調度技術對於優化企業生產流程、提高效率、降低成本等具有重要意義，是實現制造過程智能化的關鍵。在實際生產中，工藝規劃與車間調度問題呈現出規模大、目標多、約束復雜、不可導及解空間復雜等特性，導致數學精確方法難以求解。近年來，智能算法在上述問題中表現出了高效的求解性能，是智能制造領域學術界和工業界備受關注的前沿研究熱點。

本書在作者團隊多年研究、教學和工程實踐的基礎上，結合生產實際需求，首先對柔性工藝規劃、裝配序列規劃、車間調度等問題進行了系統闡述和分類，在已有智能算法研究成果的基礎上，總結了面向工藝規劃與車間調度問題的遺傳算法、遺傳規劃、蜜蜂交配優化算法、Memetic算法、和聲搜索算法、布谷鳥算法、類電磁機制算法、人工蜂群算法、入侵性雜草優化算法、粒子群優化算法、基因表達式編程算法與遺傳變鄰域搜索算法等智能算法。以作者近年來在上述問題及方法的研究成果為主，系統地闡述了工藝規劃與車間調度問題的智能算法的設計思路與過程，為廣大研究人員采用智能算法解決實際工程問題提供了有效的技術手段與參考。

全書共包含13章： 第1章緒論； 第2章遺傳算法及其在柔性工藝規劃中的應用； 第3章遺傳規劃及其在柔性工藝規劃中的應用； 第4章蜜蜂交配優化算法及其在柔性工藝規劃中的應用； 第5章Memetic算法及其在裝配序列規劃中的應用； 第6章和聲搜索算法及其在裝配序列規劃中的應用； 第7章布谷鳥算法及其在流水車間調度中的應用； 第8章類電磁機制算法及其在流水車間調度中的應用； 第9章人工蜂群算法及其在批量流流水車間調度中的應用； 第10章入侵性雜草算法及其在批量流流水車間調度中的應用； 第11章粒子群優化算法及其在柔性作業車間調度中的應用； 第12章基因表達式編程及其在車間動態調度中的應用和第13章遺傳變鄰域搜索算法及其在IPPS中的應用。

本書所涉及的研究成果得到了作者主持或參與的國家杰出青年科學基金項目（51825502）、國家自然科學基金重點項目（51435009）、國家自然科學基金項目（51375004、51421062、60973086、51005088、50305008、51775216）、國家科技支撐計劃（2015BAF01B04）、新世紀優秀人才支持計劃（NCET080232）和國家“863”計劃（2006AA04Z131）等項目的資助。本書部分內容引用了國內外同行專家的研究成果，在此表示誠摯的謝意。感謝《排序與調度叢書》編委會專家在本書撰寫中所提出的寶貴意見，感謝張潔、潘全科在本書審稿中所做出的細致嚴謹的工作，感謝清華大學出版社編輯汪操在本書出版中所付出的辛勤勞動，感謝華中科技大學機械科學與工程學院、數字制造裝備與技術國家重點實驗室各位同仁的大力支持。此外，華中科技大學機械科學與工程學院的聶黎、桑紅燕、文笑雨、張春江、盧超、曾冰、石楊、黃繼達、萬亮、錢衛榮等研究生也參與了相關研究工作，在此一並表示感謝。

由於作者水平有限，加之時間倉促，本書難免存在疏漏甚至錯誤之處，許多內容有待完善和深入研究，敬請廣大讀者批評指正。

作者華中科技大學2018年11月

第1章緒論

1.1工藝規劃與車間調度問題

1.1.1工藝規劃

1.1.2裝配序列規劃

1.1.3車間調度

1.2優化算法

1.2.1精確方法

1.2.2近似方法

1.3本書主要內容

參考文獻

第一部分工藝規劃的智能算法

第2章遺傳算法及其在柔性工藝規劃中的應用

2.1遺傳算法基本原理

2.1.1遺傳算法

2.1.2遺傳算法基本框架

2.2基於遺傳算法的柔性工藝規劃方法

2.2.1柔性工藝規劃問題描述

2.2.2遺傳算法求解柔性工藝規劃問題

2.2.3實驗結果與分析

2.3本章小結

參考文獻

第3章遺傳規劃及其在柔性工藝規劃中的應用

3.1遺傳規劃的基本原理

3.1.1遺傳規劃

3.1.2遺傳規劃符號及算子

3.1.3遺傳規劃基本框架

3.2基於遺傳規劃的柔性工藝規劃方法

3.2.1基於遺傳規劃的柔性工藝規劃算法

3.2.2實驗結果與分析

3.3本章小結

參考文獻

第4章蜜蜂交配優化算法及其在柔性工藝規劃中的應用

4.1蜜蜂交配優化算法基本原理

4.2基於HBMO算法的柔性工藝規劃方法

4.2.1柔性工藝規劃問題

4.2.2編碼和解碼

4.2.3蜂群初始化

4.2.4幼蜂生成階段

4.2.5工蜂培育幼蜂階段

4.2.6HBMO算法求解柔性工藝規劃問題的流程

4.2.7算例分析

4.3本章小結

參考文獻

第5章Memetic算法及其在裝配序列規劃中的應用

5.1Memetic算法的基本原理

5.1.1Memetic算法的提出

5.1.2Memetic算法的基本概念

5.2基於Memetic算法的裝配序列規劃方法

5.2.1裝配序列規劃

5.2.2基於Memetic算法的裝配序列規劃算法設計

5.2.3實例計算與分析

5.3本章小結

參考文獻

第6章和聲搜索算法及其在裝配序列規劃中的應用

6.1和聲搜索算法的基本原理

6.1.1和聲搜索算法的提出

6.1.2和聲搜索算法的應用

6.1.3和聲搜索算法的改進

6.2基於和聲搜索算法的線性加權裝配序列規劃方法

6.2.1和聲的編碼

6.2.2基於LPV規則的裝配序列轉化

6.2.3算法的改進

6.2.4算法的求解步驟

6.2.5實例驗證和分析

6.3基於和聲搜索算法的多目標裝配序列規劃方法

6.3.1IMOHS算法求解步驟

6.3.2實例驗證和分析

6.4本章小結

參考文獻

第二部分車間調度的智能算法

第7章布谷鳥算法及其在流水車間調度中的應用

7.1布谷鳥算法的基本原理

7.1.1布谷鳥算法

7.1.2Lévy飛行

7.1.3布谷鳥算法的基本理論框架

7.2改進的布谷鳥算法

7.2.1教學優化算法

7.2.2基於教學優化機制的改進布谷鳥算法

7.3基於TLCS的流水車間調度方法

7.3.1置換流水車間調度問題

7.3.2隨機鍵的引入

7.3.3求解PFSP的TLCS算法流程

7.3.4算例分析

7.4本章小結

參考文獻

第8章類電磁機制算法及其在流水車間調度中的應用

8.1類電磁機制算法的基本原理

8.1.1類電磁機制算法

8.1.2類電磁機制算法的步驟

8.2基於離散EM算法的分布式置換流水車間調度方法

8.2.1分布式置換流水車間調度問題

8.2.2基於pathrelinking的離散EM算法

8.2.3實例驗證

8.3本章小結

參考文獻

第9章人工蜂群算法及其在批量流流水車間調度中的應用

9.1人工蜂群算法的基本原理

9.1.1人工蜂群算法的基本理論

9.1.2離散人工蜂群算法

9.1.3DABC算法流程

9.2基於ABC的零空閑等量分批批量流流水車間調度方法

9.2.1基於ABC的批次內零空閑等量分批批量流流水

車間調度方法

9.2.2基於ABC的機器零空閑等量分批批量流流水車間

調度方法

9.3基於ABC的零等待等量分批批量流流水車間調度方法

9.3.1零等待ELFSP問題描述與數學模型

9.3.2離散人工蜂群算法求解m/N/E/NI/DV/TF/

nowait

9.3.3試驗設計與分析

9.4基於ABC的序列相關準備時間的等量分批批量流流水

車間調度方法

9.4.1序列相關準備時間的ELFSP描述與數學模型

9.4.2離散人工蜂群算法求解m/N/E/II/DV/TF/SDST

9.5本章小結

參考文獻

第10章入侵性雜草算法及其在批量流流水車間調度中的應用

10.1入侵性雜草算法的基本原理

10.1.1入侵性雜草算法的基本理論

10.1.2離散入侵性雜草優化算法設計

10.2基於IWO的零空閑等量分批批量流流水車間調度方法

10.2.1基於IWO的批次內零空閑等量分批批量流流水

車間調度方法

10.2.2基於IWO的機器零空閑等量分批批量流流水車間

調度方法

10.3基於IWO的零等待等量分批批量流流水車間調度方法

10.3.1DIWO的設計

10.3.2試驗設計與分析

10.4基於IWO的序列相關準備時間的等量分批批量流流水

車間調度方法

10.4.1DIWO的設計

10.4.2試驗設計與分析

10.5基於IWO的批量流流水車間集成調度方法

10.5.1問題描述

10.5.2數學模型

10.5.3改進DIWO求解批量流流水車間集成

調度問題

10.6本章小結

參考文獻

第11章粒子群優化算法及其在柔性作業車間調度中的應用

11.1廣義粒子群優化算法與元胞粒子群優化算法

11.1.1廣義粒子群優化算法

11.1.2元胞粒子群優化算法

11.2基於CPSO的柔性作業車間調度方法

11.2.1粒子的編碼

11.2.2粒子速度和位置的更新操作

11.2.3粒子的鄰域結構與局部搜索

11.2.4CPSO算法求解FJSP的流程

11.2.5實驗結果分析

11.3本章小結

參考文獻

第12章基因表達式編程及其在車間動態調度中的應用

12.1基因表達式編程的基本原理

12.1.1基因表達式編程

12.1.2GEP與GA，GP的關係

12.1.3GEP的基本流程

12.1.4GEP環境

12.1.5染色體的結構

12.1.6遺傳操作

12.2基於GEP的車間動態調度框架

12.2.1編碼方式

12.2.2適應度函數

12.3基於GEP的柔性作業車間動態調度方法研究

12.3.1柔性作業車間動態調度問題描述

12.3.2編碼與解碼方式

12.3.3遺傳操作

12.3.4實驗結果與分析

12.3本章小結

參考文獻

第三部分集成式工藝規劃與車間調度的智能算法

第13章遺傳變鄰域搜索算法及其在IPPS中的應用

13.1變鄰域搜索算法的基本原理

13.2基於GAVNS的IPPS方法

13.2.1混合GAVNS算法流程設計

13.2.2混合GAVNS算法求解IPPS問題

13.2.3實驗結果與分析

13.3本章小結

參考文獻

索引

附錄A英漢排序與調度詞匯

第1章緒論

數字化制造是制造技術、計算機技術、網絡技術與管理科學的交叉、融合、發展和應用的結果。數字化快速工藝準備是數字化制造的關鍵技術之一。工藝規劃是數字化快速工藝準備的核心內容之一，為迅速組織產品的生產和提高制造業的快速響應能力提供了相應的理論與技術基礎。同時，在制造成本中，裝配成本占很大的比重。據不完全統計，裝配成本占產品制造總成本的40%，裝配所用時間占產品制造總時間的20%~70%。

隨著全球市場競爭的日益激烈，客戶需求也越來越多樣化，“多品種小批量”的生產方式已成為大量制造企業的主要生產模式。在該模式下，必須同步提升制造車間的生產管理水平。車間調度是生產管理的一個重要環節，高效的車間調度優化技術對提高生產效率、縮短生產周期、提高市場響應速度、降低生產成本具有重要的意義。

可見，對工藝規劃、裝配序列規劃以及車間調度的優化技術進行研究是十分必要的。

1.1工藝規劃與車間調度問題

1.1.1工藝規劃

工藝規劃是優化配置工藝資源、合理編排工藝流程的一門技術。它是生產準備工作的第一步，也是連接產品設計與產品制造的橋梁(許煥敏 等，2008)。以文件形式確定下來的工藝規程是工裝制造和零件加工的主要依據。工藝規劃是數字化快速工藝準備的關鍵性工作，對組織生產、保證產質量量、提高生產率、降低成本、縮短生產周期及改善勞動條件等都有直接的影響。工藝規劃決定了產品的加工方法，是生產準備中最重要的任務之一，也是一切生產活動的基礎。工業界和學術界都對工藝規劃做了許多研究工作。

工藝規劃的定義有很多種，總結如下(許煥敏 等，2008)：

(1) 工藝規劃是產品設計與制造的橋梁，將產品設計數據轉化為制造信息(Mahmood,1998)。換言之，工藝規劃是連接設計功能與制造功能的一個重要活動，其指定產品零部件的加工策略與步驟。

(2) 工藝規劃是一個包含許多任務的復雜過程，這個過程要求工藝設計人員具有較深厚的產品設計與制造的知識(Ramesh，2002)。這些任務包括零件編碼、特征識別、加工方法與特征之間的映射、內外排序、裝夾規劃、中間件建模、加工設備工具及相應參數選擇、過程優化、成本評估、公差分析、檢測計劃、路徑規劃、數控程序等。

(3) 工藝規劃是制定將原材料轉化成最終零件的詳細操作的活動，或為零件加工與裝配的過程準備詳細文檔的活動(Chang et al.,1985)。

(4) 工藝規劃系統地確定了詳細的制造過程，在可用資源及其能力範圍內滿足設計規格的要求(Deb et al.,2006)。

上述定義從不同的工程技術角度，對工藝規劃進行了描述。這些定義可以總結為： 工藝規劃是連接產品設計與制造的橋梁，是在車間或工廠制造資源的限制下，將制造工藝知識與具體設計相結合準備其具體操作說明的活動。傳統上，工藝規劃由人工基於經驗來完成，導致了如下問題： ①經驗豐富人員的短缺； ②指定工藝路線的低效率； ③工藝人員經驗與判斷的差異而造成的工藝路線的不一致性； ④對實際制造環境的動態變化反應不及時等。

工藝路線的優化是工藝規劃的核心問題。經過證明，該問題是NP難問題，僅僅利用傳統的梯度下降法、圖論法和仿真方法等很難實現工藝路線的優化。為了更好地解決該問題，國內外大量學者采用智能算法來研究和求解該問題，主要包括遺傳算法、禁忌搜索、模擬退火等方法。

1.1.2裝配序列規劃

裝配是產品全生命周期的重要組成部分，是實現產品功能的最後一個操作。通常，產品功能無法通過單獨的零件來實現，而是需要通過將一些零件按照一定的關係組合在一起，成為一個統一的整體來實現產品的功能，且產品的性能很大程度上取決於產品的裝配質量。產品裝配序列是影響產品裝配成本和裝配質量的關鍵因素之一。一旦產品的裝配序列確定下來，產品的裝配線布置完畢後，如果產品的裝配序列需要改變，那麼產品的裝配線也需要進行相應的調整，這會導致成本的大大增加； 並且，當產品比較復雜時，產品可行裝配序列的數量與產品零部件的數量呈指數增長關係，所以復雜產品的裝配序列規劃存在組合爆炸問題(Wang et al.,2009)。

傳統上，工程師需要花大量的時間來確定產品的最終裝配序列，但所得的最終裝配序列不一定是可行的或最優的。因此，裝配序列規劃在產品制造過程中占有很重要的地位。裝配序列規劃是基於裝配體中各個零部件之間的幾何和工程約束信息，求得一個滿足這些約束要求的最優裝配序列。裝配序列規劃是一個典型的組合優化問題，其實質是在多種幾何約束條件和工藝約束條件的制約下求得性能優良的裝配序列的過程。

一般優化方法難以求解復雜產品的最優裝配序列。20世紀末以來，計算機技術的快速發展為軟計算方法奠定了堅實的硬件基礎，廣大研究者開始將智能算法應用到裝配序列規劃領域，如遺傳算法(Lazzerini et al.,2000)、文化基因算法(Gao et al.，2010)、蟻群算法(Su et al.,2013)等，並取得了很多的研究成果。

1.1.3車間調度

車間調度問題通常定義如下： 在一定的約束條件下，把有限的資源在時間上按照一定的順序分配給若幹個任務，以滿足或優化一個或多個性能指標(高亮 等,2012)。由此可見，車間調度的目的不僅是要對任務排序，還要獲得各個任務的開始和結束時間。通常假設每個任務都按照其最早開工時間開始加工，那麼任務的一個排序就可以確定一個調度方案。

經典的車間調度問題可表示為： n個工件在m臺機器上加工，一個工件可以有多道加工工序，每道工序可在一臺或若幹臺機器上加工，但須按照可行的工藝路線進行加工。車間調度問題的基本要素主要有3種：

(1) 工件和機器信息。調度所涉及的工件和機器的基本信息，如工件的數量、工件的釋放時間、工件中各種工序的加工時間、機器的數量、機器和工件的交貨期等。

(2) 約束條件。在各類調度中應滿足的限制，如加工不可中斷約束、機器適配約束、工件加工路徑約束等工藝約束以及原料和機器約束等資源約束。

(3) 調度性能指標。調度問題中的優化目標，如最小化最大完工時間、最小化總延誤、最小化能源消耗和最大化瓶頸機器利用率等。

車間調度問題的分類方法有很多。根據工件和機器構成不同，車間調度問題可分為：

(1) 單機調度問題。該問題中加工系統只有一臺機床，待加工的工件有且僅有一道工序，所有工件都在該臺機床上進行加工。該問題是最簡單的車間調度問題，當生產車間出現瓶頸機床時的調度可以視為該調度問題。

(2) 並行機調度問題。該問題中加工系統中有多臺同類型的機床，每個工件只有一道工序，工件可在任意一臺機床上進行加工。

(3) 開放車間調度問題。該問題中每個工件的工序之間沒有先後次序約束(如產品檢測車間等)，工件的加工可以從任何一道工序開始，在任何一道工序結束。

(4) 流水車間調度問題。該問題中加工系統有一組功能不同的機床，待加工的工件包含多道工序，每道工序在一臺機床上加工，所有工件的工藝路線是相同的。

(5) 作業車間調度問題。該問題中加工系統有一組功能不同的機床，待加工的工件包含多道工序，每道工序在一臺機床上加工，工件的加工路線互不相同，每個工件工序之間有先後順序約束。

此外，基於機器加工環境的車間調度問題還有： 流水車間與並行機混合的柔性流水車間（也稱作混合流水車間）、作業車間與並行機混合的柔性作業車間等。鑒於流水車間和作業車間的特殊性和典型性，通常將它們稱為基本車間調度問題。

車間調度是一類非常復雜的組合優化問題，要考慮任務、環境、目標等多方面的要求，通常車間調度問題具有以下幾個特點(王凌,2003)：

(1) 復雜性。車間調度問題要綜合考慮加工工藝、加工機器、加工任務以及生產環境等多方面的因素，本身就是一個復雜的優化問題，隨著車間調度問題規模的增加，求解車間調度問題所消耗的時間呈指數級增長，車間調度問題已被證明是NP完全問題。

(2) 不確定性/動態性。在實際車間調度中有很多隨機因素，如工件到達時間的不確定性，工件的加工時間隨著不同的加工機器也有一定的不確定性。而且，系統中常有突發事件，如緊急訂單插入、訂單取消、原材料緊缺、交貨期變更、設備發生故障等。

(3) 離散型。車間生產系統是典型的離散系統，其調度問題是離散優化問題。工件的開始加工時間、任務的到達、訂單的變更以及設備的增添或故障都是離散事件。可以利用數學規劃、離散系統建模與仿真、排序理論等方法對車間調度問題進行研究。

(4) 多約束性。在通常情況下，工件的工藝路線是已知的，並且受到嚴格的工藝約束，使得各道工序在加工順序上具有先後約束關係。同時，工件的加工機器集是已知的，工件必須按照工序順序在可以選擇的機床上進行加工。

(5) 多目標性。車間調度問題往往要考慮加工方和客戶方的多個優化目標，如最小化最大完工時間、最小提前/拖期懲罰、最小加工費用、最大化客戶滿意度、最大化資源利用率等，這些目標之間可能存在衝突，導致難以同時優化多個目標，需要綜合考慮和權衡。

1.2優化算法

針對工藝規劃、裝配序列規劃、車間調度等問題，學者提出了很多種不同的優化方法。這些方法主要可以分為兩類： 精確方法(exact methods)和近似方法(approximation methods)（李新宇，2009）。精確方法包括數學規劃方法和部分枚舉等，能保證得到全局最優解，但是通常只能求解較小規模的問題。近似方法能很快地獲得問題的解，但不能保證得到的解是最優的。然而，近似方法對大規模問題是非常合適的，可以較好地滿足實際問題的需求。

1.2.1精確方法

精確方法主要包括數學規劃方法和分支定界法。這類方法雖然從理論上能求得最優解，但是由於計算復雜、運算量大和能解決問題規模有限等原因，在實際應用中受到了限制(高亮等,2012)。

1. 數學規劃方法

數學規劃(mathematical programming)方法是較早用於求解車間調度問題的方法。20世紀60年代，研究人員傾向於設計具有多項式時間復雜度的確定性方法，以獲取車間調度問題的最優解。整數規劃(integer programming)方法是常用的求解調度問題的數學方法，該方法的缺點是在運算中計算時間會隨著問題規模增大呈指數增長。所以，有研究人員認為使用整數規劃方法求解調度問題在計算上是不可行的。

用於求解調度問題比較成功的數學方法還包括： 拉格朗日松弛法(Lagrangian relaxation)和分解方法(decomposition methods)。拉格朗日松弛法用非負拉格朗日乘子將工藝約束和資源約束進行松弛，最後將懲罰函數加入目標函數中，在有限時間裡求出復雜問題的次優解。分解方法通過將原問題分解為多個易於求解的子問題，將子問題求出最優，該方法也已用於求解調度問題。

2. 部分枚舉法

分支定界法(branch & bound)是一種主要的部分枚舉法。它用動態結構分支來描述所有的可行解空間，這些分支隱含有要被搜索的可行解。這個方法可以用公式和規則來描述，在對最優解搜索過程中，它允許把大部分的分支從搜索過程中去掉。這種方法從誕生之日起，就十分流行，適合求解總工序數N小於250的調度問題。對於求解大規模問題，該方法需要巨大的計算時間，這限制了它的使用範圍。目前，該方法被大量的用於求解車間調度問題。1989年，Carlier提出的分支定界法第一次證明了著名的車間調度基準實例中FT10問題的最優解是930。

1.2.2近似方法

從對工藝規劃與車間調度問題復雜性的研究發現，僅有極少數特殊實例可以在多項式時間內得到解決。由於精確方法難以求解該問題，因此近似方法成為一種可行的選擇。近似方法能在合理的時間內產生比較滿意的次優解，廣泛應用於較大規模的問題(李新宇,2009)。

1. 構造性方法

最早開發的近似方法是構造性方法(constructive methods)，主要包括優先分配規則、基於瓶頸的啟發式方法以及插入方法等。

優先分配規則(priority dispatch rules，PDR)是最早提出的近似方法。該方法是分配一個優先權給所有待加工的工序，然後選擇優先權最高的加工工序先加工，接下來按優先權次序依次進行排序。該方法具有容易實現和較小時間復雜性的特點，是在實際應用中解決調度問題的常用方法。目前許多優先規則被提出，常用的規則包括： LRPT(longest remaining processing time)、SRPT(shortest remaining processing time)、LOR(least operations remaining)、SIRO(service in random order)、FCFS(first coming first serving)、SPT(smallest processing time)、LPT(longest processing time)、SQNO(shortest queue at the next operation)、LQNO(longest queue at the next operation)(高亮 等,2012)。優先分配規則雖然速度非常快，但卻短視。它只考慮機器的當前狀態和解的質量等級等因素，而不能全面考慮該問題的屬性和特點。

基於瓶頸的啟發式方法(bottleneck based heuristics)包括瓶頸移動(shifting bottleneck procedure，SBP)方法等。SBP方法是按照解的大小順序對所有機器進行排序，有著最大下界的機器被確定為瓶頸機器。SBP方法對瓶頸機器排序，留下被忽視的未被排序的機器，固定已排序的機器。當每次瓶頸機器排序後，每個先前被排定的有接受改進能力的機器，通過解決單一機器問題的方法再次被局部重新最優化，而單一機器問題的排序是用Carlier（1982）提出的方法迭代解決。SBP方法雖然能比PDR提供質量更好的解，但是計算時間較長，算法實施比較復雜。

2. 人工智能方法

人工智能(artificial intelligence，AI)是求解工藝規劃與車間調度問題的重要方法。該類方法是利用人工智能的原理和技術進行搜索，譬如將優化過程轉化為智能系統動態的演化過程，基於系統動態的演化來實現優化。該方法主要包括： 約束滿足技術、神經網絡、專家系統、多代理系統、混沌搜索以及後來通過模擬某些自然現象、過程和規律而發展的元啟發式算法(如： 進化算法、免疫算法、蟻群算法和粒子群優化算法等)。下面對流行的智能算法進行簡要介紹(張超勇,2006)。

約束滿足技術(constraint satisfaction，CS)通過運用約束減少搜索空間的有效規模。這些約束限制了選擇變量的次序和分配到每個變量可能值的排序。當一個值被分配給一個變量後，不一致的情況將被剔除，去掉不一致的過程稱為一致性檢查，但是也需要進行回訪修正，當所有的變量都得到了分配的值並且並不違背約束條件時，約束滿足問題就得到了解決。

神經網絡(neural networks，NN)指由大量簡單神經元互聯而構成的一種計算結構，它在某種程度上可以模擬生物神經系統的工作過程。該方法較早地被用來求解調度問題，目前應用最多的是BP網絡和Hopfield網絡。由於神經網絡通過訓練和學習來尋找輸入和輸出的關係，隨著問題的規模增大，網絡的規模也急劇地增大。因此，目前的NN方法僅能解決規模較小的問題。

專家系統(expert system，ES)是一種模擬人類專家解決領域問題的計算機程序系統，主要由知識庫和推理機兩部分組成。它將傳統的調度方法與基於知識的調度評價相結合，根據系統當前的狀態和給定的優化目標，對知識庫進行有效的啟發式搜索和並行模糊推理，避免繁瑣的計算，並選擇最優的調度策略，為在線決策提供支持。該方法的不足之處在於開發周期長，成本昂貴，需要豐富的調度經驗和知識，而且對新環境的適應性差等。

多代理系統(multiagent system,MAS)代理是一種具有自治能力的、能夠與其他代理進行協調交互，並對環境變化做出響應和基於目的采取行動的問題求解實體。MAS則是由多個代理協調組成的自組織系統。MAS立足於每個代理的局部信息和目標，遵循代理間的依賴關係和約束，在有限的資源和信息的基礎上通過代理間的信息交互完成系統目標。代理的自主性和協調性使得MAS在解決復雜系統時具有分布性、適應性和開放性的特點。MAS和專家系統一樣，都需要豐富的調度經驗和知識，這是MAS的瓶頸問題。