制造過(guò)程調(diào)度理論及應(yīng)用教材(共36頁(yè)).ppt

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

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

3、的根本能力；n局部學(xué)有余力的同學(xué)在課程結(jié)束時(shí)將能撰寫具有一定學(xué)術(shù)水平的調(diào)度算法相關(guān)論文；課程簡(jiǎn)介n本課程的評(píng)分體系課堂表現(xiàn)：20；實(shí)驗(yàn)：20；作業(yè)：10；專項(xiàng)課題研究報(bào)告：50；課程簡(jiǎn)介n課程教材/參考書目：n教材：劉民，吳澄.?制造過(guò)程智能優(yōu)化調(diào)度算法及其應(yīng)用?，國(guó)防工業(yè)出版社，2021；n劉民，?制造過(guò)程調(diào)度理論及應(yīng)用?講義；n王凌，?車間調(diào)度及其遺傳算法?，清華大學(xué)出版社，2003nPeter Brucker, Scheduling Algorithms, Springer Press，1998 Sigrid Knust University of Osnabrck, Germany 課

4、程簡(jiǎn)介n 根底知識(shí)參考書目：n 有關(guān)遺傳算法、禁忌搜索根底知識(shí)；n 遺傳算法： n 陳國(guó)良，遺傳算法及其應(yīng)用n 玄光男，程潤(rùn)偉，遺傳算法與工程設(shè)計(jì)汪定偉 等譯n 禁忌搜索方法：n F. Glover. Tabu Search Part I. ORSA Journal on Computing. Vol.1, No.3, 1989: 190-206. n F. Glover, Tabu Search Part, ORSA Journal on Computing. Vol.2, 1990: 4-32.n 分支定界算法；n 胡運(yùn)權(quán) 運(yùn)籌學(xué)教程 n 計(jì)算復(fù)雜性理論；n 組合最優(yōu)化 : 算法和復(fù)雜性

5、/ (美) 帕帕季米特里烏, 施泰格利茨 著; 劉振宏, 蔡茂誠(chéng) 譯 制造過(guò)程調(diào)度概論n本節(jié)課內(nèi)容 什么是制造過(guò)程調(diào)度問(wèn)題 為什么要研究制造過(guò)程調(diào)度理論與方法 求解制造過(guò)程調(diào)度問(wèn)題的常用方法 小結(jié)制造過(guò)程調(diào)度概論n本節(jié)課內(nèi)容 為什么要研究制造過(guò)程調(diào)度理論與方法 求解制造過(guò)程調(diào)度問(wèn)題的常用方法 小結(jié)制造過(guò)程調(diào)度概論 什么是調(diào)度問(wèn)題？ 調(diào)度問(wèn)題一般是指如下一類資源優(yōu)化問(wèn)題： 如何將資源(resources)分配給任務(wù)(tasks)，在滿足相關(guān)約束條件(constraints) 下，使得某項(xiàng)(或多項(xiàng))性能指標(biāo)(objective/performance)到達(dá)最優(yōu)。 生產(chǎn)和日常生活中有哪些調(diào)度問(wèn)題的例

6、子？制造過(guò)程調(diào)度概論n什么是制造過(guò)程調(diào)度問(wèn)題?n n制造過(guò)程調(diào)度問(wèn)題是指如下一類資源優(yōu)化問(wèn)題：n 將機(jī)器(含各種配件等資源)分配給工件(任務(wù))，即安排各機(jī)器上相應(yīng)工件的上機(jī)時(shí)間或上機(jī)順序，在滿足相關(guān)約束條件(工藝約束、資源約束等) 下使某項(xiàng)或多項(xiàng)性能指標(biāo)(制造周期、總拖期數(shù)/總拖期時(shí)間、機(jī)器利用率、能耗/物耗、本錢等)到達(dá)最優(yōu)。n 制造過(guò)程調(diào)度在企業(yè)生產(chǎn)過(guò)程中的位置AMR提出的三層企業(yè)集成模型制造過(guò)程調(diào)度概論制造過(guò)程調(diào)度是MES中的 關(guān)鍵業(yè)務(wù)執(zhí)行生產(chǎn)如何生產(chǎn)生產(chǎn)什么制造過(guò)程調(diào)度概論n 制造過(guò)程調(diào)度的常見形式CAD/CAE/CAPP/PDM制造過(guò)程調(diào)度概論n什么是制造過(guò)程調(diào)度問(wèn)題?從現(xiàn)代集成制造

