張 潔 秦 威

1.東華大學機械工程學院，上海，201620 2.上海交通大學機械與動力工程學院，上海，200240

1 智能調度是制造系統(tǒng)運行優(yōu)化的核心

近年來，隨著大規(guī)模定制和協(xié)同生產模式的發(fā)展，制造企業(yè)需要獲取客戶的個性化定制數據和分布式環(huán)境下的車間制造數據，實現(xiàn)生產資源的合理配置［1－2］。一些明顯的環(huán)境和產業(yè)變化，使得制造業(yè)的服務化成為一種世界范圍內的新趨勢。這些變化主要表現(xiàn)在以下3個層面：

（1）消費行為的轉變。終端顧客由傳統(tǒng)的對產品功能的追求，轉變?yōu)榛诋a品的更加個性化的消費體驗和心理滿足的追求。這使得制造業(yè)的服務化在制造環(huán)節(jié)更加貼近客戶的需求和心理滿足，最終表現(xiàn)為對客戶服務價值實現(xiàn)的追求。

（2）企業(yè)間合作和服務的趨勢。由傳統(tǒng)的單個核心企業(yè)轉變?yōu)槠髽I(yè)間密切的合作聯(lián)系，企業(yè)間通過密切的交互行為充分配置資源，形成密集、動態(tài)的企業(yè)服務網絡。

（3）企業(yè)模式的轉變。世界典型的大型制造企業(yè)紛紛由傳統(tǒng)的產品生產商轉變?yōu)榛诋a品組合＋全生命周期服務的方案解決商。

制造系統(tǒng)智能調度指利用人工智能技術，依靠具備自主感知、學習、分析、決策和協(xié)調控制的智能化設備，結合互聯(lián)網來進行制造企業(yè)生產的動態(tài)協(xié)同自適應的管理活動。面對企業(yè)與企業(yè)、車間與車間之間互聯(lián)程度越來越高的復雜環(huán)境，現(xiàn)代化制造系統(tǒng)正逐漸向大數據和智能化系統(tǒng)演變［3］。因此，優(yōu)化智能調度是企業(yè)快速響應市場變化、組織高效生產和滿足用戶多樣化需求的根本途徑［4］，是制造系統(tǒng)運行優(yōu)化的核心。只有這樣，才能逐漸降低制造企業(yè)的生產成本，提升排產效果，提高經濟價值。

2 新時代制造業(yè)與云服務的結合更緊密

制造業(yè)服務化所展示的資源整合、價值創(chuàng)造、知識創(chuàng)新等優(yōu)勢越來越明顯［5－6］，因此，相對落后的制造系統(tǒng)調度方法也逐漸成為制造企業(yè)服務化過程中的瓶頸。所以新時代的制造業(yè)應具有的特點具體如下：數據的集成化與更高的共享度，優(yōu)越的調度優(yōu)化全局性能［7］；針對生產過程中的動態(tài)時間（如設備故障、訂單變更等）更快的響應速度［8］；調度系統(tǒng)更強勁和更廣泛的可擴展性，以應對隨時變化的生產環(huán)境［9］。

基于大數據、云計算和物聯(lián)網技術，制造系統(tǒng)結合智能調度云服務，能夠縮短制造車間調度系統(tǒng)開發(fā)周期，提高業(yè)務響應速度，實現(xiàn)用戶服務獲取與數據共享［10］，與現(xiàn)代制造調度系統(tǒng)的需求相符合。構建基于云服務的制造系統(tǒng)智能調度平臺，可實現(xiàn)“按需即用，隨需應變”，能夠適應現(xiàn)代制造系統(tǒng)服務化需求，實現(xiàn)多系統(tǒng)的跨區(qū)信息交互、業(yè)務整合以及海量數據存儲和處理［11］，集成和共享面向服務的體系架構，便于實現(xiàn)動態(tài)擴展，能產生巨大的經濟效益［12］。

3 制造系統(tǒng)調度問題研究的結構體系

