第一章生產調度概論

1、制造過程調度理論及應用Scheduling Theory for Manufacturing Process and Its Applications自動化系 曹政才2015.9.18課程簡介n 為什么開設本課程？制造過程調度技術研究是國內外先進制造與自動化、系統(tǒng)工程、工業(yè)工程、管理工程等領域前沿性研究方向之一；制造過程調度理論和方法研究極富挑戰(zhàn)性；NP難題；復雜優(yōu)化問題；制造企業(yè)對制造過程調度理論和方法應用需求越來越強；通過開設本課程，使更多的研究生了解和掌握該領域的理論與方法，提高研究生科研能力和創(chuàng)新能力，培養(yǎng)可從事調度技術研究及應用的專業(yè)人才，促進調度技術的進一步發(fā)展課程簡介n本課程有哪

2、些教學內容？制造過程調度問題概述制造過程調度問題基本描述方法；制造過程調度問題基本優(yōu)化算法；制造過程調度問題算法仿真實驗；制造過程調度問題專項課題研究；制造過程調度問題實際應用案例；制造企業(yè)參觀/調度軟件演示調度問題三元表示法析取圖模型數(shù)學規(guī)劃模型常用分類方法調度問題基本概念國內外發(fā)展狀況常用研究方法數(shù)學規(guī)劃算法啟發(fā)式算法智能優(yōu)化算法課程簡介n通過本課程的學習將有哪些收獲？掌握制造過程調度問題概念、基本描述方法及優(yōu)化理論和方法；通過專項課題(Project)研究，培養(yǎng)和提高科研能力；接觸制造過程調度問題的實際背景，拓寬知識面，掌握利用所學調度理論和方法解決實際調度問題的基本能力；部分學有余力的

3、同學在課程結束時將能撰寫具有一定學術水平的調度算法相關論文；課程簡介n本課程的評分體系課堂表現(xiàn)：20；實驗：20；作業(yè)：10；專項課題研究報告：50；課程簡介n課程教材/參考書目：教材：劉民，吳澄.制造過程智能優(yōu)化調度算法及其應用，國防工業(yè)出版社，2008；劉民，制造過程調度理論及應用講義；王凌，車間調度及其遺傳算法，清華大學出版社，2003Peter Brucker, Scheduling Algorithms, Springer Press，1998 （Sigrid Knust University of Osnabrck, Germany ）課程簡介n 基礎知識參考書目：有關遺傳算法、禁

4、忌搜索基礎知識；遺傳算法： 陳國良，遺傳算法及其應用 玄光男，程潤偉，遺傳算法與工程設計（汪定偉 等譯）禁忌搜索方法： F. Glover. Tabu Search Part I. ORSA Journal on Computing. Vol.1, No.3, 1989: 190-206. F. Glover, Tabu Search Part, ORSA Journal on Computing. Vol.2, 1990: 4-32.分支定界算法； 胡運權 運籌學教程 計算復雜性理論； 組合最優(yōu)化 : 算法和復雜性 / (美) 帕帕季米特里烏, 施泰格利茨 著; 劉振宏, 蔡茂誠 譯 制造過

5、程調度概論n本節(jié)課內容 什么是制造過程調度問題 為什么要研究制造過程調度理論與方法 求解制造過程調度問題的常用方法 小結制造過程調度概論n本節(jié)課內容 為什么要研究制造過程調度理論與方法 求解制造過程調度問題的常用方法 小結制造過程調度概論 什么是調度問題？ 調度問題一般是指如下一類資源優(yōu)化問題：調度問題一般是指如下一類資源優(yōu)化問題： 如何將如何將資源資源(resources)分配給分配給任務任務(tasks)，在滿足相關在滿足相關約束條件約束條件(constraints) 下，使得某下，使得某項項(或多項或多項)性能指標性能指標(objective/performance)達到最優(yōu)。達到最優(yōu)。

