《分布估計調度算法》主要介紹分布估計算法（EDA）在柔性車間調度與資源約束調度等問題上的應用。全書由11章構成，內容自成體系，安排如下：第1章介紹EDA的原理及其相關研究的進展。第2~6章分別介紹不相關并行機調度、柔性作業車間調度、模糊柔性作業車間調度、隨機混合流水線調度、分布式流水線裝配調度等問題的EDA設計與性能分析。第7~9章介紹隨機資源約束項目調度、多目標資源約束項目調度、低碳項目調度等問題的EDA設計與性能分析。第10~11章分別介紹EDA在半導體最終測試調度、電子系統綜合設計建模與優化等問題上的應用。
本書主要面向自動化、管理、計算機、機械、工業工程等學科的高等院校、研究機構和企業的教師、學生、技術人員。
分布估計算法EDA是目前與優化相關的領域的熱點研究算法，而基于分布估計的調度研究是學術界和工程界的前沿課題，而至今國內外沒有一本關于分布估計調度方面的書籍。本著作歸納介紹了分布估計算法的原理和研究進展，重點闡述了EDA在柔性車間調度和資源約束調度兩大類離散調度問題上的研究。對于自動化、管理、計算機、機械、工業工程等學科的高等院校、研究機構和企業的教師、學生、技術人員，本著作是一本很好的參考書，具有很好的推廣和銷售市場，有助于推動EDA的深入研究和應用，并有助于完善智能優化與調度方面課程的相關教學與研究。
前言
隨著科學技術的不斷發展，當前所面臨的問題越來越復雜。從優化的角度而言，許多實際問題存在非線性、強約束、多極小、多目標、不確定等復雜性，規模龐大，建模困難，評價費時.鑒于諸多復雜性對優化理論與技術帶來的新挑戰，借鑒生物、物理、社會等系統的相關功能、特點與作用機理以及其他學科最新的研究成果，研究新的信息處理機制和計算模型，設計適合大規模問題的智能求解算法已成為諸多學科的重要研究課題.
智能優化就是基于計算智能的機制，提煉合適的特征模型，設計有效的優化算法，進而獲得復雜問題的最優解或滿意解.智能算法要盡量保證取得全局的優化質量、快速的優化效率和魯棒的優化性能.對于優化問題的非線性和多極小性，智能算法應具有克服搜索過程陷入局部極小的能力；對于問題的大規模性和NP難特性，應具有保證一定優化質量前提下的高效搜索能力；對于問題的多目標性，應具有綜合與協調多個目標的能力；對于問題的強約束性，應具有高效處理約束來保證獲得可行解的能力；對于問題的不確定性因素和算法本身的參數設置，應具有良好的魯棒性；對于問題的理解與特征建模，應具有合理性和實用性；對于解的性能評價過程，應具有快速性和準確性；對于問題連續與離散變量共存的特點，應具有搜索操作的靈活性和有效性.研究先進的智能優化理論，設計高效的智能優化方法，推廣有效的智能優化應用，不僅具有重要的學術價值和學科發展意義，而且對于提高企業的管理水平、增加企業的效益、促進企業的發展具有十分重要的現實意義.
作為一種群體智能優化算法，分布估計算法(estimationofdistributionalgorithm，EDA)基于統計學習的理論和方式，從群體宏觀的角度建立概率模型，用以描述候選解在搜索空間中的分布信息，然后通過對概率模型的隨機采樣產生新解，再利用優良解的信息更新概率模型，如此反復迭代進而獲得問題的優良解.EDA采用基于搜索空間宏觀層面的進化方式，通過對搜索空間的采樣和統計學習來預測搜索的最佳區域，因此具備較強的全局搜索能力和較快的收斂速度.EDA自1996年被提出后，迅速成為群體智能優化研究的熱點算法之一，尤其在算法設計層面得到了廣泛的研究與發展，并在諸多領域得到成功應用.同時，IEEETransonEvolutionaryComputation、IEEETransonCybernetics等權威國際期刊，計算智能領域的兩大旗艦會議WorldCongressonComputationalIntelligence(WCCI)、IEEESymposiumSeriesonComputationalIntelligence(SSCI)上涌現出大量有關EDA的研究論文.
文獻調研表明，分布估計算法的研究大部分針對連續優化問題，而針對離散組合優化問題的研究相對較少.近些年，EDA在典型生產調度問題上得到了應用與推廣，但國內外尚無一本專門介紹EDA調度的書籍.依托國家杰出青年科學基金、國家自然科學基金重點和面上項目、國家重點研發計劃、教育部博士點基金等項目，作者所在課題組圍繞一系列復雜調度問題深入開展了EDA的設計、性能分析與應用研究，近些年在運籌與管理、生產制造等領域的著名國際期刊和IEEE匯刊上發表了多篇高水平研究論文，得到了國際同行的高度評價與廣泛引用.本書融合了課題組的代表性研究成果以及多篇清華大學優秀博士學位論文、優秀碩士學位論文的內容，介紹EDA的原理、基本框架和研究進展，著重介紹EDA在柔性車間調度和資源約束調度兩類典型問題上的研究與應用，為復雜調度問題的求解提供新的思路和方法.全書由11章構成，內容自成體系.第1章介紹EDA的原理及其相關研究的進展，第2章介紹不相關并行機調度的混合EDA，第3章介紹柔性作業車間調度的多目標EDA，第4章介紹模糊柔性作業車間調度的EDA，第5章介紹隨機混合流水線調度的混合EDA，第6章介紹分布式流水線裝配調度的混合EDA，第7章介紹隨機資源約束項目調度基于序的EDA，第8章介紹多目標資源約束項目調度的混合EDA，第9章介紹低碳項目調度的混合EDA，第10章介紹EDA在半導體最終測試調度上的應用，第11章介紹EDA在電子系統綜合設計建模與優化上的應用.
希望本書的出版，有助于初學的讀者了解EDA調度算法的原理與設計，有助于有基礎的讀者開展EDA調度算法的應用與推廣，進而促進EDA研究的發展與完善，加強基于計算智能的調度算法研究，推動相關學科的交叉與融合.
最后，感謝清華大學吳澄院士、鄭大鐘教授、金以慧教授、劉民教授，北京理工大學陳杰教授，香港城市大學ZhangQF教授，新加坡南洋理工大學SuganthanPN教授，華中科技大學高亮教授、潘全科教授等對相關研究工作給予的熱心指導和建議，感謝清華大學出版社的大力支持，感謝參與研究的課題組全體博士生和碩士生.另外，特別感謝國家重點研發計劃(2016YFB0901900)、國家杰出青年科學基金(61525304)等項目對相關研究工作的資助.
由于作者水平有限，本書許多內容還有待完善和深入研究，對于不足之處，誠望讀者批評指教.
作者2017年9月
收起全部↑
目錄
第1章緒論
1.1分布估計算法概述
1.1.1標準EDA及其特點
1.1.2EDA的改進研究
1.1.3EDA的理論研究
1.1.4EDA的拓展與應用
1.1.5EDA研究展望
1.2柔性車間調度概述
1.2.1典型柔性生產調度問題
1.2.2問題特性和求解難點
1.3資源約束項目調度概述
1.3.1問題描述
1.3.2RCPSP的擴充
1.3.3理論研究進展
1.3.4算法研究進展
1.3.5RCPSP的應用
1.3.6RCPSP研究展望
參考文獻
第2章基于EDAIG的不相關并行機調度
2.1引言
2.2問題描述
2.2.1符號定義
2.2.2數學模型
2.3調度解的鄰域分析
2.3.1鄰域搜索操作
2.3.2操作的有效性分析
2.4結合迭代貪婪搜索的EDA
2.4.1編碼方式
2.4.2種群初始化
2.4.3概率模型及其更新與采樣
2.4.4迭代貪婪搜索
2.4.5算法流程
2.4.6復雜度分析
2.5仿真實驗
2.5.1算法參數設置
2.5.2混合策略的有效性
2.5.3迭代貪婪搜索的選擇準則
2.5.4算法性能比較
參考文獻
第3章基于BEDA的柔性作業車間調度
3.1引言
3.2問題描述
3.2.1符號定義
3.2.2數學模型
3.3雙種群分布估計算法
3.3.1多目標優化的基本概念
3.3.2編碼與解碼
3.3.3種群初始化
3.3.4概率模型及采樣方式
3.3.5概率模型的更新機制
3.3.6種群的分裂與合并
3.3.7基于關鍵路徑的局部搜索
3.3.8算法流程
3.3.9計算復雜度分析
3.4單目標優化仿真實驗
3.4.1算法參數設置
3.4.2種群分裂機制的有效性
3.4.3算法性能比較
3.5多優化目標仿真實驗
3.5.1算法參數設置
3.5.2算法性能比較
參考文獻
第4章基于EDA的模糊柔性作業車間調度
4.1引言
4.2模糊柔性作業車間調度問題
4.2.1符號定義
4.2.2問題描述
4.2.3模糊加工時間的運算
4.3fFJSP的分布估計算法
4.3.1編碼與解碼
4.3.2左移插空操作
4.3.3概率模型及其更新
4.3.4算法流程
4.4數值仿真與比較
4.4.1參數設置
4.4.2算法性能比較
參考文獻
第5章基于OEDA的隨機混合流水線調度
5.1引言
5.2問題描述
5.2.1符號定義
5.2.2數學模型
5.3基于序的分布估計算法
5.3.1評價指標
5.3.2編碼與解碼
5.3.3概率模型
5.3.4基于OCBA的概率模型更新
5.3.5算法流程
5.4仿真實驗
5.4.1算法參數設置
5.4.2OCBA機制的有效性
5.4.3算法性能比較
參考文獻
第6章基于EDALS的分布式流水線裝配調度
6.1引言
6.2分布式流水線裝配調度描述
6.2.1符號定義
6.2.2問題描述
6.3帶局部搜索的分布估計算法
6.3.1編碼與解碼規則
6.3.2概率模型采樣與更新
6.3.3選擇性增強采樣
6.3.4基于關鍵路徑的局部搜索
6.3.5EDALS流程及其復雜度分析
6.4數值仿真
6.4.1算法參數設置
6.4.2混合策略的有效性
6.4.3選擇性增強采樣的有效性
6.4.4算法性能對比
參考文獻
第7章基于OEDA的隨機資源約束項目調度
7.1引言
7.2隨機資源約束項目調度問題
7.2.1符號定義
7.2.2經典RCPSP描述
7.2.3隨機RCPSP描述
7.2.4調度策略
7.2.5SRCPSP算法概述
7.3隨機RCPSP的OEDA
7.3.1編碼規則與適配值函數
7.3.2概率模型
7.3.3概率模型采樣
7.3.4局部搜索策略
7.3.5更新機制
7.3.6概率矩陣初始化
7.3.7OEDA流程
7.4數值仿真
7.4.1實驗說明
7.4.2OEDA參數設置
7.4.3項目參數與分布類型的影響
7.4.4算法比較與分析
參考文獻
第8章基于PAEDA的多目標資源約束項目調度
8.1引言
8.2MORCPSPMSRI描述
8.3MORCPSPMSRI的PAEDA
8.3.1編碼與解碼
8.3.2種群初始化
8.3.3混合概率模型
8.3.4概率模型的采樣
8.3.5Pareto檔案集與更新檔案集
8.3.6概率模型的更新
8.3.7局部搜索策略
8.3.8PAEDA流程
8.4數值仿真
8.4.1實驗說明
8.4.2性能指標
8.4.3概率模型進化過程
8.4.4算法比較與分析
參考文獻
第9章基于PBEDA的低碳項目調度
9.1引言
9.2低碳生產的項目調度模型
9.2.1低碳調度
9.2.2多目標多模式RCPSP模型
9.3低碳項目調度的PBEDA
9.3.1編碼與解碼
9.3.2種群初始化
9.3.3混合概率模型
9.3.4概率模型的采樣
9.3.5Pareto檔案集的更新
9.3.6概率模型的更新
9.3.7PBEDA流程及其復雜度分析
9.4數值仿真與算法比較
9.4.1測試數據說明
9.4.2參數設置
9.4.3不同總調度數下的Pareto集
9.4.4算法比較與分析
參考文獻
第10章半導體最終測試調度優化
10.1引言
10.2半導體最終測試調度問題
10.2.1符號定義
10.2.2問題描述
10.3混合分布估計算法
10.3.1編碼與解碼
10.3.2概率模型及其更新
10.3.3局部搜索
10.3.4算法流程及其復雜度分析
10.4性能測試與算法比較
10.4.1算法參數設置
10.4.2算法性能對比
參考文獻
第11章電子系統綜合設計建模與優化
11.1引言
11.2系統級綜合問題
11.3項目調度模型
11.3.1活動與時間約束
11.3.2模式、工期與資源約束
11.3.3數學模型
11.3.4調度生成機制
11.4PAEDA_MI
11.4.1編碼方式
11.4.2概率模型
11.4.3概率模型的采樣
11.4.4更新機制
11.4.5PAEDA_MI流程
11.5案例研究
11.5.1問題描述
11.5.2AoN網絡簡化
11.5.3仿真結果
參考文獻
第3章基于BEDA的柔性作業車間調度
3.1引言
柔性作業車間調度問題（flexiblejobshopschedulingproblem，FJSP）是柔性制造系統中典型的調度問題，可視為傳統作業車間調度問題（jobshopschedulingproblem，JSP）的一種擴展.對于傳統的作業車間，每臺機器只能完成某一道特定工序，每道工序也只能由某一臺特定機器完成.對于柔性作業車間，機器為多功能機，可以完成多種工序，每道工序也可由多臺機器中的任一臺完成.求解FJSP，既要確定每臺機器上的工序順序，還要確定每道工序的機器分配.因此，FJSP是典型的組合優化問題，其求解比JSP更為復雜［1］.
近年來，FJSP已成為生產調度領域的研究熱點，尤其是以最小化最大完工時間為指標的單目標優化問題.假設每道工序在不同機器上的加工時間相同，Bruker等［2］提出了求解兩工件問題的一種多項式算法.Brandimarte［3］提出了一種基于問題分解的雙層禁忌搜索算法（tabusearch，TS），首先求解工序的機器分配問題，然后將問題轉化為傳統的JSP進一步求解.DauzerePeres等［4］給出了一種擴展的析取圖模型，定義了問題的鄰域結構，進而提出了基于綜合法的一種TS算法.隨后，Mastrolilli等［5］提出了兩種改進的鄰域結構，縮短了TS算法的運行時間，并提高了算法的求解性能.Pezzella等［6］提出了一種遺傳算法（geneticalgorithm，GA），研究表明采用多種不同的策略進行種群初始化、選擇和個體生成可以改進算法的性能.Gao等［7］將GA與變鄰域搜索（variableneighborhoodsearch，VNS）結合求解FJSP.Yazdani等［8］設計了六種鄰域結構，提出了一種并行變鄰域搜索算法（parallelVNS，PVNS）算法.Xing等［9］采用知識模型記錄搜索過程中獲取的信息，提出了一種基于知識的蟻群優化算法（knowledgebasedantcolonyoptimization，KBACO）.Li等［10］設計了一種快速局部搜索方法，進而提出了一種基于公共關鍵塊的禁忌搜索算法（TSwithpubliccriticalblock，TSPCB）.
對于多目標FJSP（multiobjectiveFJSP，MFJSP），現有的求解算法大致可分為兩類：目標加權法和Pareto支配方法.
目標加權法通過為各個目標設置相應的權重，將多目標優化問題轉化為單目標優化問題進行求解，但每次運行通常只能獲得一個解.例如，微粒群優化（particleswarmoptimization，PSO）與模擬退火（simulatedannealing，SA）的混合算法［11］、基于遺傳編程（geneticprogramming，GP）的集成指派規則（dispatchingrule，DR）方法［12］、過濾束搜索算法（filteredbeamsearchbasedheuristic，FBSH）［13］、禁忌搜索算法［14］等.
Pareto支配方法采用基于Pareto支配意義上的最優性進行解的性能比較，進而基于群體優化算法迭代搜索性能更好的解，每次運行通常可以得到一組Pareto最優解，供決策者選擇.例如，模糊邏輯進化算法［15］、多目標遺傳算法（multiobjectiveGA，MOGA）［16］、多目標微粒群優化算法（multiobjectivePSO，MOPSO）［17］、基于Pareto的離散人工蜂群算法（Paretobaseddiscreteartificialbeecolony，PDABC）［18］等.
針對柔性作業車間調度問題，本章首先考慮最小化完工時間的單目標優化，然后同時考慮最大完工時間、總負荷和機器最大負荷三個指標的最小化，結合問題的特性提出相應的雙種群的混合分布估計算法.
新書資訊