制造系統(tǒng)調度問題基于數學模型來描述，了解調度問題的實質需要從數學模型入手進行分析比較。在理解模型的基礎上，使用不同的智能調度算法求解調度問題，使得近似化算法求解最大程度上趨于最優(yōu)。結合云計算技術，應用到智能調度云服務體系，以適應智能調度逐漸向云制造轉變。多條并行產線或多道工序具有加工能力不同、生產時間不等、生產成本不一致的特征，歸結為非等效并行調度問題；為提高調度的柔性，每道工序添加多條加工工藝路線，為選擇一條合理的工藝路線且能生成全部任務的調度結果，產生了多工藝路線作業(yè)車間調度問題；結合流水車間調度問題和并行機調度問題，集成產品的批次劃分，構成了混合流水車間調度問題；而面對復雜產品的裝配過程中多型架、多種零部件、多構型的特點，并且裝配過程中可能發(fā)生工時偏差、零件報廢、型架被占用等異常事件，結合平尾翼裝配過程實例，介紹了混流裝配線智能調度問題。由于不同產品的制造過程特征不同，產品的生產計劃安排往往需要面向多制造過程進行，為保證產品總體進度最優(yōu)，面向多車間、多制造過程的調度模型和算法，開發(fā)出智能調度算法庫和插件平臺，實現(xiàn)不同調度算法的集成。為了促進小微制造企業(yè)信息化完善，以靈活的方式根據自身需要選擇合適的服務，書中給出了制造系統(tǒng)智能調度云服務平臺原型系統(tǒng)設計實例與實現(xiàn)過程。制造系統(tǒng)調度問題研究的結構體系如圖1所示。

圖1 制造系統(tǒng)調度問題研究框架Fig.1 Research framework of manufacturing system scheduling problem

4 求解大規(guī)模調度問題，智能調度算法提供新思路

由于制造系統(tǒng)中的絕大部分調度問題均屬于NP-hard組合優(yōu)化問題，在不同的發(fā)展階段，研究的側重點和手段方法有較大差別。早期解決調度問題的主要方法為精確方法，包括分支定界法、混合整數規(guī)劃法、拉格朗日松弛法、分解方法等，它們雖然能夠保證得到全局最優(yōu)解，但對大規(guī)模的問題卻表現(xiàn)出計算量繁復的劣勢。雖然近似算法中的啟發(fā)式規(guī)則能快速得到問題的解，但解的質量通常較差，難以得到全局優(yōu)化結果，不能很好地對獲得的結果進行次優(yōu)性的定量評估。

20世紀80年代以來，人們通過模擬或揭示某些自然現(xiàn)象、過程和規(guī)律而產生的人工智能算法，為解決復雜的組合優(yōu)化問題提供了新的思路和手段。這些算法有的是從生物學的機理中受到啟發(fā)而建立的智能算法，如遺傳算法、粒子群算法和蟻群算法等；有的是從物理學、人工智能的思想中受到啟發(fā)，由傳統(tǒng)的局部搜索算法擴展而提出的，如禁忌搜索算法、模擬退火算法等；以及受帝國競爭機制啟發(fā)而建立的帝國競爭算法。這些智能算法的目的都是解決NP-hard組合優(yōu)化問題的全局最優(yōu)解，并追求求解的快速性。

5 調度系統(tǒng)云服務體系——基于云計算的智能調度

目前關于云計算，為大眾所廣泛接受的是美國國家標準與技術研究院（NIST）的定義：一種按使用量付費的模式，提供可用的、便捷的、按需的網絡訪問，進入可配置的計算資源共享池，只需投入很少的管理工作。云計算是一種動態(tài)的、易擴展的、基于互聯(lián)網的、利用虛擬化技術為不同用戶提供服務的計算模式。

云計算基本結構由SOA構建層、管理中間層、資源池層和物理資源層構成，所具有的能力分別為獲得服務接口、服務注冊、服務查找、服務訪問和服務工作流；對虛擬資源情況進行實時監(jiān)測以達到均衡管理云計算資源，以及根據用戶提交的任務找到相應資源并進行部署和管理；應用虛擬化技術，將數據中心包含的基礎設施和硬件資源虛擬為各種虛擬資源，并供給管理中間層對資源分配利用；不同地域數據中心的物理資源基礎設施構成云計算硬件的硬件平臺支持。

