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