生產(chǎn)調(diào)度及智能優(yōu)化（課堂PPT）

1、3/23/20221生產(chǎn)調(diào)度及智能優(yōu)化 陳靜杰博士教授航空自動化學(xué)院航空電子系中國民航大學(xué)數(shù)據(jù)分析研究所24092499（O）/ 136520379393/23/20222生產(chǎn)調(diào)度生產(chǎn)調(diào)度與運籌學(xué)3/23/20223生產(chǎn)調(diào)度什么是生產(chǎn)調(diào)度？即按時間分配資源完成任務(wù)/作業(yè)的過程或方法。要求：任務(wù)/作業(yè)必須是可分割的。生產(chǎn)調(diào)度問題生產(chǎn)調(diào)度問題Q：現(xiàn)場有哪些？：現(xiàn)場有哪些？3/23/20224生產(chǎn)調(diào)度生產(chǎn)調(diào)度與生產(chǎn)計劃都是對生產(chǎn)過程的規(guī)劃與控制（均考慮優(yōu)化的目的），主要區(qū)別是考慮的時間尺度不同，理論上均稱調(diào)度問題；生產(chǎn)調(diào)度是生產(chǎn)計劃的可行性驗證過程生產(chǎn)計劃側(cè)重于經(jīng)營計劃和生產(chǎn)能力的平衡，考慮的時間以

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

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

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

5、總的作業(yè)時間最短、總的延遲時間最小等其他：依人物特點：可否終端、加工時限、順序約束等3/23/202211生產(chǎn)調(diào)度問題的分類車間調(diào)度問題：束考慮工序的先后順序約時需個工件的某道工序，同在任一時刻只能加工某道工序，每一臺機器臺機器上加工需個工件在kmn車間調(diào)度加工設(shè)備的分配工件的加工時間與加工順序?qū)嵸|(zhì)生產(chǎn)調(diào)度3/23/202212生產(chǎn)調(diào)度問題的分類小序，使最大流程時間最是求工件的最優(yōu)加工順是給定的，目標(biāo)工時間上的加在機器，工件臺機器上加工順序相同在個工件個工件的某道工序，在任一時刻只能加工某道工序，每一臺機器臺機器上加工需個工件在mjnitjimnkmnij,2, 1;,2, 1流水車間調(diào)度問題

6、：max/cFmn 簡記：分類（基于加工時間或交付期）：確定型、隨機型和模糊型分類（基于加工時間或交付期）：確定型、隨機型和模糊型/滿意型滿意型生產(chǎn)調(diào)度3/23/202213NP難題工程近似可用解生產(chǎn)調(diào)度生產(chǎn)調(diào)度問題的分類作業(yè)車間調(diào)度問題：行有效的排序。度的調(diào)度，即對作業(yè)進目標(biāo)是找到最小時間長束考慮工序的先后順序約時需個工件的某道工序，同在人一時刻只能加工某道工序，每一臺機器臺機器上加工需個工件在，kmnJSP問題可以采用整數(shù)線性規(guī)劃模型描述。前問題可以采用整數(shù)線性規(guī)劃模型描述。前提假設(shè)：所有的任務(wù)在零時刻都可用，且無提假設(shè)：所有的任務(wù)在零時刻都可用，且無設(shè)備故障，任務(wù)在機器上執(zhí)行時間事先已知

7、設(shè)備故障，任務(wù)在機器上執(zhí)行時間事先已知JSPproblemschedulingshopjob:3/23/202214生產(chǎn)調(diào)度生產(chǎn)調(diào)度問題的分類間隙生產(chǎn)調(diào)度問題：分類：多產(chǎn)品（分類：多產(chǎn)品（multi-product）間隙生產(chǎn)過程）間隙生產(chǎn)過程所有所有產(chǎn)品生產(chǎn)順序相同，加工路徑相同，整個生產(chǎn)過程分產(chǎn)品生產(chǎn)順序相同，加工路徑相同，整個生產(chǎn)過程分成若干個生產(chǎn)階段，每個階段包含若干并行設(shè)備。類成若干個生產(chǎn)階段，每個階段包含若干并行設(shè)備。類似似Flow-shop和多用途或多目的（和多用途或多目的（multi-purpose）間隙生產(chǎn)過程間隙生產(chǎn)過程可以是不同的生產(chǎn)線、不同的路徑、不可以是不同的生產(chǎn)線、不