現(xiàn)代網絡化先進技術與云計算、物聯(lián)網等技術相結合所構建出的云制造服務模式，不僅可以實現(xiàn)資源的跨地區(qū)、跨空間大規(guī)模配置，滿足大規(guī)模復雜制造任務的需求，而且其專業(yè)化的服務平臺可以實現(xiàn)大批量的資源匹配和信息檢索，實現(xiàn)制造資源的智能化配置。云制造服務把用戶的需求放在價值鏈的頂端，實現(xiàn)了真正的面向服務、面向需求的架構。這種大轉變是實現(xiàn)生產型企業(yè)向服務型企業(yè)轉變、實現(xiàn)資源優(yōu)化配置以提高資源利用率的關鍵。

調度業(yè)務具有實時性強、可靠性高、分布廣、一體化程度高等特點。借助云計算的發(fā)展，可以更好地提高調度智能化和一體化水平。調度領域具有廣域監(jiān)控與集中管理的特點，通過遠程訪問代理服務實現(xiàn)從本地計算機到遠程服務的訪問，提供網絡文件服務、節(jié)點冗余管理和并行計算等功能?；谠朴嬎愕恼{度愿景，是通過調度數據網絡將分布于各調度中心的應用、數據及IT資源整合成一個抽象的、虛擬的和可動態(tài)擴展的調度資源池，以“需則可用”的方式快速為模型管理、實時監(jiān)控與預警、方式計算、調度計劃編制、安全校核以及調度管理等業(yè)務應用提供所需的計算、控制、信息、存儲等各類服務，從而實現(xiàn)計算能力和海量信息的共享以及應用功能的協(xié)同，更好地適應未來調度領域對業(yè)務融合和多層級、多維度高效協(xié)同的需求。調度領域采用虛擬化分布式處理、云安全等云計算技術，具有廣闊的應用前景。

6 典型制造系統(tǒng)智能調度方法

制造系統(tǒng)的產能主要取決于瓶頸工序的生產能力，提高瓶頸工序的計劃與調度水平能夠優(yōu)化生產資源的配置，改善生產系統(tǒng)的績效。制造系統(tǒng)通常具有多條并行生產線或多道工序，且每道工序有多臺并行設備生產。由于并行生產線或設備功能相同，但存在加工能力不同、生產時間不等、生產成本不一致的非等效特征，從而產生了非等效并行機調度問題；在日益完善的生產制造系統(tǒng)中，為了提高調度的柔性，每道工序可以有多條可行的加工工藝路線，則零件能以不同的方式加工，從而產生了多工藝路線作業(yè)車間調度問題；由于同一種產品作為最小的調度單元，而實際生產中一種產品包含多個工件，對產品進行合理批次劃分進而縮短設備負載縮短周期，結合流水車間調度和并行機調度進而產生了混合流水車間調度問題；由于一些大型復雜產品裝配涉及多副型架、多種零部件供應、多構型產品混流裝配等多種因素，從而產生了混流裝配線調度問題。

6.1 非等效并行機智能調度方法

非等效并行機調度問題，即在多個工件在多臺機器上加工的基礎上，要求每個工件僅需在某臺機器上加工一次，它在各臺機器上的加工時間完全獨立，使得某個調度序列的目標函數最優(yōu)，例如最小化最長完工時間。針對帶重入式特征的非等效并行機動態(tài)調度問題，滾動時間窗口的大小與窗口工件的數量可以依據生產中的實際情況加以確定。采用兩段式編碼策略，完成設備選擇和確定加工順序，解碼后利用集成PD-SRPT規(guī)則的遞階混合帝國競爭算法，進行初始化、同化、交換地位、代價計算、競爭、革命和取優(yōu)過程，對比不同驅動機制并綜合，能夠得到混合利用了PDSRPT規(guī)則的遞階混合帝國競爭算法，對在線調度問題進行局部優(yōu)化的同時，兼顧了全局調度性能，相對于一般的算法，加入基于混沌序列的局部搜索算法后，算法性能有了進一步提高。

6.2 多工藝路線作業(yè)車間智能調度方法

多工藝路線作業(yè)車間智能調度方法主要分為單目標多工藝路線柔性作業(yè)車間調度問題（flexible job shop scheduling problem with process plan flexibility，F(xiàn)JSP-PPF）方法、多目標 FJSPPPF方法和批調度方法。單目標主要是以最小化最長完工時間為目標，研究問題的建模方法、調度模型和優(yōu)化算法，目前的建模方法主要有基于染色體種群的建模方法、基于語法的建模方法和混合整數線性規(guī)劃模型建模方法。在多目標優(yōu)化問題中，最優(yōu)解的定義相比單目標問題中的定義有較大變化，單一目標的比較不適用，需要找到的是包含多個目標的妥協(xié)解，在不降低其他目標性能的情況下盡量提高一個目標的性能，使其成為一個有效解。常見的目標有最小化最長完工時間、平均流經時間、最大機器負載、機器總負載、拖期懲罰、設備空閑時間等。但是，早期大多數車間調度問題的研究沒有考慮工件的批量，而在實際生產中工件往往是成批生產的，即構成批量生產調度問題。多工藝批量調度是柔性作業(yè)車間調度的擴展，工件不僅采用批量生產，而且每種工件具有多條加工路徑。

面向多目標優(yōu)化的三階段蟻群調度算法應用于多工藝路線作業(yè)車間調度問題，采用三層嵌套結構，第一階段為工藝路線選擇層，螞蟻根據一定的狀態(tài)轉移規(guī)則進行搜索，得到工藝路線選擇方案；第二階段為機器指派層，針對工藝路線選擇螞蟻搜索到的每一種工藝路線序列，為各批次的每一道工序指派機器，第三階段為工序排序層，針對機器指派層搜索到的工藝路線序列的每一種機器指派方案，對工藝路線約束下各機器的工序進行排列，并根據序列得到排產方案。相比其他調度方法，應用于FJSP-PPF的三階段蟻群算法能夠表現(xiàn)出明顯的優(yōu)越性。

6.3 混合流水車間智能調度方法

混合流水車間調度問題（hybrid flow-shop scheduling problem，HFSP）結合了流水車間調度問題和并行機調度問題，主要分為靜態(tài)調度和動態(tài)調度。靜態(tài)調度中包含訂單分批問題和多目標生產調度問題，由于智能化方法求解效率高、易于融入問題知識和魯棒性強，在求解大規(guī)模復雜的組合優(yōu)化問題方面具有很好的優(yōu)勢，但基于其自身的不足和優(yōu)勢互補的思想，?？紤]將智能化方法和啟發(fā)式方法相結合。靜態(tài)調度問題中，一般設定一個調度周期的各項參數事先已知并且在該周期內不會改變。但在實際生產過程中，一些參數會隨著生產活動的進行發(fā)生變化，按照確定環(huán)境中建立模型得到的調度方案在實際生產過程中執(zhí)行時可能不再是最優(yōu)的，通常將這些在實際生產過程中的不確定事件稱為動態(tài)事件或擾動。針對動態(tài)事件影響下的調度問題通常采用的措施是重調度，而對重調度策略的研究主要有完全反應式和預測反應式。近年來，群智能方法由于具有較強的通用性和較低的經驗依賴性等優(yōu)點，在重調度中得到了廣泛的重視。

