【正文】 生產計劃與調度 Production Planning and Scheduling 浙江大學系統工程研究所 OUTLINE－ Production Scheduling 1. 離散制造過程 (APS) 2. 流程工業(yè)（間歇與連續(xù)） 3. 生產調度數學模型 4. 調度問題 優(yōu)化方法 5. 智能調度方法 離散制造過程生產調度 生產控制的主要內容是作業(yè)計劃與動態(tài)調整，它稱為車間調度問題。包括兩個方面： ? 其一為靜態(tài)調度，產生一個初始調度； ? 其二為意外事件發(fā)生后，進行調度的修改與調整即動態(tài)調度。 ? MRP II內主要采用啟發(fā)式規(guī)則進行作業(yè)調度與優(yōu)先級控制，提供一個建議的作業(yè)計劃，在訂單下達時，包括開工日期與完工日期，但已考慮了時間余量，因此，車間調度有一定的緩沖余地。 ? 執(zhí)行中的意外即動態(tài)調度可由車間進行有限的局部調度，但當其影響到生產計劃時，只能反饋至計劃部門，由計劃部門統一調整。 車間作業(yè)調度的特點 ? 離散制造過程中，工件生產時間較短，工件切換加工成本低但庫存成本很高。 ? 主要解決多個產品對設備的爭用問題。 ? 目的在于尋找最優(yōu)的設備加工任務次序，使得等待時間與切換時間最小。 (1) 單機調度問題 (2) 并行機調度問題 (3) Jobshop調度問題 (4) Flowshop調度問題 (5) Openshop調度問題 給定一個工件的集合 P和一個機器的集合 M 每個工件包括多道工序 Ji={Pi1 ….. Pik} 每臺設備可以多個加工任務 JMi={J(1) ….. J(li) } 約束： ? 順序約束：同一個產品的有序工序對必須在前一工序完成后才能開始 ? 占用約束：每臺機床同一時間只能加工一個產品的某個工序， 每道工序需要在一臺給定的機器上非間斷地加工一段時間 Jobshop問題 決策：工序分配給機器上某個時間段 目標：總加工時間最短的調度 ijkJijkSijkT Jobshop問題 A設備 B設備 C設備 D設備 任務 1 任務 n JSP是一類滿足任務配置和順序約束要求的資源分配問題，是最困難的組合優(yōu)化問題之一。 生產的柔性： ? 設備使用的柔性 ? 設備安排的柔性 調度決策內容包括： ? 分配決策 (工件的加工次序 ) ? 時間決策 (工件的各工序的加工時間 ) ? 路徑決策 (工件的工序的設備分配 ) Flowshop調度問題 n個工件在 m臺機器上加工，一個工件分為 n道工序，每道工序要求不同的機器加工。 n個工件在 m臺機器上的加工順序相同，工件在機器上的加工時間是給定。 問題目標：求個工件在機器上最優(yōu)的加工順序，使最大流程時間最小。 M1 M2 M3 M4 P1 P2 設備 產品 流水車間調度問題，常用 表示，即個 n工件 /m臺機器 /流水車間 /最大流程時間 。 m a x/// cFmn Flowshop問題示例 假設有 A、 B、 C、 D四種零件，都需要進行先車后銑，其加工時間如表所示。 零件名稱 車床工時（時） 銑床工時（時） A 15 4 B 8 10 C 6 5 D 12 7 合計 41 26 ( D , 1 , 1 )( C , 1 , 1 )( A , 1 , 1 ) ( B , 1 , 1 )0 15 23 41( D , 2 , 2 )( C , 2 , 2 )( A , 2 , 2 )0 19 3833( B , 2 , 2 )15 23 4829M1（ 車床）M2（銑床）甘特圖 調度結果甘特圖 (A,1,1) (C,1,1) B,1,1) (D,1,1) 0 8 20 41 (D,2,2) (C,2,2) (A,2,2) 0 20 41 32 (B,2,2) 18 27 45 26 M1 （ 車床 ） M2 （ 銑床 ） 優(yōu)化調度結果： 調度問題不同特點 Flowshop 問題中各個產品的生產路徑相同，產品加工工序的順序與設備的順序對應，因而某個設備的加工任務順序就表示產品的加工順序。 Jobshop問題 中各個產品的加工路線并不相同，設備上加工任務與總的加工任務矩陣無對應關系，即使產品數量與設備數量確定，也不能確定所有的加工任務，存在路徑選擇問題。 對于 Flowshop，若給定某一個產品生產次序，則可以計算出所有工序的完成時間以及等待時間，而對于 Jobshop，由于它存在路徑選擇問題，即使給定產品生產次序，也無法計算。 實際調度問題 ? “ 因為瓶頸工序在不斷變化 ， 我們如何知道瓶頸在那里 ？ ” ? “ 能否自動分配工序 ？ 自動調配人力 ， 設備能力 ？ ” ? “ 在插入急單時 ， 能否自動根據目標重排計劃 ， 一些定單自動延遲 ， 一些定單自動提前 ？ ” ? “ 能否對采購延遲 ， 生產的延遲 ， 設備的故障 ， 人員的效率等意外快速響應 ， 及自動進行模擬 ， 調整 ？ ” ERP作業(yè)計劃 ERP(MRPII)制定作業(yè)計劃的方法一般包括以下幾個步驟： 確定批量； 計算提前期； 安排優(yōu)先權，安排作業(yè)計劃； 根據能力限制調整作業(yè)計劃，再重復前三個步驟。 按預先制定的提前期，用無限能力計劃法編制作業(yè)計劃。 APS先進計劃調度 ? 基于約束理論 ? 能夠處理生產類型和工序約束 ? 自動的 ， 可視化的作業(yè)計劃 TOC約束理論一 ? “約束資源”， “瓶頸” ? 約束資源決定企業(yè)有效產出與庫存 企業(yè)有效產出受到企業(yè)的生產能力和市場的需求量的制約 ? “非約束”應與“約束”同步 庫存水平只要能維持“約束”上的物流連續(xù)穩(wěn)定即可 ? “非約束”的利用程度不由其本身決定，而是由系統的“約束”決定的。 ? “約束”上一個小時的損失則是整個系統的一個小時的損失。 ? “非約束”節(jié)省的一個小時無益于增加系統有效產出 。 APS約束類型 ?資源約束 a，單一資源 b，無限資源 c，并發(fā)資源 d，共享資源 e，可調整共享資源 ?順序約束 ?庫存約束 ?特別約束 APS計劃算法一 ?有限能力計劃 a，算法順序計劃 b，向前順序計劃 c，向后順序計劃 b，雙向計劃或瓶頸計劃 ?基于模擬的計劃 基于模擬規(guī)則產生一個優(yōu)化的計劃 APS計劃算法二 ? 向前順序計劃固定了開始時間 ， 決定結束時間 ， 也許會違反完成日期 。 向后順序計劃固定結束時間 ， 決定開始時間 ， 產生一個不會延遲的計劃 ， 然而 ， 計劃也許有不可行的開始時間 。 ? 雙向計劃或瓶頸計劃 ， 先安排約束資源上加工的關鍵件的生產進度計劃 ， 以約束資源為基準 ， 把約束資源之前 、 之間 、 之后的工序分別按拉動 、 工藝順序 、 推動的方式排定 ， 并進行一定優(yōu)化 ， 接下來編制非關鍵件的作業(yè)計劃 。 特點： 與 ERP不同，瓶頸算法順序計劃中的提前期是批量、優(yōu)先權和其它許多因素的函數，是編制作業(yè)計劃產生的結果。 啟發(fā)式規(guī)則 ? 主要的優(yōu)點是啟發(fā)式規(guī)則往往利用與該問題相關的知識，因此，在通常情況下能夠在較短的時間內得到較好方案。 ? 啟發(fā)式規(guī)則無法分析與判斷其方案的質量。 APS中的啟發(fā)式規(guī)則 預先確定任務的參數類規(guī)則 如升序定單屬性值 ， 優(yōu)先級 、 反向優(yōu)先級 最小化任務延遲類規(guī)則 如先到先服務 最小化任務流程時間類規(guī)則 適用于最小時間的控制 ， 提高工時利用率 。 如完成日期 最大設備能力類規(guī)則 適用于是計劃設備效率來最大化整個設備的生產能力 。 如閑散時間 定制規(guī)則 流程工業(yè)調度特點 ? 產品配方 、 產品混合 、 物料平衡等問題 ? 需要考慮主產品 、 副產品 、 協產品 、 半成品 ? 循環(huán)和回流 ? 熱蒸汽 、 冷凍水 、 壓縮空氣 、 水 、 電等動力能源輔助系統也應納入調度 生產調度 流程工業(yè)中生產過程的柔性是靠改變各裝置間的物流分配和生產裝置的工作點來實現的，必須由先進的在線優(yōu)化、控制技術來保證。 ? 靜態(tài)調度：它考慮工廠生產資源優(yōu)化分配，屬于在確定性環(huán)境下靜態(tài)組合優(yōu)化問題； ? 動態(tài)調度：它是在生產過程出現各種動態(tài)變化因素時進行的再調度。 靜態(tài)調度 ? 主要的決策變量為：各個操作的開始時間 ， 持續(xù)時間 、 執(zhí)行的單元設備 ， 以及容量 。 ? 調度期變化范圍為 2－ 3天至 2－ 6月 。 受到單元設備的操作周期 、 產品的生產周期以及原料準備所需的時間影響 。 聯系： ? 產品生產率和產品質量指標直接由調度下達至先進控制。 ? 先進控制將生產過程的狀態(tài)、過程模型的參數的更新反饋至生產調度。 動態(tài)調度 ? 動態(tài)調度又稱再調度：處理突發(fā)事件，如某項生產控制指標超出臨界值，設備的故障、資源突然短缺以及能源供應中斷等。它在生產過程中出現的意外事件進行，保證生產的平穩(wěn)進行。 ? 動態(tài)調度依據生產計劃和實際工況響應進行調度，與靜態(tài)調度不同，需要考慮實時性。 ? 動態(tài)生產調度對生產運行控制的性能具有重大影響，但大規(guī)模的具有工業(yè)意義的動態(tài)生產調度問題由于其復雜性，單純依靠人（即使是有經驗的生產調度人員）來解決已被實踐經驗證明是不現實的。 最優(yōu)調度問題描述 給定： 生產過程的工藝 、 設備及全部相關信息； 一個感興趣的時間段； 用戶定單及原料到貨信息或生產計劃信息 決定： 每個設備單元的操作時間 （ 例如 ， 在感興趣的時間段內設備在每個時刻執(zhí)行哪個任務 ） ；工廠的物料流 。 使得： 目標函數最優(yōu) 。 生產過程的約束 約束條件： 生產調度受到諸多因素的限制 ， 一般有：產品的投產期 ， 交貨期 （ 完成期 ） ， 生產能力 ， 加工順序 ， 加工設備和原料的可用性 ， 批量大小 ，加工路徑 ， 成本限制等 ， 這些都是所謂的約束條件 。 硬約束與軟約束： 硬約束是必須要滿足的 ， 如交貨期 ， 生產能力等 ， 而軟約束只需達到一定的滿意度即可 ， 如生產成本等 。 這些約束一般情況是確定的 ， 在進行調度時大都作為確定性因素考慮 。 不確定性因素： 設備故障 ， 原料供應變化 ， 生產任務變化等非正常情況 ， 都是事先不能預見的 ， 大都作為不確定性因素考慮 。 Scheduling model Constraints ? Time relations start(A)+p(A)=end(A) sequencing BA end(B)≤start(A) ? Resource capacity constraints unary resource (activities cannot overlap) AB ∨ BA end(A)≤start(B) ∨ end(B)≤start(A) B A 優(yōu)化目標 生產調度的性能指標可以是成本最低、庫存費用最少（減少流動資金占用）、生產周期最短、生產切換最少、設備利用率最高、三廢最少等。生產調度的性能指標大致可以歸結為三類： ? 最大能力指標 ? 成本指標 ? 客戶滿意度指標 間歇型生產過程調度 ? 間歇型生產過程適用于中小批量且產出價值較高的產品。 一般是由一些通用型的設備組成，通過對設備、原材料等資源的共享，在同一組設備上實現多種產品的生產，并且可以實現較為復雜的合成過程。 ? 間歇型生產過程的靈活性，對生產調度提出了更高的要求。 由于設備可由多項流程共享，工藝描述與設備描述是不同且獨立的，在設備管理的同時還亟需工藝管理。為了在特定的時間段上將設備分配給特定的工藝流程，調度成為最重要的功能。 中間貯罐協調工序間差異 中間貯罐： 某些需要較長加工時間的工序成為生產過程的瓶頸，它屬于時間瓶頸。為解決瓶頸問題，往往在工序間加入中間貯罐，使得上、下游的物料流分離，協調工序間生產能力、加工時間差異。 中間貯罐并不能夠完全地解決時間與能力瓶頸。 由于中間產品往往具有不穩(wěn)定的特點，它在加工完成后，必須立即由下一道工序加工，而不允許等待。導致了工序間存在大量的空閑時間，降低了設備