7、系統(tǒng)(CIMS)/制造業(yè)信息化角度：方案與調(diào)度在制品跟蹤管理原料管理庫(kù)存管理質(zhì)量管理設(shè)備管理方案管理人力資源管理工藝管理制造過(guò)程調(diào)度重點(diǎn)解決該系統(tǒng)中的作業(yè)方案優(yōu)化制定與動(dòng)態(tài)調(diào)整問(wèn)題方案與調(diào)度既屬于管理自動(dòng)化范疇又屬于制造過(guò)程自動(dòng)化的范疇底層自動(dòng)化設(shè)備制造過(guò)程調(diào)度概論n實(shí)際制造過(guò)程調(diào)度問(wèn)題的特點(diǎn)n規(guī)模大：如紡織生產(chǎn)制造過(guò)程上千臺(tái)設(shè)備、上萬(wàn)個(gè)加工任務(wù)；n約束復(fù)雜：資源約束、工藝約束.；n不確定因素多：訂單插入/撤銷/更改、設(shè)備故障、質(zhì)量事故、原料短缺、工藝更改等；n多目標(biāo)相互制約：制造周期、總拖期時(shí)間/總拖期數(shù)、生產(chǎn)本錢等；軋鋼生產(chǎn)線 色織生產(chǎn)線汽車生產(chǎn)線實(shí)際生產(chǎn)線調(diào)度問(wèn)題舉例制造過(guò)程調(diào)度概論n本

8、節(jié)課內(nèi)容 什么是制造過(guò)程調(diào)度問(wèn)題 求解制造過(guò)程調(diào)度問(wèn)題的常用方法 小結(jié)制造過(guò)程調(diào)度概論n為什么要研究制造過(guò)程調(diào)度理論與方法？n制造業(yè)在國(guó)民經(jīng)濟(jì)中占據(jù)支柱地位；n鋼鐵n石化n紡織n微電子n機(jī)械n制造業(yè)的開展?fàn)顩r直接影響了國(guó)家的經(jīng)濟(jì)根底和綜合國(guó)力的強(qiáng)弱；全球500強(qiáng)企業(yè)中，制造企業(yè)占208家我國(guó)制造業(yè)年產(chǎn)值占GDP的37.8%制造過(guò)程調(diào)度概論n 為什么要研究制造過(guò)程調(diào)度理論與方法？n 隨著我國(guó)參加WTO，企業(yè)面臨的形勢(shì)愈加嚴(yán)峻，如何挖潛增效，在不過(guò)多增加投資的情況下實(shí)現(xiàn)生產(chǎn)過(guò)程高效運(yùn)行，以有效提高生產(chǎn)效率，降低生產(chǎn)本錢和能耗/物耗，提高產(chǎn)品質(zhì)量，提高經(jīng)濟(jì)效益和綜合競(jìng)爭(zhēng)力已成為眾多企業(yè)迫在眉睫、亟需

9、解決的關(guān)鍵難題；n 以信息化帶開工業(yè)化，促進(jìn)工業(yè)化和信息化融合，用信息技術(shù)改造傳統(tǒng)產(chǎn)業(yè)，實(shí)現(xiàn)制造業(yè)跨越式開展是國(guó)家的重要戰(zhàn)略決策，而生產(chǎn)制造過(guò)程的建模、優(yōu)化與調(diào)度技術(shù)是信息技術(shù)的重要組成局部之一，其在提高制造企業(yè)經(jīng)濟(jì)效益和綜合競(jìng)爭(zhēng)力中有舉足輕重的作用；制造過(guò)程調(diào)度概論n 為什么要研究制造過(guò)程調(diào)度理論與方法？n 早期的生產(chǎn)系統(tǒng)提高產(chǎn)能主要通過(guò)購(gòu)置新設(shè)備及投入更多人力資源實(shí)現(xiàn)，隨著市場(chǎng)競(jìng)爭(zhēng)日趨劇烈，僅靠購(gòu)置新設(shè)備、投入人力資源提高產(chǎn)能將大幅增加企業(yè)生產(chǎn)本錢。企業(yè)提高經(jīng)濟(jì)效益的有效途徑應(yīng)是提高產(chǎn)品附加值、挖掘已有生產(chǎn)系統(tǒng)產(chǎn)能、降低本錢等；n 某大型色織企業(yè)制造周期每縮短1%，可增加出口額上百萬(wàn)美元；

