遺傳算法GA（geneticalgorithm）是Holland［60］基於自然遺傳進化的絕對模型提出的並行搜索機製，GA的5個要素是編碼、適應值函數、初始種群、遺傳算子和參數設置。Nakano等［61］首先將遺傳算法應用到Jobshop調度問題上。遺傳算法的最大優點是通過群體間的相互作用，保持已經搜索到的信息，這是基於單次搜索過程的優化方法所無法比擬的。但是，遺傳算法也存在著計算速度較慢等問題。
（十一）拉氏鬆弛法
拉氏鬆弛法（Lagrangianrelaxationapproach）由於其在可行的時間裏能對複雜的規劃問題提供好的次優解，並能對解的次優性進行定量評估，近年來已成為解決複雜車間調度問題的一種重要方法。Luh等［62］用拉氏鬆弛法解決了單機調度和多台並行機調度的問題；Hoitomt等［63］通過引入更多的拉氏乘子鬆弛了操作之間的順序約束，並將這種方法用於一般的JSP調度問題；Chen等［64］提出的用動態規劃算法解決作業級子問題的方法，較好地解決了將子問題分解到操作級可能出現解振蕩的問題。
（十二）蟻群算法
蟻群算法ACO（antcolonyoptimization）是20世紀90年代初由意大利學者Dorigo等［65，66］提出的一種新型的模擬進化算法，其主要思想是利用蟻群在搜索食物源的過程中所體現出來的尋優能力，來解決一些離散係統優化中的困難問題。生物世界中的螞蟻有能力在沒有任何可見提示下，找出從窩巢至食物源的最短路徑，並能隨環境的變化而變化，適應性地搜索新的路徑。蟻群算法已經在若幹領域獲得了成功的應用。Li等［67］提出了一種嵌套混雜蟻群算法，用於解決具有混雜變量類型的複雜生產調度問題，在一種新的最佳路徑信息素（pheromone）更新算法的基礎上，提高了搜索效率。目前，國內對蟻群算法及其在組合優化問題中的應用才剛剛開始。
（十三）粒子群算法
粒子群算法PSO（particleswarmoptimization）是受鳥群捕食啟發產生的元啟發式算法。PSO算法通過種群內粒子之間的合作與競爭產生的群體智能指導優化搜索。與遺傳算法比較，PSO算法保留了基於種群的全局搜索策略，其優化機理清晰易懂，搜索模型步驟簡單，計算費用較低。華中科技大學的高亮教授等［68，69］研究了將粒子群算法用於車間調度問題；浙江大學的葉建芳等［70］引入免疫係統的抗體濃度選擇機製，構造了一種基於免疫機製的粒子群優化算法求解JSP問題。
（十四）組合算法
組合算法是指對上述兩種或兩種以上算法進行組合，利用各自的優點開發出優化能力更強的算法。同濟大學的嚴雋薇教授等［71］提出以整體退火選擇的方式選擇遺傳算法中的雜交母體，以克服種群早熟化，然後進行了車間日作業計劃的製訂；同濟大學的馬玉敏等［72］提出了采用仿真與優化算法相結合的求解方法進行車間調度；華中科技大學的朱海平等［73］給出了不確定信息條件下的車間調度隨機規劃模型，然後用混合智能算法進行了求解。北京航空航天大學的林楠等［74］將模擬退火算法結合到基本遺傳算法，並將該算法應用於航空複雜產品製造車間靜、動態調度問題；Mittenthal［75］等將模擬退火法與貪心法相結合，先用貪心法搜索，將得到的作業序列作為初始解，再用模擬退火法求解單機調度問題；Holsapple等［76］將遺傳算法與圖搜索法相結合，利用遺傳算法進行知識的推理、啟發，再用過濾束搜索法進行優化搜索，以得到高質量的FMS靜態調度；Solimanpur等［78］將ANN與TS結合用於流水作業計劃問題的求解。通過算例研究可以得出組合算法比其所采用的獨立算法具有更好的性能［75~77］。本書將采用組合算法的思路開發新的算法。