6、 生產和日常生活中有哪些調度問題的例子？制造過程調度概論n什么是制造過程調度問題? 制造過程調度問題是指如下一類資源優(yōu)化問題：制造過程調度問題是指如下一類資源優(yōu)化問題： 將將機器機器(含各種配件等資源含各種配件等資源)分配給分配給工件工件(任任務務)，即安排各機器上相應工件的上機時間或上，即安排各機器上相應工件的上機時間或上機順序，在滿足相關機順序，在滿足相關約束條件約束條件(工藝約束、資源工藝約束、資源約束等約束等) 下使某項或多項下使某項或多項性能指標性能指標(制造周期、制造周期、總拖期數(shù)總拖期數(shù)/總拖期時間、機器利用率、能耗總拖期時間、機器利用率、能耗/物耗、物耗、成本等成本等)達到最優(yōu)

7、。達到最優(yōu)。n 制造過程調度在企業(yè)生產過程中的位置AMR提出的三層企業(yè)集成模型制造過程調度概論制造過程調度是MES中的 關鍵業(yè)務執(zhí)行生產如何生產生產什么制造過程調度概論n 制造過程調度的常見形式CAD/CAE/CAPP/PDM制造過程調度概論n什么是制造過程調度問題?從現(xiàn)代集成制造系統(tǒng)(CIMS)/制造業(yè)信息化角度：計劃與調度在制品跟蹤管理原料管理庫存管理質量管理設備管理計劃管理人力資源管理工藝管理制造過程調度重點解決該系統(tǒng)中的作業(yè)計劃優(yōu)化制定與動態(tài)調整問題計劃與調度既屬于管理自動化范疇又屬于制造過程自動化的范疇底層自動化設備制造過程調度概論n實際制造過程調度問題的特點規(guī)模大：如紡織生產制造過

8、程（上千臺設備、上萬個加工任務）；約束復雜：資源約束、工藝約束.；不確定因素多：訂單插入/撤銷/更改、設備故障、質量事故、原料短缺、工藝更改等；多目標相互制約：制造周期、總拖期時間/總拖期數(shù)、生產成本等；軋鋼生產線 色織生產線汽車生產線實際生產線調度問題舉例制造過程調度概論n本節(jié)課內容 什么是制造過程調度問題 求解制造過程調度問題的常用方法 小結制造過程調度概論n為什么要研究制造過程調度理論與方法？制造業(yè)在國民經濟中占據(jù)支柱地位；鋼鐵石化紡織微電子機械制造業(yè)的發(fā)展狀況直接影響了國家的經濟基礎和綜合國力的強弱；全球500強企業(yè)中，制造企業(yè)占208家我國制造業(yè)年產值占GDP的37.8%制造過程調度

9、概論n 為什么要研究制造過程調度理論與方法？隨著我國加入WTO，企業(yè)面臨的形勢愈加嚴峻，如何挖潛增效，在不過多增加投資的情況下實現(xiàn)生產過程高效運行，以有效提高生產效率，降低生產成本和能耗/物耗，提高產品質量，提高經濟效益和綜合競爭力已成為眾多企業(yè)迫在眉睫、亟需解決的關鍵難題；以信息化帶動工業(yè)化，促進工業(yè)化和信息化融合，用信息技術改造傳統(tǒng)產業(yè)，實現(xiàn)制造業(yè)跨越式發(fā)展是國家的重要戰(zhàn)略決策，而生產制造過程的建模、優(yōu)化與調度技術是信息技術的重要組成部分之一，其在提高制造企業(yè)經濟效益和綜合競爭力中有舉足輕重的作用；制造過程調度概論n 為什么要研究制造過程調度理論與方法？早期的生產系統(tǒng)提高產能主要通過購買新