10、n 某微電子制造企業(yè)制造周期每縮短1%，可增加利潤(rùn)上千萬(wàn)元；n 某大型汽車制造企業(yè)制造周期每縮短10%，每月可增加產(chǎn)值1200萬(wàn)元。制造過(guò)程調(diào)度概論n 為什么要研究制造過(guò)程調(diào)度理論與方法？n 研究者們已提出各種方法，如各類數(shù)學(xué)規(guī)劃方法、傳統(tǒng)啟發(fā)式方法、傳統(tǒng)人工智能方法專家系統(tǒng)、案例推理、約束滿足等、智能優(yōu)化算法進(jìn)化計(jì)算、禁忌搜索、基于仿真的方法等，這些方法已在實(shí)際調(diào)度問(wèn)題中得到初步應(yīng)用并有一些成功案例；n 某紡織企業(yè)在實(shí)現(xiàn)信息集成的根底上，采用以智能調(diào)度系統(tǒng)為核心的集成化智能信息系統(tǒng)，使總生產(chǎn)周期縮短50%，準(zhǔn)時(shí)交單率提高40%；n 某汽車制造企業(yè)采用以智能調(diào)度系統(tǒng)為核心的MES，使總生產(chǎn)周期

11、縮短12.5%。制造過(guò)程調(diào)度概論n為什么要研究制造過(guò)程調(diào)度理論與方法？n從生產(chǎn)模式的開展看：作坊生產(chǎn)模式大批量生產(chǎn)模式多品種小批量生產(chǎn)模式批量小，產(chǎn)品類型少批量大，產(chǎn)品類型少產(chǎn)品類型多，同品種批量小，生產(chǎn)規(guī)模大，交貨期要求高調(diào)度過(guò)程簡(jiǎn)單，主要靠直觀判斷作出調(diào)度過(guò)程具有一定難度，需要較豐富的人工經(jīng)驗(yàn)或采用簡(jiǎn)單啟發(fā)式方法調(diào)度難度高，單憑人工經(jīng)驗(yàn)或簡(jiǎn)單啟發(fā)式方法，無(wú)法滿足生產(chǎn)要求制造過(guò)程調(diào)度概論n為什么要研究制造過(guò)程調(diào)度理論與方法？從控制的角度看：粗放型管理集約型管理單一設(shè)備控制生產(chǎn)線控制制造過(guò)程調(diào)度制造過(guò)程調(diào)度調(diào)度問(wèn)題不僅是一個(gè)管理優(yōu)化問(wèn)題，同時(shí)是一個(gè)重要的生產(chǎn)線控制問(wèn)題，需要采用制造過(guò)程調(diào)度理論

12、與方法解決傳統(tǒng)/現(xiàn)代控制理論所解決的問(wèn)題，控制對(duì)象往往用微分/差分方程表示主要關(guān)注同時(shí)關(guān)注制造過(guò)程調(diào)度問(wèn)題一般無(wú)法用微分/差分方程表示，一般屬于離散事件動(dòng)態(tài)系統(tǒng)(DEDS)問(wèn)題調(diào)度問(wèn)題操作優(yōu)化問(wèn)題故障預(yù)報(bào)問(wèn)題制造過(guò)程調(diào)度概論n為什么要研究制造過(guò)程調(diào)度理論與方法？n制造過(guò)程調(diào)度問(wèn)題是一類典型的復(fù)雜NP問(wèn)題，該問(wèn)題與諸多其它組合優(yōu)化問(wèn)題(TSP、Packing、VRP、工程調(diào)度問(wèn)題等)具有許多內(nèi)在相似性，該問(wèn)題研究成果對(duì)解決其它組合優(yōu)化問(wèn)題也有很好的指導(dǎo)和借鑒作用；制造過(guò)程調(diào)度概論n本節(jié)課內(nèi)容 什么是制造過(guò)程調(diào)度問(wèn)題 為什么要研究制造過(guò)程調(diào)度理論與方法 小結(jié)制造過(guò)程調(diào)度概論n求解制造過(guò)程調(diào)度問(wèn)題的