8、同的路徑、不同的工序，可通過設(shè)備的組織來調(diào)整。類似同的工序，可通過設(shè)備的組織來調(diào)整。類似Job-shop排序的排序的問題問題中間產(chǎn)品中間產(chǎn)品存儲策略存儲策略等待時間等待時間切換時間切換時間上層組織路經(jīng)與時間分配上層組織路經(jīng)與時間分配下層設(shè)備與資源分配決策下層設(shè)備與資源分配決策3/23/202215生產(chǎn)調(diào)度生產(chǎn)調(diào)度問題的分類動態(tài)調(diào)度問題：靜態(tài)調(diào)度：調(diào)度環(huán)境和任務(wù)已知的前提下的所謂的事前調(diào)度方法例行維修作業(yè)例行維修作業(yè)動態(tài)調(diào)度：也稱再調(diào)度，指在調(diào)度環(huán)境和任務(wù)存在不可預(yù)見的擾動情況下的調(diào)度方案，即依賴于事前調(diào)度環(huán)境和任務(wù)也與當(dāng)前狀態(tài)有關(guān)例行例行+非例行維修作業(yè)非例行維修作業(yè)為適應(yīng)生產(chǎn)過程的不確定性和

9、隨機性，一為適應(yīng)生產(chǎn)過程的不確定性和隨機性，一般采用周期性調(diào)度和再調(diào)度相結(jié)合的策略般采用周期性調(diào)度和再調(diào)度相結(jié)合的策略3/23/202216生產(chǎn)調(diào)度生產(chǎn)調(diào)度問題的分類動態(tài)調(diào)度問題（續(xù)）：動態(tài)調(diào)度形式：滾動調(diào)度（rolling scheduling）和被動調(diào)度（reactive scheduling）被動調(diào)度目標(biāo)是盡可能被動調(diào)度目標(biāo)是盡可能維持原靜態(tài)調(diào)度水平，維持原靜態(tài)調(diào)度水平，既保持原有的性能指標(biāo)既保持原有的性能指標(biāo)滾動調(diào)度：移動時間段內(nèi)的生產(chǎn)調(diào)度；滾動調(diào)度：移動時間段內(nèi)的生產(chǎn)調(diào)度；被動調(diào)度：隨生產(chǎn)過程變化而不可行的調(diào)度的修正被動調(diào)度：隨生產(chǎn)過程變化而不可行的調(diào)度的修正動態(tài)調(diào)度的動態(tài)調(diào)度的實時

10、性要求實時性要求Q：變化（加工時間、：變化（加工時間、任務(wù)、設(shè)備故障任務(wù)、設(shè)備故障等）等）調(diào)機作業(yè)調(diào)機作業(yè)3/23/202217生產(chǎn)調(diào)度生產(chǎn)調(diào)度方法分類：優(yōu)化調(diào)度方法和啟發(fā)式調(diào)度方法優(yōu)化調(diào)度：精確求解解析模型而獲得最優(yōu)解、近似求解得次優(yōu)解；基礎(chǔ)：數(shù)學(xué)規(guī)劃；適用：小規(guī)模優(yōu)化問題啟發(fā)式調(diào)度：包括基于規(guī)則的方法、基于人工智能的方法、隨機搜索方法、基于仿真的方法等，立足當(dāng)前，追求局部最優(yōu)而非全局最優(yōu)方向：二者結(jié)合方向：二者結(jié)合啟發(fā)推理啟發(fā)推理3/23/202218生產(chǎn)調(diào)度生產(chǎn)調(diào)度方法（續(xù)）數(shù)學(xué)規(guī)劃數(shù)學(xué)規(guī)劃等式與等式與不不等式約等式約束束分支定界法分支定界法Lagrangian松弛法松弛法貝葉斯啟發(fā)方法

