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