13、常用方法基于運(yùn)籌學(xué)的方法基于傳統(tǒng)啟發(fā)式的方法基于傳統(tǒng)人工智能的方法基于計(jì)算機(jī)仿真的方法基于軟計(jì)算的方法制造過(guò)程調(diào)度概論n求解制造過(guò)程調(diào)度問(wèn)題的主要方法基于運(yùn)籌學(xué)的方法；實(shí)際制造過(guò)程調(diào)度問(wèn)題數(shù)學(xué)規(guī)劃模型運(yùn)籌學(xué)方法求解形成實(shí)際問(wèn)題解哪些數(shù)學(xué)規(guī)劃模型和 求解方法可以采用？l以求解最優(yōu)解為目標(biāo)；l存在“指數(shù)爆炸現(xiàn)象；特點(diǎn)：分支定界法動(dòng)態(tài)規(guī)劃 割平面法 拉格朗日松弛 等等處理變換化簡(jiǎn)并附加假設(shè)條件制造過(guò)程調(diào)度概論n求解制造過(guò)程調(diào)度問(wèn)題的主要方法n傳統(tǒng)啟發(fā)式方法(基于規(guī)那么的簡(jiǎn)單啟發(fā)式方法和復(fù)雜啟發(fā)式方法)； 實(shí)際制造過(guò)程調(diào)度問(wèn)題用與工件或機(jī)器等相關(guān)的簡(jiǎn)單信息決定上機(jī)順序形成實(shí)際問(wèn)題解l計(jì)算量小，運(yùn)行速度

14、快；l對(duì)具有復(fù)雜約束、復(fù)雜目標(biāo)或大規(guī)模等特 征的調(diào)度問(wèn)題，其調(diào)度效果不令人滿意；一些簡(jiǎn)單調(diào)度規(guī)那么基于規(guī)那么的簡(jiǎn)單啟發(fā)式方法舉例？特點(diǎn)：LPT/SPT/EDD制造過(guò)程調(diào)度概論n求解制造過(guò)程調(diào)度問(wèn)題的主要方法基于傳統(tǒng)人工智能的方法；專家系統(tǒng)；案例推理；約束滿足；l 采用傳統(tǒng)人工智能方法并利用豐富的問(wèn)題信 息以產(chǎn)生比傳統(tǒng)啟發(fā)式方法更好的調(diào)度效果， 前兩類往往應(yīng)用于特定行業(yè)調(diào)度問(wèn)題中；l 對(duì)規(guī)模大、帶復(fù)雜約束、多目標(biāo)等特點(diǎn)的 復(fù)雜調(diào)度問(wèn)題難以實(shí)用；特點(diǎn)：制造過(guò)程調(diào)度概論n求解制造過(guò)程調(diào)度問(wèn)題的主要方法基于計(jì)算機(jī)仿真的方法；實(shí)際制造過(guò)程調(diào)度問(wèn)題建立仿真模型確定初始參數(shù)執(zhí)行仿真形成實(shí)際問(wèn)題解是否滿意l建