11、貝葉斯啟發(fā)方法規(guī)則調(diào)規(guī)則調(diào)度方法度方法簡單規(guī)則簡單規(guī)則復(fù)合規(guī)則復(fù)合規(guī)則啟發(fā)式規(guī)則啟發(fā)式規(guī)則動態(tài)調(diào)度動態(tài)調(diào)度依靠機器學(xué)習(xí)的依靠機器學(xué)習(xí)的動態(tài)選擇規(guī)則動態(tài)選擇規(guī)則利用神經(jīng)網(wǎng)絡(luò)實利用神經(jīng)網(wǎng)絡(luò)實現(xiàn)智能選擇規(guī)則現(xiàn)智能選擇規(guī)則基于人工基于人工智能方法智能方法啟發(fā)式啟發(fā)式搜索規(guī)則搜索規(guī)則基于規(guī)則與基于規(guī)則與知識的方法知識的方法智能求智能求解方法解方法ANNsGAFuzzy SetsModel-based and model-free3/23/202219生產(chǎn)調(diào)度的啟發(fā)式算法啟發(fā)式算法（heuristics algorithm）語義性描述：一個基于直觀或者經(jīng)驗構(gòu)造的算法，在語義性描述：一個基于直觀或者經(jīng)驗構(gòu)造

12、的算法，在可接受的代價下，給出待解決組合優(yōu)化問題的一個可可接受的代價下，給出待解決組合優(yōu)化問題的一個可行解行解未定義可行解與未定義可行解與最優(yōu)解的距離最優(yōu)解的距離3/23/202220生產(chǎn)調(diào)度的啟發(fā)式算法啟發(fā)式算法（heuristics algorithm）Johnson問題：以最大流程時間為目標(biāo)的兩臺機器流問題：以最大流程時間為目標(biāo)的兩臺機器流水車間調(diào)度問題水車間調(diào)度問題依依Johnson規(guī)則確定其最優(yōu)調(diào)度規(guī)則確定其最優(yōu)調(diào)度問題描述：問題描述：n 個工件在機器個工件在機器1和機器和機器2上的加工時間分上的加工時間分別為別為ti1和和ti2 ，目標(biāo)是給出最短生產(chǎn)周期的產(chǎn)品序列，目標(biāo)是給出最短生

13、產(chǎn)周期的產(chǎn)品序列ni,2, 1前在，則工件規(guī)則：jittttiiii1221,min,minJohnson2121,iiiitttt3/23/202221生產(chǎn)調(diào)度的啟發(fā)式算法啟發(fā)式算法（heuristics algorithm）基于基于Johnson規(guī)則構(gòu)造最優(yōu)調(diào)度，步驟如下：規(guī)則構(gòu)造最優(yōu)調(diào)度，步驟如下：組；余的工件歸，其在機器1上加工時間長組的工件在機器2上比兩組，分組的原則是：和個工件分成步驟1：將QPQPN間地間順序排列組工件按機器2加工時間遞增順序排列，組工件按機器1加工時步驟2：QP最優(yōu)工件順序便構(gòu)成生產(chǎn)周期最短的，組工件順序連接在一起組工件順序和步驟3：將QP3/23/202222