10、設備及投入更多人力資源實現(xiàn)，隨著市場競爭日趨激烈，僅靠購買新設備、投入人力資源提高產能將大幅增加企業(yè)生產成本。企業(yè)提高經濟效益的有效途徑應是提高產品附加值、挖掘已有生產系統(tǒng)產能、降低成本等；某大型色織企業(yè)制造周期每縮短1%，可增加出口額上百萬美元；某微電子制造企業(yè)制造周期每縮短1%，可增加利潤上千萬元；某大型汽車制造企業(yè)制造周期每縮短10%，每月可增加產值1200萬元。制造過程調度概論n 為什么要研究制造過程調度理論與方法？研究者們已提出各種方法，如各類數(shù)學規(guī)劃方法、傳統(tǒng)啟發(fā)式方法、傳統(tǒng)人工智能方法（專家系統(tǒng)、案例推理、約束滿足等）、智能優(yōu)化算法（進化計算、禁忌搜索）、基于仿真的方法等，這些方

11、法已在實際調度問題中得到初步應用并有一些成功案例；某紡織企業(yè)在實現(xiàn)信息集成的基礎上，采用以智能調度系統(tǒng)為核心的集成化智能信息系統(tǒng)，使總生產周期縮短50%，準時交單率提高40%；某汽車制造企業(yè)采用以智能調度系統(tǒng)為核心的MES，使總生產周期縮短12.5%。制造過程調度概論n為什么要研究制造過程調度理論與方法？從生產模式的發(fā)展看：作坊生產模式大批量生產模式多品種小批量生產模式批量小，產品類型少批量大，產品類型少產品類型多，同品種批量小，生產規(guī)模大，交貨期要求高調度過程簡單，主要靠直觀判斷作出調度過程具有一定難度，需要較豐富的人工經驗或采用簡單啟發(fā)式方法調度難度高，單憑人工經驗或簡單啟發(fā)式方法，無法滿

12、足生產要求制造過程調度概論n為什么要研究制造過程調度理論與方法？從控制的角度看：粗放型管理集約型管理單一設備控制生產線控制制造過程調度制造過程調度調度問題不僅是一個管理優(yōu)化問題，同時是一個重要的生產線控制問題，需要采用制造過程調度理論與方法解決傳統(tǒng)/現(xiàn)代控制理論所解決的問題，控制對象往往用微分/差分方程表示主要關注同時關注制造過程調度問題一般無法用微分/差分方程表示，一般屬于離散事件動態(tài)系統(tǒng)(DEDS)問題調度問題操作優(yōu)化問題故障預報問題制造過程調度概論n為什么要研究制造過程調度理論與方法？制造過程調度問題是一類典型的復雜NP問題，該問題與諸多其它組合優(yōu)化問題(TSP、Packing、VRP、

13、項目調度問題等)具有許多內在相似性，該問題研究成果對解決其它組合優(yōu)化問題也有很好的指導和借鑒作用；制造過程調度概論n本節(jié)課內容 什么是制造過程調度問題 為什么要研究制造過程調度理論與方法 小結制造過程調度概論n求解制造過程調度問題的常用方法基于運籌學的方法基于傳統(tǒng)啟發(fā)式的方法基于傳統(tǒng)人工智能的方法基于計算機仿真的方法基于軟計算的方法制造過程調度概論n求解制造過程調度問題的主要方法基于運籌學的方法；實際制造過程調度問題數(shù)學規(guī)劃模型運籌學方法求解形成實際問題解哪些數(shù)學規(guī)劃模型和 求解方法可以采用？n以求解最優(yōu)解為目標；n存在“指數(shù)爆炸”現(xiàn)象；特點：分支定界法動態(tài)規(guī)劃 割平面法 拉格朗日松弛 等等處