6.4 混流裝配線智能調度方法

以飛機平尾翼裝配為例的混流裝配調度問題具有復雜的動態(tài)生產環(huán)境，經常發(fā)生各種動態(tài)異常事件。由于裝配過程中部分采用人力手工裝配生產模式，裝配過程中經常發(fā)生裝配工時偏差事件；裝配過程中可能發(fā)生零部件裝配報廢現(xiàn)象；裝配型架可能會臨時被其他產品訂單緊急占用。所以該類問題具有多道裝配工序、每個工序具備多個裝配站位多構型混流裝配、裝配周期長等特點，該類問題可分為正向調度問題和逆向調度問題，利用改進的兩級遺傳算法對正向調度問題進行求解，利用混合遺傳算法對逆向調度問題進行求解。由自適應容忍度驅動機制的偏差容忍實驗分析，基于該策略的智能調度算法在求解混流裝配線調度問題上表現(xiàn)出優(yōu)異的求解性能。

7 整合統(tǒng)一——智能調度算法庫應用于多制造過程控制管理

飛機、大型汽輪機、壓縮機、發(fā)動機、大型電力裝備等復雜裝備的生產制造過程，是由多個跨時空、跨地域的制造系統(tǒng)耦合而實現(xiàn)的分布式復雜制造過程。大型負載裝備多為單件小批量生產，其關鍵零部件復雜度高、精度高、價值高，整個產品的生產組織一般都是圍繞其關鍵零部件展開多個不同的制造過程。不同產品制造過程特征不同，因此，產品的生產計劃安排往往需要面向多制造過程進行，從而保證產品總體進度最優(yōu)。

