生產調度及智能優(yōu)化(chen)

1、02.01.2021,生產調度及智能優(yōu)化,24092499（O）/02.01.2021,生產調度,生產調度與運籌學,Q：區(qū)別？ 聯系,生產調度,運籌學,02.01.2021,生產調度,什么是生產調度,即按時間分配資源完成任務/作業(yè)的過程或方法。要求：任務/作業(yè)必須是可分割的,生產調度問題 Q：現場有哪些,02.01.2021,生產調度,生產調度與生產計劃,都是對生產過程的規(guī)劃與控制（均考慮優(yōu)化的目的），主要區(qū)別是考慮的時間尺度不同，理論上均稱調度問題；生產調度是生產計劃的可行性驗證過程,生產計劃側重于經營計劃和生產能力的平衡，考慮的時間以月或年計的中長期粗,生產調度則

2、在較短的時間內進行，最主要的任務是生產作業(yè)的安排與資源的具體分配，涉及實際生產環(huán)境的各種約束細,02.01.2021,生產調度,生產調度與生產計劃,生產計劃的制定以企業(yè)的利潤最大化為目標，而生產調度則以生產過程的平穩(wěn)過渡/順暢接續(xù)為目標,生產計劃的制定，一般是考慮靜態(tài)情況。當生產因素比較穩(wěn)定和比較理想時才能達到優(yōu)化的預期目標,生產過程是動態(tài)的，要求生產調度系統(tǒng)有一定的柔性，能適應生產過程中內、外因素的異動，以便準確而靈活地完成生產計劃；生產調度側重于生產裝置的分配利用和物料平衡,02.01.2021,生產調度,生產計劃優(yōu)化系統(tǒng),優(yōu)化系統(tǒng)可根據企業(yè)的產、供、銷狀況，以企業(yè)綜合效益為目標，建立合適

3、的數學模型，依一定方法求解，分別考慮企業(yè)內外約束，進而獲得最優(yōu)計劃；計劃的實施，必須充分利用現有資源，優(yōu)化資源配置，提高生產決策的科學性，實現效益的最大化,02.01.2021,生產調度,生產調度系統(tǒng)的功能,計劃的分解：一般采用時間分配方法，即滾動計劃,動態(tài)監(jiān)控：實時監(jiān)控，包括數據的采集、關鍵參數的歷史趨勢圖分析、圖表及工藝流程的顯示。平衡協調，包括外部的生產和經營兩大系統(tǒng)產供銷，內部生產過程人員工位器具等,02.01.2021,生產調度,生產調度系統(tǒng)的特點,復雜性； 隨機性； 多約束； 多目標,Q: 維修作業(yè)調度 系統(tǒng)特點的表達,02.01.2021,生產調度,生產調度問題的一般描述,語義描

4、述：目標-任務集合-資源集合-約束條件； 數學描述調度問題的數學符號表達,生產調度問題的性能指標,能力指標：最大生產率、最短生產周期等； 成本指標：最大利潤、最小費用等； 客戶滿意度指標：最短交付期（提前拖期懲罰）等,02.01.2021,生產調度,生產調度問題的分類,依模型變量分類：1）連續(xù)變量問題；2）離散變量問題/組和優(yōu)化問題（combinatorial optimization problem: COP） 依生產過程輸出：1）連續(xù)生產過程（連續(xù)的產品流）；2）間隙生產過程（離散批量）/批處理過程批處理調度問題；3）離散生產過程（離散數量）車間調度問題 按調度目標：總的作業(yè)時間最短、總的

5、延遲時間最小等 其他：依人物特點：可否終端、加工時限、順序約束等,02.01.2021,生產調度問題的分類,車間調度問題,車間 調度,加工設備的分配,工件的加工時間與加工順序,實質,生產調度,02.01.2021,生產調度問題的分類,流水車間調度問題,分類（基于加工時間或交付期）：確定型、隨機型和模糊型/滿意型,生產調度,02.01.2021,NP難題 工程近似 可用解,生產調度,生產調度問題的分類,作業(yè)車間調度問題,JSP問題可以采用整數線性規(guī)劃模型描述。前提假設：所有的任務在零時刻都可用，且無設備故障，任務在機器上執(zhí)行時間事先已知,02.01.2021,生產調度,生產調度問題的分類,間隙生

6、產調度問題,分類：多產品（multi-product）間隙生產過程所有產品生產順序相同，加工路徑相同，整個生產過程分成若干個生產階段，每個階段包含若干并行設備。類似Flow-shop和多用途或多目的（multi-purpose）間隙生產過程可以是不同的生產線、不同的路徑、不同的工序，可通過設備的組織來調整。類似Job-shop,排序的 問題,中間產品 存儲策略,等待時間 切換時間,上層組織路經與時間分配 下層設備與資源分配決策,02.01.2021,生產調度,生產調度問題的分類,動態(tài)調度問題,靜態(tài)調度：調度環(huán)境和任務已知的前提下的所謂的事前調度方法例行維修作業(yè),動態(tài)調度：也稱再調度，指在調度環(huán)

