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章緒論

數字化制造是制造技術、計算機技術、網絡技術與管理科學的交叉、融合、發展和應用的結果。數字化快速工藝準備是數字化制造的關鍵技術之一。工藝規劃是數字化快速工藝準備的核心內容之一，為迅速組織產品的生產和提高制造業的快速響應能力提供了相應的理論與技術基礎。同時，在制造成本中，裝配成本占很大的比重。據不完全統計，裝配成本占產品制造總成本的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) 多目標性。車間調度問題往往要考慮加工方和客戶方的多個優化目標，如小化完工時間、小提前/拖期懲罰、小加工費用、化客戶滿意度、化資源利用率等，這些目標之間可能存在衝突，導致難以同時優化多個目標，需要綜合考慮和權衡。