15、模靈活；l建模過(guò)程耗時(shí)長(zhǎng)；l對(duì)復(fù)雜問(wèn)題，難以 得到令人滿意的調(diào) 度效果；l單純采用仿真方法 難以有效解決實(shí)時(shí) 調(diào)度問(wèn)題；特點(diǎn)：NY制造過(guò)程調(diào)度概論n求解制造過(guò)程調(diào)度問(wèn)題的主要方法軟計(jì)算方法；遺傳算法；禁忌搜索算法；模擬退火算法；粒子群算法/蟻群算法等；終止條件初始解通過(guò)某種尋優(yōu)策略改進(jìn)當(dāng)前解新解退出l不以尋求問(wèn)題最優(yōu)解為目標(biāo)；l求解過(guò)程基于簡(jiǎn)單的形式化描l 述如編碼過(guò)程，將決策變l 量包含在待尋優(yōu)個(gè)體中；l對(duì)目標(biāo)函數(shù)無(wú)特殊要求(可導(dǎo)/可微/凸函數(shù)等)；l方便在算法中參加問(wèn)題特征信息；特點(diǎn)：制造過(guò)程調(diào)度概論n求解制造過(guò)程調(diào)度問(wèn)題的主要方法n遺傳算法；n 遺傳算法(由美國(guó)Michigan的 Hol

16、land于1975年提出)是一種基于“優(yōu)勝劣汰自然選擇思想和遺傳機(jī)制的搜索算法，其根本步驟包括編碼、初始種群產(chǎn)生、適應(yīng)度評(píng)價(jià)、交叉和變異。遺傳算法在計(jì)算機(jī)上模擬生物的進(jìn)化過(guò)程和基因操作，實(shí)現(xiàn)簡(jiǎn)單，且適用問(wèn)題廣泛，因此近年來(lái)在優(yōu)化領(lǐng)域得到普遍應(yīng)用。制造過(guò)程調(diào)度概論n求解制造過(guò)程調(diào)度問(wèn)題的主要方法人類的演化過(guò)程制造過(guò)程調(diào)度概論n 求解制造過(guò)程調(diào)度問(wèn)題的主要方法n 禁忌搜索算法；n 禁忌搜索算法(由美國(guó)Mississippi大學(xué)的Glover于1986年提出)是在傳統(tǒng)局部搜索方法根底上引入禁忌技術(shù)產(chǎn)生的一種基于鄰域的搜索方法，其是對(duì)傳統(tǒng)局部搜索方法的一種改進(jìn)。n 其根本思想是在搜索過(guò)程中通過(guò)引入一個(gè)

17、記憶裝置，即具有一定長(zhǎng)度的禁忌表(表中記錄了最近所進(jìn)行的所有解的移動(dòng)，禁忌對(duì)象可以是一個(gè)解，也可以是解的一局部，或是解的某種屬性等)，以防止基于鄰域的搜索過(guò)程陷入循環(huán)或局部最優(yōu)。制造過(guò)程調(diào)度概論n求解制造過(guò)程調(diào)度問(wèn)題的主要方法n現(xiàn)有求解方法存在的問(wèn)題n對(duì)實(shí)際問(wèn)題有較多前提假設(shè)、對(duì)問(wèn)題簡(jiǎn)化過(guò)多，因而對(duì)復(fù)雜調(diào)度問(wèn)題缺乏實(shí)用性；n對(duì)調(diào)度問(wèn)題本身的分析不夠透徹，對(duì)實(shí)際調(diào)度問(wèn)題數(shù)據(jù)利用不夠充分，問(wèn)題特征信息未得到充分利用；n現(xiàn)有調(diào)度問(wèn)題根本優(yōu)化算法大多針對(duì)確定性調(diào)度問(wèn)題提出，對(duì)不確定環(huán)境下的復(fù)雜調(diào)度問(wèn)題缺乏有效求解算法；n缺乏對(duì)實(shí)際問(wèn)題具有較好調(diào)度性能的綜合(集成)算法；制造過(guò)程調(diào)度概論n 本章小結(jié)n 什么是制造過(guò)程調(diào)度問(wèn)題n 為什么要研究制造過(guò)程調(diào)度問(wèn)題n 制造過(guò)程調(diào)度問(wèn)題的常用研究方法n 參考文獻(xiàn)綜述文章：n 劉民. 基于數(shù)據(jù)的生產(chǎn)過(guò)程調(diào)度方法研究綜述. 自動(dòng)化學(xué)報(bào), 2021, 35(6):785-805 n蘇格蘭鄧迪大學(xué)應(yīng)用物理、