7、境和任務存在不可預見的擾動情況下的調度方案，即依賴于事前調度環(huán)境和任務也與當前狀態(tài)有關例行+非例行維修作業(yè),為適應生產過程的不確定性和隨機性，一般采用周期性調度和再調度相結合的策略,02.01.2021,生產調度,生產調度問題的分類,動態(tài)調度問題（續(xù),動態(tài)調度形式：滾動調度（rolling scheduling）和被動調度（reactive scheduling,被動調度目標是盡可能維持原靜態(tài)調度水平，既保持原有的性能指標,滾動調度：移動時間段內的生產調度； 被動調度：隨生產過程變化而不可行的調度的修正,動態(tài)調度的 實時性要求,Q：變化（加工時間、任務、設備故障等）調機作業(yè),02.01.202

8、1,生產調度,生產調度方法,分類：優(yōu)化調度方法和啟發(fā)式調度方法,優(yōu)化調度：精確求解解析模型而獲得最優(yōu)解、近似求解得次優(yōu)解；基礎：數學規(guī)劃；適用：小規(guī)模優(yōu)化問題,啟發(fā)式調度：包括基于規(guī)則的方法、基于人工智能的方法、隨機搜索方法、基于仿真的方法等，立足當前，追求局部最優(yōu)而非全局最優(yōu),方向：二者結合,啟發(fā)推理,02.01.2021,生產調度,生產調度方法（續(xù),Model-based and model-free,02.01.2021,生產調度的啟發(fā)式算法,啟發(fā)式算法（heuristics algorithm,語義性描述：一個基于直觀或者經驗構造的算法，在可接受的代價下，給出待解決組合優(yōu)化問題的一個可

9、行解,未定義可行解與最優(yōu)解的距離,02.01.2021,生產調度的啟發(fā)式算法,啟發(fā)式算法（heuristics algorithm,Johnson問題：以最大流程時間為目標的兩臺機器流水車間調度問題依Johnson規(guī)則確定其最優(yōu)調度,問題描述：n 個工件在機器1和機器2上的加工時間分別為ti1和ti2 ，目標是給出最短生產周期的產品序列,02.01.2021,生產調度的啟發(fā)式算法,啟發(fā)式算法（heuristics algorithm,基于Johnson規(guī)則構造最優(yōu)調度，步驟如下,02.01.2021,生產調度的啟發(fā)式算法,啟發(fā)式算法（heuristics algorithm,例,問題的關鍵是啟

10、發(fā)式規(guī)則的建立,啟發(fā)式算法通常是以犧牲計算時間為代價,02.01.2021,生產調度的啟發(fā)式算法,啟發(fā)式算法（heuristics algorithm,常用啟發(fā)式規(guī)則： 用優(yōu)先分配規(guī)則來解決工序中可能的加工沖突（要求算法有識別所有加工沖突的能力） 基于隨機分配規(guī)則的啟發(fā)式算法：每一工序都對應啟發(fā)式規(guī)則集/族中的任意規(guī)則，規(guī)則可重用，全部工序遍歷一遍后即可找到生產活動調度工序順序集,02.01.2021,遺傳算法,遺傳算法：借鑒生物界自然選擇和自然遺傳機制的隨機算法,原理：始于多個初始解，然后通過一定規(guī)則進行逐步迭代產生新的解，合成解集，通過對解集中解的性質的判斷，篩出需要的解,02.01.20

11、21,遺傳算法,遺傳算法：借鑒生物界自然選擇和自然遺傳機制的隨機算法,算法設計的內容： 編碼解空間 適應度函數解的質量的度量/目標函數 選擇策略大適值解對應大存活概率/機會 控制參數種群規(guī)模、算法代數/終止準則、遺傳操作概率等 遺傳算子選擇/遺傳、交叉、變異,缺點：沒有利用目標函數梯度等信息，造成了解的無方向性,02.01.2021,基于遺傳算法的車間調度問題,遺傳算法：把調度問題參數表達成按一定結構組成的染色體編碼,部分算法設計內容： 編碼工件加工順序 適應度函數完成加工作業(yè)可能的最大流程時間的倒數（流程時間越短越好） 選擇策略大適值解對應大存活概率/機會 控制參數種群規(guī)模、算法代數/終止準則、遺傳操作概率等 遺傳算子選擇/遺傳、交叉、變異,02.01.2021,基于遺傳算法的模糊車間調度方法,主要解決提前/拖期費用調度問題利用模糊量表示客戶對交貨期的滿意程度,Q：航班延誤問題 A1：可用隨機規(guī)則調度法 A2：也可用模糊調度法,02.01.2021,基于同一時間離散化生產調度,把調度范圍分成許許多多等長度的時間段民航維修作業(yè)標準工時下的派工問題，然后明確約束條件（分配約束、容量約束、物料平衡、公共及人力資源限制），最終可表達為以利潤最大為目標函數的調度問題,一個經典的調度問題,02.01.2021,不確定性生產調度問題,生產