14、理變換化簡并附加假設條件制造過程調度概論n求解制造過程調度問題的主要方法傳統(tǒng)啟發(fā)式方法(基于規(guī)則的簡單啟發(fā)式方法和復雜啟發(fā)式方法)； 實際制造過程調度問題用與工件或機器等相關的簡單信息決定上機順序形成實際問題解n計算量小，運行速度快；n對具有復雜約束、復雜目標或大規(guī)模等特 征的調度問題，其調度效果不令人滿意；一些簡單調度規(guī)則（基于規(guī)則的簡單啟發(fā)式方法）舉例？特點：LPT/SPT/EDD制造過程調度概論n求解制造過程調度問題的主要方法基于傳統(tǒng)人工智能的方法；專家系統(tǒng)；案例推理；約束滿足；n 采用傳統(tǒng)人工智能方法并利用豐富的問題信 息以產生比傳統(tǒng)啟發(fā)式方法更好的調度效果， 前兩類往往應用于特定行業(yè)

15、調度問題中；n 對規(guī)模大、帶復雜約束、多目標等特點的 復雜調度問題難以實用；特點：制造過程調度概論n求解制造過程調度問題的主要方法基于計算機仿真的方法；實際制造過程調度問題建立仿真模型確定初始參數(shù)執(zhí)行仿真形成實際問題解是否滿意n建模靈活；n建模過程耗時長；n對復雜問題，難以 得到令人滿意的調 度效果；n單純采用仿真方法 難以有效解決實時 調度問題；特點：NY制造過程調度概論n求解制造過程調度問題的主要方法軟計算方法；遺傳算法；禁忌搜索算法；模擬退火算法；粒子群算法/蟻群算法等；終止條件初始解通過某種尋優(yōu)策略改進當前解新解退出n不以尋求問題最優(yōu)解為目標；n求解過程基于簡單的形式化描 述（如編碼過

16、程），將決策變 量包含在待尋優(yōu)個體中；n對目標函數(shù)無特殊要求(可導/可微/凸函數(shù)等)；n方便在算法中加入問題特征信息；特點：制造過程調度概論n求解制造過程調度問題的主要方法遺傳算法； 遺傳算法(由美國Michigan的 Holland于1975年提出)是一種基于“優(yōu)勝劣汰”自然選擇思想和遺傳機制的搜索算法，其基本步驟包括編碼、初始種群產生、適應度評價、交叉和變異。遺傳算法在計算機上模擬生物的進化過程和基因操作，實現(xiàn)簡單，且適用問題廣泛，因此近年來在優(yōu)化領域得到普遍應用。制造過程調度概論n求解制造過程調度問題的主要方法人類的演化過程制造過程調度概論n 求解制造過程調度問題的主要方法禁忌搜索算法；

17、 禁忌搜索算法(由美國Mississippi大學的Glover于1986年提出)是在傳統(tǒng)局部搜索方法基礎上引入禁忌技術產生的一種基于鄰域的搜索方法，其是對傳統(tǒng)局部搜索方法的一種改進。 其基本思想是在搜索過程中通過引入一個記憶裝置，即具有一定長度的禁忌表(表中記錄了最近所進行的所有解的移動，禁忌對象可以是一個解，也可以是解的一部分，或是解的某種屬性等)，以避免基于鄰域的搜索過程陷入循環(huán)或局部最優(yōu)。制造過程調度概論n求解制造過程調度問題的主要方法現(xiàn)有求解方法存在的問題對實際問題有較多前提假設、對問題簡化過多，因而對復雜調度問題缺乏實用性；對調度問題本身的分析不夠透徹，對實際調度問題數(shù)據(jù)利用不夠充分，問題特征信息未得到充分利用；現(xiàn)有調度問題基本優(yōu)化算法大多針對確定性調度問題提出，對不確定環(huán)境下的復雜調度問題缺乏有效求解算法；缺乏對實際問題具有較好調度性能的綜合(集成)算法；制造過程調度概論n 本章小結什么是制造過程調度問題為什么要研究制造過程調度問題制造過程調度問題的常用研究方法參考文獻（綜述文章）： 劉民. 基于數(shù)據(jù)的生產過程調度方法研究綜述. 自動化學報, 2009, 35(6):785-805 蘇