智能調度算法庫應用于多制造過程控制管理多采用面向對象程序設計的思想，充分利用面向對象編程語言的繼承性和多態(tài)性，利用接口開發(fā)技術定義規(guī)范，利用類的繼承實現(xiàn)父類和子類的層次分解，可以使算法庫具有很好的靈活性和可擴展性。利用Microsoft.Net類庫技術，將調度算法封裝為類庫中的不同方法，最終形成DLL文件供其他程序調用。采用三層架構來開發(fā)類庫，數據層包含SQL Server數據庫、專用存檔文件、Excel數據文件，通過協(xié)議與過程層相連，包含參數輸入、問題建模、算法選擇和配置、問題求解和結果輸出，輸出的結果通過應用程序接口反映到應用層，體現(xiàn)在甘特圖、數據報表和性能指標分析圖中。

生產計劃與調度算法庫包含5部分功能，首先在問題定義時，結合調度問題的特征實現(xiàn)對不同類型調度問題的歸類，針對每一類問題給出適用的算法以供選擇；建立模型時，定義統(tǒng)一的建模流程，實現(xiàn)建模流程的格式化、規(guī)范化；算法插件封裝，將不同的算法封裝后作為插件，通過統(tǒng)一的接口集成到平臺中?？筛鶕{度背景添加和移除算法插件，實現(xiàn)平臺快速配置；在系統(tǒng)輸入輸出上，制定兼容各問題描述的輸入規(guī)范，制定統(tǒng)一的文件存儲格式和圖標輸出規(guī)范；基礎功能代碼復用，實現(xiàn)文件讀寫、甘特圖繪制、數據庫訪問、用戶權限控制等基礎功能的模塊化。

結合上述方法結構，多制造過程的智能調度算法庫總的功能實現(xiàn)設計思路如下：首先進行問題定義，選擇問題類別、選擇具體問題、設定問題參數、載入問題相關數據；其次設置算法插件，為各算法建立專有類庫項目；再次建立模型，選擇調度算法、選擇目標函數、設定約束條件、設定算法參數；最后模型建立完畢后求解算法，執(zhí)行算法，顯示算法中間結果，對結果進行輸出和保存?；诖?，可以借助此實例，從中觀和微觀層面實現(xiàn)產品制造過程的控制與管理，以及企業(yè)生產計劃的閉環(huán)控制。

8 調度服務云平臺系統(tǒng)為更多小微型企業(yè)日常調度服務提供方案需求

生產計劃與調度根據市場的需求和企業(yè)的生產能力，對企業(yè)中的產出產品、產出速度、產出時間、勞動力和設備配置以及庫存等問題做出預先的考慮和安排。生產計劃與調度技術是企業(yè)生產管理的核心和關鍵技術，系統(tǒng)、全面、合理的生產計劃與調度方法不僅有助于提高制造企業(yè)的整體運行效率，而且能為企業(yè)帶來顯著的社會效益和經濟效益。隨著企業(yè)信息化、自動化程度的提高，企業(yè)生產計劃與調度方案的制定已從過去的人工排產階段進入計算機排產階段。排產算法也由最初的規(guī)則算法拓展到啟發(fā)式規(guī)則、智能算法等多種方法。企業(yè)資源計劃（ERP）、制造執(zhí)行系統(tǒng)（MES）、高級計劃與排程系統(tǒng)（APS）等的出現(xiàn)，使得精確的制造過程管控成為可能。

隨著“互聯(lián)網＋”的浪潮和“大眾創(chuàng)業(yè)”的政策導向，我國出現(xiàn)了大批小微型企業(yè)。相比大型制造企業(yè)的成熟完善，小微型企業(yè)在制造設備、管理體系、人才配置和資本方面有著較大差距，加之對應的制造系統(tǒng)多樣，使其在企業(yè)管理信息化上面臨著投資高、難以找到合適的軟件系統(tǒng)的難點，從而制約了其進一步的發(fā)展。云服務概念的提出，為小微型制造企業(yè)的信息化提供了新的解決思路。通過提供IaaS、PaaS、SaaS等多種不同類型的云制造服務，以靈活的方式有效地幫助小微制造企業(yè)解決企業(yè)信息化的問題。

制造系統(tǒng)調度云服務的核心思想是實現(xiàn)計劃調度的云端化、層次化、并行化和分布化，其體系由企業(yè)用戶、調度云服務平臺、云計算基礎設施3部分構成，關鍵功能模塊包括數據采集模塊、數據存儲模塊、調度算法庫模塊、調度方案執(zhí)行監(jiān)控模塊、服務封裝與發(fā)布模塊、用戶在線交互模塊，借助物聯(lián)網、云計算等技術來實現(xiàn)制造資源和制造能力的共享、協(xié)同與服務化；實現(xiàn)生產數據的合理組織與有效管理，為上層提供可靠可復用的數據資源；通過調度問題、調度對象、目標約束等不同分類條件，對不同類別的調度算法實行直觀有效的統(tǒng)一管理和規(guī)范化輸入輸出；實現(xiàn)對制造執(zhí)行過程的把控，達到數據反饋的效果；實現(xiàn)某業(yè)務目標將若干個Web服務按照一定業(yè)務邏輯組裝成組合服務并執(zhí)行；使物理世界與信息世界之間的交互更加順暢等。

9 展望

通過閱讀本書，可以幫助從事智能調度的科研人員、學生在熟悉多種制造系統(tǒng)調度模型異同的基礎上充分了解制造系統(tǒng)調度方法的發(fā)展過程和適用條件，全面掌握多種制造系統(tǒng)智能調度算法的原理和應用，領略基于云計算的制造系統(tǒng)調度服務體系的精髓，由淺入深地充分理解非等效并行機調度問題、多工藝路線作業(yè)車間調度問題、混合流水車間調度問題、混流裝配線調度問題的智能調度方法，以及它們特有的云端化處理技術的應用方法，并結合面向多制造過程調度算法庫與制造系統(tǒng)智能調度云服務平臺，分別對實際案例進行全程模擬，這對掌握智能調度方法和云服務技術具有重要指導意義。

閱讀本書，也可以為從事制造業(yè)調度設計和云端化技術的企業(yè)工作人員提供參考。云服務概念的提出和云計算、大規(guī)模數據處理方法、制造服務的出現(xiàn)，為小微型企業(yè)的制造提供了新方案。智能調度作為制造系統(tǒng)運行優(yōu)化的核心，將和云技術結合得更加緊密，從而呈現(xiàn)出云端化、層次化、并行化和分布化特點。

云端化 計劃調度算法以遠程服務的形式提供，核心調度算法庫部署在云平臺上，企業(yè)通過遠程調用的方式租用相應的調度模塊，來管理車間生產過程。

層次化 實現(xiàn)制造系統(tǒng)調度云服務平臺內部架構的分層設計，將通過數據訪問、調度算法、對外接口、圖形報表等不同目標的功能點進行優(yōu)化組合，內聚成數據訪問層、業(yè)務邏輯層、用戶服務層，使得各層間解耦，更加便于系統(tǒng)開發(fā)和提供服務。

并行化 通過數據分區(qū)、算法分解、資源協(xié)調等方式，將原有的單線程的算法發(fā)放到多處理器多線程上，以實現(xiàn)同時處理大量數據，并充分利用云平臺帶來的大量計算資源，加快處理速度。

分布式 通過使用眾多服務器以可控的成本快速搭建調度云服務平臺，同時提供高并發(fā)能力、高吞吐能力、高計算能力、高擴展能力、高容錯能力和高可靠性的服務。

基于物聯(lián)網和云服務，實現(xiàn)智能設備之間、人與生產資料之間的互聯(lián)互通，將會使更多企業(yè)產生生產制造變革，逐步走向智能化。隨著人工智能技術的不斷發(fā)展，應用機器學習和深度學習的方法在智能調度上的應用將更加廣泛和深入，并且結合多領域（如生物技術、金融學、語言學甚至社會行為學等）在智能調度方面的跨學科研究也將呈現(xiàn)出越來越深入的趨勢。相信未來智能調度和云服務將在生產設備更新、不斷吸引新型技術的同時，不斷地發(fā)展和變化，并最終能夠在企業(yè)中生根發(fā)芽，引領中國智能制造創(chuàng)造出更多成就，使祖國的工業(yè)發(fā)展更加繁榮昌盛。