14、生產(chǎn)調(diào)度的啟發(fā)式算法啟發(fā)式算法（heuristics algorithm）例：例：3,16,5,4,2QP 步驟1：、1,36,5,2,4:QP、排序-步驟2周期是37最短生產(chǎn)是步驟3：最優(yōu)加工順序，136524工件123456機器1上加工時間10511379機器2上加工時間47981015問題的關(guān)鍵問題的關(guān)鍵是啟發(fā)式規(guī)是啟發(fā)式規(guī)則的建立則的建立啟發(fā)式算法啟發(fā)式算法通常是以犧通常是以犧牲計算時間牲計算時間為代價為代價3/23/202223生產(chǎn)調(diào)度的啟發(fā)式算法啟發(fā)式算法（heuristics algorithm）常用啟發(fā)式規(guī)則：常用啟發(fā)式規(guī)則： 用優(yōu)先分配規(guī)則來解決工序中可能的加工沖用優(yōu)先分配規(guī)

15、則來解決工序中可能的加工沖突（要求算法有識別所有加工沖突的能力）突（要求算法有識別所有加工沖突的能力）1.基于隨機分配規(guī)則的啟發(fā)式算法：每一工序基于隨機分配規(guī)則的啟發(fā)式算法：每一工序都對應(yīng)啟發(fā)式規(guī)則集都對應(yīng)啟發(fā)式規(guī)則集/族中的任意規(guī)則，規(guī)則族中的任意規(guī)則，規(guī)則可重用，全部工序遍歷一遍后即可找到生產(chǎn)可重用，全部工序遍歷一遍后即可找到生產(chǎn)活動調(diào)度活動調(diào)度工序順序集工序順序集3/23/202224遺傳算法遺傳算法：借鑒生物界自然選擇和自然遺傳機制的隨機算法p原理：始于多個初始解，然后通過一定規(guī)則原理：始于多個初始解，然后通過一定規(guī)則進行逐步迭代產(chǎn)生新的解，合成解集，通過進行逐步迭代產(chǎn)生新的解，合成解

16、集，通過對解集中解的性質(zhì)的判斷，篩出需要的解對解集中解的性質(zhì)的判斷，篩出需要的解3/23/202225遺傳算法遺傳算法：借鑒生物界自然選擇和自然遺傳機制的隨機算法p算法設(shè)計的內(nèi)容：算法設(shè)計的內(nèi)容：l 編碼解空間l 適應(yīng)度函數(shù)解的質(zhì)量的度量/目標(biāo)函數(shù)l 選擇策略大適值解對應(yīng)大存活概率/機會l 控制參數(shù)種群規(guī)模、算法代數(shù)/終止準(zhǔn)則、遺傳操作概率等l 遺傳算子選擇/遺傳、交叉、變異缺點：沒有利缺點：沒有利用目標(biāo)函數(shù)梯用目標(biāo)函數(shù)梯度等信息，造度等信息，造成了解的無方成了解的無方向性向性3/23/202226基于遺傳算法的車間調(diào)度問題遺傳算法：把調(diào)度問題參數(shù)表達成按一定結(jié)構(gòu)組成的染色體編碼p部分算法設(shè)計

17、內(nèi)容：部分算法設(shè)計內(nèi)容：l 編碼工件加工順序l 適應(yīng)度函數(shù)完成加工作業(yè)可能的最大流程時間的倒數(shù)（流程時間越短越好）l 選擇策略大適值解對應(yīng)大存活概率/機會l 控制參數(shù)種群規(guī)模、算法代數(shù)/終止準(zhǔn)則、遺傳操作概率等l 遺傳算子選擇/遺傳、交叉、變異3/23/202227基于遺傳算法的模糊車間調(diào)度方法主要解決提前/拖期費用調(diào)度問題利用模糊量表示客戶對交貨期的滿意程度Q：航班延誤問題：航班延誤問題A1：可用隨機規(guī)則調(diào)度法：可用隨機規(guī)則調(diào)度法A2：也可用模糊調(diào)度法：也可用模糊調(diào)度法3/23/202228基于同一時間離散化生產(chǎn)調(diào)度把調(diào)度范圍分成許許多多等長度的時間段民航維修作業(yè)標(biāo)準(zhǔn)工時下的派工問題，然后明確約束條件（分配約束、容