生產(chǎn)計(jì)劃與調(diào)度培訓(xùn)課程

1、生產(chǎn)計(jì)劃與調(diào)度生產(chǎn)計(jì)劃與調(diào)度Production Planning and Scheduling浙江大學(xué)系統(tǒng)工程研究所浙江大學(xué)系統(tǒng)工程研究所OUTLINEProduction Scheduling1. 離散制造過(guò)程離散制造過(guò)程(APS)2. 流程工業(yè)（間歇與連續(xù)）流程工業(yè)（間歇與連續(xù)）3. 生產(chǎn)調(diào)度數(shù)學(xué)模型生產(chǎn)調(diào)度數(shù)學(xué)模型4. 調(diào)度問(wèn)題調(diào)度問(wèn)題優(yōu)化方法優(yōu)化方法5. 智能調(diào)度方法智能調(diào)度方法離散制造過(guò)程生產(chǎn)調(diào)度離散制造過(guò)程生產(chǎn)調(diào)度生產(chǎn)控制的主要內(nèi)容是作業(yè)計(jì)劃與動(dòng)態(tài)調(diào)整，它稱為車間調(diào)度問(wèn)題。包括兩個(gè)方面：n其一為靜態(tài)調(diào)度，產(chǎn)生一個(gè)初始調(diào)度；n其二為意外事件發(fā)生后，進(jìn)行調(diào)度的修改與調(diào)整即動(dòng)態(tài)調(diào)度。

2、nMRP II內(nèi)主要采用啟發(fā)式規(guī)則進(jìn)行作業(yè)調(diào)度與優(yōu)先級(jí)控制，提供一個(gè)建議的作業(yè)計(jì)劃，在訂單下達(dá)時(shí)，包括開(kāi)工日期與完工日期，但已考慮了時(shí)間余量，因此，車間調(diào)度有一定的緩沖余地。n執(zhí)行中的意外即動(dòng)態(tài)調(diào)度可由車間進(jìn)行有限的局部調(diào)度，但當(dāng)其影響到生產(chǎn)計(jì)劃時(shí)，只能反饋至計(jì)劃部門(mén)，由計(jì)劃部門(mén)統(tǒng)一調(diào)整。 車間作業(yè)調(diào)度的特點(diǎn)車間作業(yè)調(diào)度的特點(diǎn)n離散制造過(guò)程中，工件生產(chǎn)時(shí)間較短，工件切換加工成本離散制造過(guò)程中，工件生產(chǎn)時(shí)間較短，工件切換加工成本低但庫(kù)存成本很高。低但庫(kù)存成本很高。 n主要解決多個(gè)產(chǎn)品對(duì)設(shè)備的爭(zhēng)用問(wèn)題。主要解決多個(gè)產(chǎn)品對(duì)設(shè)備的爭(zhēng)用問(wèn)題。n目的在于尋找最優(yōu)的設(shè)備加工任務(wù)次序，使得等待時(shí)間與目的在于尋

3、找最優(yōu)的設(shè)備加工任務(wù)次序，使得等待時(shí)間與切換時(shí)間最小。切換時(shí)間最小。(1) 單機(jī)調(diào)度問(wèn)題單機(jī)調(diào)度問(wèn)題(2) 并行機(jī)調(diào)度問(wèn)題并行機(jī)調(diào)度問(wèn)題(3) Job-shop調(diào)度問(wèn)題調(diào)度問(wèn)題(4) Flow-shop調(diào)度問(wèn)題調(diào)度問(wèn)題(5) Open-shop調(diào)度問(wèn)題調(diào)度問(wèn)題給定一個(gè)工件的集合給定一個(gè)工件的集合P和一個(gè)機(jī)器的集合和一個(gè)機(jī)器的集合M每個(gè)工件包括多道工序每個(gè)工件包括多道工序 Ji=Pi1 . Pik 每臺(tái)設(shè)備可以多個(gè)加工任務(wù)每臺(tái)設(shè)備可以多個(gè)加工任務(wù)JMi=J(1) . J(li) 約束：約束：n順序約束：同一個(gè)產(chǎn)品的有序工序?qū)Ρ仨氃谇耙还ば蛲瓿珊蟛拍茼樞蚣s束：同一個(gè)產(chǎn)品的有序工序?qū)Ρ仨氃谇耙还ば蛲?/p>

4、成后才能開(kāi)始開(kāi)始n占用約束：每臺(tái)機(jī)床同一時(shí)間只能加工一個(gè)產(chǎn)品的某個(gè)工序，占用約束：每臺(tái)機(jī)床同一時(shí)間只能加工一個(gè)產(chǎn)品的某個(gè)工序，每每道工序需要在一臺(tái)給定的機(jī)器上非間斷地加工一段時(shí)間道工序需要在一臺(tái)給定的機(jī)器上非間斷地加工一段時(shí)間Job-shop問(wèn)題問(wèn)題 決策：工序分配給機(jī)器上某個(gè)時(shí)間段決策：工序分配給機(jī)器上某個(gè)時(shí)間段目標(biāo)：總加工時(shí)間最短的調(diào)度目標(biāo)：總加工時(shí)間最短的調(diào)度ijkJijkSijkTJob-shop問(wèn)題問(wèn)題A設(shè)備設(shè)備B設(shè)備設(shè)備C設(shè)備設(shè)備D設(shè)備設(shè)備任務(wù)任務(wù)1任務(wù)任務(wù)nJSP是一類滿足任務(wù)配置和順序約束要求的資源分配問(wèn)題，是最困難是一類滿足任務(wù)配置和順序約束要求的資源分配問(wèn)題，是最困難的組合

5、優(yōu)化問(wèn)題之一。的組合優(yōu)化問(wèn)題之一。生產(chǎn)的柔性：生產(chǎn)的柔性：設(shè)備使用的柔性設(shè)備使用的柔性設(shè)備安排的柔性設(shè)備安排的柔性調(diào)度決策內(nèi)容包括：調(diào)度決策內(nèi)容包括：分配決策分配決策(工件的加工次序工件的加工次序)時(shí)間決策時(shí)間決策(工件的各工序的加工時(shí)間工件的各工序的加工時(shí)間)路徑?jīng)Q策路徑?jīng)Q策(工件的工序的設(shè)備分配工件的工序的設(shè)備分配) Flow-shop調(diào)度問(wèn)題調(diào)度問(wèn)題 n個(gè)工件在個(gè)工件在m臺(tái)機(jī)器上加工，一個(gè)工件分為臺(tái)機(jī)器上加工，一個(gè)工件分為n道工序，每道工序道工序，每道工序要求不同的機(jī)器加工。要求不同的機(jī)器加工。n個(gè)工件在個(gè)工件在m臺(tái)機(jī)器上的加工順序相同，工件在機(jī)器上的加工臺(tái)機(jī)器上的加工順序相同，工件在機(jī)

6、器上的加工時(shí)間是給定。時(shí)間是給定。問(wèn)題目標(biāo)：求個(gè)工件在機(jī)器上最優(yōu)的加工順序，使最大流程時(shí)問(wèn)題目標(biāo)：求個(gè)工件在機(jī)器上最優(yōu)的加工順序，使最大流程時(shí)間最小。間最小。 M1M2M3M4P1P2設(shè)備設(shè)備產(chǎn)品產(chǎn)品流水車間調(diào)度問(wèn)題，常用流水車間調(diào)度問(wèn)題，常用 表示，即個(gè)表示，即個(gè)n工件工件/m臺(tái)機(jī)器臺(tái)機(jī)器/流水車間流水車間/最大流程時(shí)間最大流程時(shí)間。max/cFmnFlow-shop問(wèn)題示例問(wèn)題示例假設(shè)有假設(shè)有A、B、C、D四種零件，都需要進(jìn)行先車后銑，其加工時(shí)間四種零件，都需要進(jìn)行先車后銑，其加工時(shí)間如表所示。如表所示。零件名稱零件名稱車床工時(shí)（時(shí)）車床工時(shí)（時(shí)）銑床工時(shí)（時(shí)）銑床工時(shí)（時(shí)）A A1515

7、4 4B B8 81010C C6 65 5D D12127 7合計(jì)合計(jì)41412626(D,1,1)(C,1,1)(A,1,1)(B,1,1)0152341(D,2,2)(C,2,2)(A,2,2)0193833(B,2,2)15234829M1（車床）M2（銑床）甘特圖調(diào)度結(jié)果甘特圖調(diào)度結(jié)果甘特圖(A,1,1)(C,1,1)B,1,1)(D,1,1)082041(D,2,2) (C,2,2)(A,2,2)0204132(B,2,2)18274526M1（車床）M2（銑床）優(yōu)化調(diào)度結(jié)果：調(diào)度問(wèn)題不同特點(diǎn)調(diào)度問(wèn)題不同特點(diǎn)Flow-shop 問(wèn)題中各個(gè)產(chǎn)品的生產(chǎn)路徑相同，產(chǎn)品加工工序的順序與設(shè)備

8、的順序?qū)?yīng)，因而某個(gè)設(shè)備的加工任務(wù)順序就表示產(chǎn)品的加工順序。 Job-shop問(wèn)題中各個(gè)產(chǎn)品的加工路線并不相同，設(shè)備上加工任務(wù)與總的加工任務(wù)矩陣無(wú)對(duì)應(yīng)關(guān)系，即使產(chǎn)品數(shù)量與設(shè)備數(shù)量確定，也不能確定所有的加工任務(wù)，存在路徑選擇問(wèn)題。 對(duì)于Flow-shop，若給定某一個(gè)產(chǎn)品生產(chǎn)次序，則可以計(jì)算出所有工序的完成時(shí)間以及等待時(shí)間，而對(duì)于Job-shop，由于它存在路徑選擇問(wèn)題，即使給定產(chǎn)品生產(chǎn)次序，也無(wú)法計(jì)算。 實(shí)際調(diào)度問(wèn)題實(shí)際調(diào)度問(wèn)題n“因?yàn)槠款i工序在不斷變化，我們?nèi)绾沃榔款i在那里？”n“能否自動(dòng)分配工序？ 自動(dòng)調(diào)配人力，設(shè)備能力？”n“在插入急單時(shí)，能否自動(dòng)根據(jù)目標(biāo)重排計(jì)劃，一些定單自動(dòng)延遲，一

9、些定單自動(dòng)提前？”n“能否對(duì)采購(gòu)延遲，生產(chǎn)的延遲， 設(shè)備的故障， 人員的效率等意外快速響應(yīng)，及自動(dòng)進(jìn)行模擬，調(diào)整？”ERP作業(yè)計(jì)劃作業(yè)計(jì)劃ERP(MRPII)制定作業(yè)計(jì)劃的方法一般包括以下幾個(gè)步驟：1、確定批量；2、計(jì)算提前期；3、安排優(yōu)先權(quán)，安排作業(yè)計(jì)劃；4、根據(jù)能力限制調(diào)整作業(yè)計(jì)劃，再重復(fù)前三個(gè)步驟。按預(yù)先制定的提前期，用無(wú)限能力計(jì)劃法編制作業(yè)計(jì)劃。APS先進(jìn)計(jì)劃調(diào)度先進(jìn)計(jì)劃調(diào)度基于約束理論能夠處理生產(chǎn)類型和工序約束自動(dòng)的，可視化的作業(yè)計(jì)劃TOC約束理論一約束理論一n“約束資源”， “瓶頸”n約束資源決定企業(yè)有效產(chǎn)出與庫(kù)存企業(yè)有效產(chǎn)出受到企業(yè)的生產(chǎn)能力和市場(chǎng)的需求量的制約n“非約束”應(yīng)與“

10、約束”同步庫(kù)存水平只要能維持“約束”上的物流連續(xù)穩(wěn)定即可n“非約束”的利用程度不由其本身決定，而是由系統(tǒng)的“約束”決定的。 n“約束”上一個(gè)小時(shí)的損失則是整個(gè)系統(tǒng)的一個(gè)小時(shí)的損失。 n“非約束”節(jié)省的一個(gè)小時(shí)無(wú)益于增加系統(tǒng)有效產(chǎn)出。APS約束類型約束類型 n資源約束 a，單一資源 b，無(wú)限資源 c，并發(fā)資源 d，共享資源 e，可調(diào)整共享資源 n順序約束 n庫(kù)存約束 n特別約束 APS計(jì)劃算法一計(jì)劃算法一n有限能力計(jì)劃有限能力計(jì)劃 a，算法順序計(jì)劃b，向前順序計(jì)劃c，向后順序計(jì)劃b，雙向計(jì)劃或瓶頸計(jì)劃 n基于模擬的計(jì)劃基于模擬的計(jì)劃 基于模擬規(guī)則產(chǎn)生一個(gè)優(yōu)化的計(jì)劃 APS計(jì)劃算法計(jì)劃算法二二向前

11、順序計(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ī)則啟發(fā)式規(guī)則 n主要的優(yōu)點(diǎn)是啟發(fā)式規(guī)則往往利用與該問(wèn)題相關(guān)的知識(shí)，因此，在通常情況下能夠在較短的時(shí)間內(nèi)得到較好方案。 n啟發(fā)式規(guī)

12、則無(wú)法分析與判斷其方案的質(zhì)量。APS中的啟發(fā)式規(guī)則中的啟發(fā)式規(guī)則1、 預(yù)先確定任務(wù)的參數(shù)類規(guī)則 如升序定單屬性值，優(yōu)先級(jí) 、反向優(yōu)先級(jí) 2、 最小化任務(wù)延遲類規(guī)則 如先到先服務(wù)3、 最小化任務(wù)流程時(shí)間類規(guī)則 適用于最小時(shí)間的控制，提高工時(shí)利用率。如完成日期 4、 最大設(shè)備能力類規(guī)則 適用于是計(jì)劃設(shè)備效率來(lái)最大化整個(gè)設(shè)備的生產(chǎn)能力。如閑散時(shí)間 5、 定制規(guī)則流程工業(yè)調(diào)度特點(diǎn)流程工業(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)度生產(chǎn)調(diào)度流程工業(yè)中生產(chǎn)過(guò)程的柔性是靠改變各裝置間的物流分配

13、和生產(chǎn)裝置的工作點(diǎn)來(lái)實(shí)現(xiàn)的，必須由先進(jìn)的在線優(yōu)化、控制技術(shù)來(lái)保證。n靜態(tài)調(diào)度：它考慮工廠生產(chǎn)資源優(yōu)化分配，屬于在確定性環(huán)境下靜態(tài)組合優(yōu)化問(wèn)題；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)度靜態(tài)調(diào)度n主要的決策變量為：各個(gè)操作的開(kāi)始時(shí)間，持續(xù)時(shí)間、執(zhí)行的單元設(shè)備，以及容量。n調(diào)度期變化范圍為23天至26月。受到單元設(shè)備的操作周期、產(chǎn)品的生產(chǎn)周期以及原料準(zhǔn)備所需的時(shí)間影響。聯(lián)系：n產(chǎn)品生產(chǎn)率和產(chǎn)品質(zhì)量指標(biāo)直接由調(diào)度下達(dá)至先進(jìn)控制。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)度n動(dòng)態(tài)調(diào)度又稱再調(diào)度：處理突發(fā)事件，如某項(xiàng)生產(chǎn)控制指標(biāo)超出臨界

14、值，設(shè)備的故障、資源突然短缺以及能源供應(yīng)中斷等。它在生產(chǎn)過(guò)程中出現(xiàn)的意外事件進(jìn)行，保證生產(chǎn)的平穩(wěn)進(jìn)行。n動(dòng)態(tài)調(diào)度依據(jù)生產(chǎn)計(jì)劃和實(shí)際工況響應(yīng)進(jìn)行調(diào)度，與靜態(tài)調(diào)度不同，需要考慮實(shí)時(shí)性。 n動(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)題描述最優(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ù)

15、最優(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 modelConstraintsTime relations start(A)+p(A)=end(

16、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)BA優(yōu)化目標(biāo)優(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é)為三類： n最大能力指標(biāo)n成本指標(biāo) n客戶滿意度指標(biāo) 間歇型生產(chǎn)過(guò)程調(diào)度間歇型生產(chǎn)過(guò)程調(diào)度n間歇型生產(chǎn)過(guò)程適用于中小批量且產(chǎn)出價(jià)值較高的產(chǎn)品。

17、一般是由一些通用型的設(shè)備組成，通過(guò)對(duì)設(shè)備、原材料等資源的共享，在同一組設(shè)備上實(shí)現(xiàn)多種產(chǎn)品的生產(chǎn)，并且可以實(shí)現(xiàn)較為復(fù)雜的合成過(guò)程。n間歇型生產(chǎn)過(guò)程的靈活性，對(duì)生產(chǎn)調(diào)度提出了更高的要求。 由于設(shè)備可由多項(xiàng)流程共享，工藝描述與設(shè)備描述是不同且獨(dú)立的，在設(shè)備管理的同時(shí)還亟需工藝管理。為了在特定的時(shí)間段上將設(shè)備分配給特定的工藝流程，調(diào)度成為最重要的功能。中間貯罐協(xié)調(diào)工序間差異中間貯罐協(xié)調(diào)工序間差異中間貯罐： 某些需要較長(zhǎng)加工時(shí)間的工序成為生產(chǎn)過(guò)程的瓶頸，它屬于時(shí)間瓶頸。為解決瓶頸問(wèn)題，往往在工序間加入中間貯罐，使得上、下游的物料流分離，協(xié)調(diào)工序間生產(chǎn)能力、加工時(shí)間差異。 中間貯罐并不能夠完全地解決時(shí)間與

18、能力瓶頸。 由于中間產(chǎn)品往往具有不穩(wěn)定的特點(diǎn)，它在加工完成后，必須立即由下一道工序加工，而不允許等待。導(dǎo)致了工序間存在大量的空閑時(shí)間，降低了設(shè)備的使用率和生產(chǎn)率，中間存儲(chǔ)策略中間存儲(chǔ)策略不同性質(zhì)的化工產(chǎn)品(中間品)具有不同的中間存儲(chǔ)策略： NIS無(wú)限存儲(chǔ)策略 FIS有限存儲(chǔ)策略 NIS無(wú)中間存儲(chǔ) ZW零等待策略 MIS混合存儲(chǔ)策略成品與原料一般為無(wú)限存儲(chǔ)，不穩(wěn)定中間品必須采用ZW策略，而穩(wěn)定中間品可采用FIS(有限能力的貯罐)或NIS(設(shè)備自身存儲(chǔ))。 連續(xù)型流程工業(yè)生產(chǎn)調(diào)度連續(xù)型流程工業(yè)生產(chǎn)調(diào)度n連續(xù)型生產(chǎn)過(guò)程適合于固定的大批量產(chǎn)品的生產(chǎn)，其特點(diǎn)是生產(chǎn)過(guò)程工藝流程基本不變，物料流是連續(xù)的。n

19、物流與能源流的連續(xù)、操作任務(wù)連續(xù)執(zhí)行是連續(xù)過(guò)程的本質(zhì)特點(diǎn)。n連續(xù)過(guò)程的特點(diǎn)為其物料(中間品)可以為多個(gè)工序使用，并生產(chǎn)不同的產(chǎn)品，調(diào)度問(wèn)題的目的在于合理調(diào)配物料，使之能夠獲得最大的經(jīng)濟(jì)效益。n由于關(guān)鍵中間品的生產(chǎn)能力存在瓶頸，可稱為有限能力下最大利潤(rùn)問(wèn)題。 連續(xù)型流程工業(yè)生產(chǎn)調(diào)度連續(xù)型流程工業(yè)生產(chǎn)調(diào)度調(diào)度方法：優(yōu)化目標(biāo)在于充分利用有限的生產(chǎn)能力進(jìn)行物料的調(diào)配與平衡。 由于產(chǎn)品的變化是由裝置加工方案和工藝操作條件決定的，生產(chǎn)過(guò)程的一定限度內(nèi)的柔性是靠改變各裝置間物流的分配和改變裝置運(yùn)行的工作點(diǎn)即工藝操作參數(shù)來(lái)實(shí)現(xiàn)的。前者通過(guò)生產(chǎn)調(diào)度系統(tǒng)來(lái)確定，后者則通過(guò)操作優(yōu)化，由先進(jìn)控制來(lái)保證。實(shí)時(shí)性要求：由

20、于生產(chǎn)是在連續(xù)不斷的進(jìn)行之中，調(diào)度問(wèn)題也隨著生產(chǎn)流程的變化而變化，在時(shí)間上要求調(diào)度決策迅速及時(shí)，與生產(chǎn)流程保持同步，要求滯后時(shí)間在一定的域值范圍之內(nèi)。Scheduling Problems Type IOne machineMultiple machine (Single-stage)Scheduling Problems Type IIMulti-stageMulti-purposeS310%90%HeatS460%Reaction 3S740%SeparationReaction1Reaction3Reaction270%30%S5S6S2S1Heat過(guò)程調(diào)度類型過(guò)程調(diào)度類型生產(chǎn)過(guò)程生產(chǎn)調(diào)

21、度問(wèn)題可按其產(chǎn)品生產(chǎn)工藝的相似程度分為兩類：多產(chǎn)品(Multi-Stage)過(guò)程，類似于Flowshop 整個(gè)生產(chǎn)過(guò)程分為若干個(gè)生產(chǎn)階段，每個(gè)階段內(nèi)包括若干個(gè)并行生產(chǎn)設(shè)備，每個(gè)產(chǎn)品都需要順序經(jīng)過(guò)所有的生產(chǎn)階段。多用途(Multi-Purpose) 過(guò)程調(diào)度。類似于Jobshop 各個(gè)產(chǎn)品的生產(chǎn)工藝不相同，同一產(chǎn)品生產(chǎn)存在多個(gè)備選生產(chǎn)路徑，其生產(chǎn)路途并不是預(yù)先確定的，可以通過(guò)設(shè)備的組織安排來(lái)調(diào)整，因此其調(diào)度問(wèn)題比多產(chǎn)品過(guò)程更復(fù)雜。 ExampleABB1CABC原生產(chǎn)過(guò)程中，A加工時(shí)間1h，B加工時(shí)間4h，C加工時(shí)間2h，原來(lái)每批次循環(huán)時(shí)間為4小時(shí)，現(xiàn)增加一個(gè)設(shè)備B1，批次循環(huán)時(shí)間降為2小時(shí)；A

22、工序上的等待時(shí)間減少了2h ，C設(shè)備上空閑時(shí)間由原來(lái)的2小時(shí)降為零 0 4 5 6 7 8 9 10 11 0 4 5 6 7 8 9Scheduling Problems PropertyDifferent Constraints Sequence (in)dependent setup times Release/due timesDifferent Objective Functions Maximize throughput over a fixed period of time Minimize completion time (makespan) for a given set o

23、f ordersScheduling in Chemical Industry Manufacturing Industry Chemical Industry Order Single unit (e.g. car) Variable amount of chemical (e.g. 1.5 ton of sulfur acid) Production Assembly/addition of parts Mixing of intermediate chemicals in various ratios Variable batch sizesRecycle streams, batch

24、splitting/mixingDifferent storage policies; shared storage tanksUtilities (cooling water, steam, etc.)S310%90%HeatS460%Reaction 3S740%SeparationReaction1Reaction3Reaction270%30%S5S6S2S1HeatState-Task Network (STN) RepresentationS3HeatReaction11h2hSeparationS4S1S2Reaction23hS5S62hReaction 3S71hSTN網(wǎng)是一

25、個(gè)具有兩類節(jié)點(diǎn)的有向圖，分別表示狀態(tài)與任務(wù)，狀態(tài)指生產(chǎn)過(guò)程的各種物料，而任務(wù)表示物料從一種狀態(tài)轉(zhuǎn)換至另一狀態(tài)的操作，通過(guò)各個(gè)狀態(tài)的存儲(chǔ)能力屬性來(lái)表示各種中間存儲(chǔ)策略。 State-Task Network (STN) RepresentationBsA2=BsA4=20S140%25%S3S260%S475%BIA,S1,2=8BOA,S3,4=5BIA,S2,2=12BOA,S4,4=15State-Task Network (STN) RepresentationInventoryS2S30 1 2 3 4 5 6 Time (h) Reactor 1Reactor 2Reactor 3C

26、olumnHeating Reaction 1Reaction 2Reaction 3Separation0 1 2 3 4 5 6 Time (h)優(yōu)化調(diào)度模型優(yōu)化調(diào)度模型時(shí)間表示方式時(shí)間表示方式 Kondili, Pantelides & Sargent (1993); Shah, Pantelides & Sargent (1993): STN - Discrete Pantelides (1994): RTN - DiscreteGeneral framework for handling wide range of scheduling problems. MILP

27、with many binaries.Zhang & Sargent (1995); Mockus & Reklaitis (1999): STN/RTN - ContinuousSchilling & Pantelides (1996): RTN - ContinuousGeneral MINLP formulation for design and scheduling. Reduces to MILP for fixed recipes.Ierapetritou & Floudas (1998): STN Continuous Event-Based Fo

28、rmulationNew continuous-time representation with different events for each process unit.Cerda and Mendez (2000); Rodriguez et al. (2001); Lee et al. (2001); Castro et al. (2001)Special cases: No batch splitting/mixing, no resource constraints other than units.優(yōu)化調(diào)度模型優(yōu)化調(diào)度模型時(shí)間表示方式 n標(biāo)準(zhǔn)時(shí)間分布(UDM)， 以所有的工廠任

29、務(wù)的最短操作時(shí)間為劃分標(biāo)準(zhǔn)等分時(shí)間，并假定所有操作(生產(chǎn)任務(wù)開(kāi)始、約束、資源的變化、設(shè)備失效等)均發(fā)生在各時(shí)間段的邊界上。非標(biāo)準(zhǔn)連續(xù)時(shí)間分布(NUDM)，將時(shí)間表達(dá)為連續(xù)變量，時(shí)間段的劃分為非均勻方式，時(shí)間段的個(gè)數(shù)與長(zhǎng)度非預(yù)先確定，它可以在整個(gè)調(diào)度期內(nèi)的任意一點(diǎn)開(kāi)始。離散事件表示，不存在時(shí)間段的劃分，直接以任務(wù)和設(shè)備上事件的開(kāi)始、結(jié)束時(shí)間來(lái)表示。Fixed time pointsFixed time intervalVariable time pointsVariable time intervals No common time intervalsTime Representations -

30、Discrete Time Representation2 hr1 hr 30 min3 hrT = 30 minT1T2T3 Approximations often needed Constant processing timesT1T2T30 1 2 3 4 5 6 7 8 t (hr)2 hr1 hr 40 min3 hrT = 20 min0 1 2 3 4 5 6 7 8 t (hr) T1 T2 T3 Time Representations -Continuous Time Representation No approximations needed Accounts for

31、 variable processing times Fewer time periods Fewer variables & constraints Duration and number of time periods unknown T1 T2 T3 T1T2T30 1 2 3 4 5 6 7 8 t (hr)Continuous Time Representation ITime Representations - Event-Based Representation T1T2T30 1 2 3 4 5 6 7 8 t (hr)122233Event-Based Represe

32、ntation 決策變量為設(shè)備事件分配與任務(wù)事件分配在某一事件上使用邏輯約束使得若任務(wù)事件發(fā)生，必然使得某個(gè)設(shè)備事件發(fā)生。此方法避免使用時(shí)間分配變量模型為MILP優(yōu)化模型，但需要預(yù)先估算事件的個(gè)數(shù)。 時(shí)間表達(dá)方式差異時(shí)間表達(dá)方式差異UDM直觀，簡(jiǎn)單，將調(diào)度水平分成的等間隔時(shí)間段。問(wèn)題可以表示為一個(gè)多時(shí)段的MILP模型。但模型規(guī)模與加工時(shí)間有關(guān)，可能產(chǎn)生計(jì)算復(fù)雜性問(wèn)題。NUDM直接通過(guò)使用連續(xù)變量來(lái)表示所有事件（如：任務(wù)的開(kāi)始和結(jié)束）的發(fā)生時(shí)間，而不是分布在每個(gè)人為分成的等間隔時(shí)間段上，從而達(dá)到減少變量的數(shù)目的目的。問(wèn)題最后表示為MINLP，模型較為復(fù)雜。模型規(guī)模與加工時(shí)間無(wú)關(guān)。在事件數(shù)目遠(yuǎn)小于

33、時(shí)間段數(shù)目時(shí)，NUDM的性能明顯優(yōu)于UDM。COMPUTATIONAL EFFICIENCYAvoid time partitioningFew time intervalsAvoid big-M constraintsNo utility constraintsGENERALITYRecycle streamsBatch splitting/mixingDifferent storage policiesUtility constraintsExample1Given:the time horizonthe available units and storage tanks, and the

34、ir capacitiesthe available utilities (steam, cooling water)the production recipe (mass balance coefficients, utility requirements)the prices of raw materials and final productsDetermine:the sequence and the timing of tasks taking place in each unitthe batch size of tasks (i.e. the processing time an

35、d the allocated resources)the amount of raw materials purchased and final products soldExample2Maximize Production over a fixed time horizonExample2-RemarkExample3Unlimited StorageFinite StorageNo Intermediate StorageZero-WaitCooling WaterLow Pressure SteamHigh Pressure SteamDifferent Storage Polici

36、es Utility ConstraintsExample3-ResultBinaries: 249 Nodes:690 Continuous: 1,711 CPU sec: 22.7 Constraints 3,382Equipment Gantt Chart -Utility Consumption Graph基于基于UDMUDM的調(diào)度優(yōu)化模型的調(diào)度優(yōu)化模型,.,2 , 1, ),(qnERSRQTfMaxiltiktijtin0),(iltiktijtisERSRQTH0),(iltiktijtisERSRQTG0),(iltiktijtisERSRQTD),.,2 , 1 (Ht基于基

37、于UDMUDM的調(diào)度優(yōu)化模型的調(diào)度優(yōu)化模型Assignment Constraints Calculation of duration and finish time of task i Mass balances Utility Constraint Tightening Constraints 計(jì)劃調(diào)度優(yōu)化方法數(shù)學(xué)規(guī)劃計(jì)劃調(diào)度優(yōu)化方法數(shù)學(xué)規(guī)劃數(shù)學(xué)規(guī)劃理論包括：排隊(duì)網(wǎng)絡(luò)方法(Queing Network)線性規(guī)劃(Linear Programming, LP)非線性規(guī)劃(Non-linear Programming, NLP)動(dòng)態(tài)規(guī)劃(Dynamical Programming, DP)混合

38、整數(shù)線性規(guī)劃(Mixed Integer Linear Programming , MILP)工業(yè)中的應(yīng)用最為廣泛的是混合整數(shù)規(guī)劃。計(jì)劃調(diào)度優(yōu)化方法數(shù)學(xué)規(guī)劃計(jì)劃調(diào)度優(yōu)化方法數(shù)學(xué)規(guī)劃優(yōu)點(diǎn)：主要優(yōu)點(diǎn)是其全局優(yōu)化的觀點(diǎn)，對(duì)所有的分配與次序決策都同時(shí)做出，能夠有效地評(píng)價(jià)方案的質(zhì)量。對(duì)于凸問(wèn)題能夠得到全局最優(yōu)解。即使求解過(guò)程在達(dá)到到最佳解之前終止，對(duì)于凸問(wèn)題也能夠得到達(dá)到全局最優(yōu)解的范圍，能夠有效地評(píng)價(jià)方案的質(zhì)量。缺點(diǎn)：盡管通用算法很有效，但也往往不能在可行時(shí)間內(nèi)得到一個(gè)可行解。必須針對(duì)特定問(wèn)題，開(kāi)發(fā)和使用特殊的算法。而且問(wèn)題發(fā)生輕微變化后，原先的算法就可能失效。用戶必須將問(wèn)題抽象為形式化的模型。相同的

39、問(wèn)題可以描述為不同的模型 。 計(jì)劃調(diào)度優(yōu)化方法人工智能計(jì)劃調(diào)度優(yōu)化方法人工智能n生產(chǎn)過(guò)程是高維對(duì)象，采用規(guī)劃模型求解調(diào)度問(wèn)題，隨著維數(shù)的增加，計(jì)算量呈指數(shù)增長(zhǎng)。n為了提高求解效率、減少計(jì)算工作量，提出了不少基于規(guī)則的優(yōu)化方法。對(duì)于提高計(jì)算效率起到了重要的作用；n采用人工智能的方法 (如各種搜索的方法、專家系統(tǒng)的方法等) 對(duì)于解決具體的調(diào)度問(wèn)題，不僅可以簡(jiǎn)化問(wèn)題，而且能獲得合乎實(shí)際的滿意解。 運(yùn)籌學(xué)和人工智能融合運(yùn)籌學(xué)和人工智能融合 兩類方法采用了不同的模型，不同的術(shù)語(yǔ)，各有其特點(diǎn)，但都未能真正解決調(diào)度與計(jì)劃決策問(wèn)題。由于生產(chǎn)環(huán)境的動(dòng)態(tài)性，生產(chǎn)領(lǐng)域知識(shí)的多樣性，調(diào)度問(wèn)題的復(fù)雜性，必須將人、數(shù)學(xué)方

40、法和信息技術(shù)結(jié)合起來(lái)研究生產(chǎn)領(lǐng)域的管理調(diào)度問(wèn)題。 注重算法在實(shí)際問(wèn)題中的應(yīng)用，以及實(shí)際調(diào)度與計(jì)劃問(wèn)題的解決。 分解Basic Decomposition IdeaCompared to “manufacturing” problems:1. Unknown type and number of batches (tasks); unknown assignments of tasks to units2. Mixing of intermediates; variable batch-size and processing time There are good algorithms for

41、problems with fixed type and number of tasks and fixed assignments Decompose problem in two subproblems1. Determine type and number of tasks and assignments of units to tasks2. Solve reduced problem with an efficient, problem-specific algorithm 分解Basic Decomposition IdeaAlgebra x1+2x2+2x3= 62x1+ x2

42、+ x3= 63x2+4x3= 7 x3+3x4+ x5= 8 x4+2x5= 8 x 1 = 2 x 2 = 1 x 3 = 1 x 4 = 2 x5=3Optimization M2M2 M1 Underdetermined Many solutions Solve (S1) & (S2) many timesSolution time: 2 (M1) 210 = 1024 sec(M1) & (M2) 25+25= 64 sec 1st Subproblem (M1): Mathematical Programming MILP 2nd Subproblem (M2):

43、Constraint Programming Modeling and Solution Paradigms Mathematical Programming Well known & widely applied Efficient algorithms for moderately sized problems (branch-and bound, cutting planes) Search is based on solution of relaxed problems Constraint Programming New Modeling and Solution Parad

44、igm Developed in early 90s in AI Very effective for classes of optimization problemsHighly constrained (feasibility) problems; some scheduling problems Special “constructs” and constraints for classes of problems Constructs:activity X, unary resource Y Constraints: X requires Y(GLOBAL)A B, A B(LOGIC

45、) Highly Expressive Effective local search Search is based on constraint propagation Mathematical vs. Constraint ProgrammingConstraint Programming Fast algorithms for special problems Computationally effective for highly constrained, feasibility and machine sequencing problems Not effective for opti

46、mization problems with complex structure and many feasible solutions Mathematical Programming Intelligent search strategy but computationally expensive for large problems Computationally effective for optimization problems with many feasible solutions Not effective for feasibility problems and machi

47、ne sequencing problems MAIN IDEA Decompose problem into two parts Use MP for high-level optimization decisions Use CP for low-level sequencing decisions Proposed Strategy ProductionZ*Upper boundFeasible solution0 2 4 6 8 10Iterations Fix no/type of tasks and assignment decisions Problem is highly co

48、nstrained: suitable for CP If feasible, obtain lower bound Add integer cut and continue until bounds converge Express problem in an aggregated MP form Use MP to identify potentially good solutions Fix no/type of tasks, assignment of tasks to units Fix no/type of tasks and assignment decisions Proble

49、m is highly constrained: suitable for CP If feasible, obtain lower bound Add integer cut and continue until bounds converge Solve MIP Master Problemmax productions.t. RELAXATIONObtain UBSolve CP Sub problemmax productions.t. ALL CONSTRAINTS w/ fixed no/type of tasksObtain LB Solve MIP Master Problem

50、max productions.t. RELAXATION Obtain UB Fix no/type of tasks,assignment to units Add integer cuts Fix no/type of tasks and assignment decisions Problem is highly constrained: suitable for CP If feasible, obtain lower bound Add integer cut and continue until bounds convergeProposed Formulation Solve

51、MIP Master Problemmax productions.t. RELAXATIONObtain UBCP Sub problem(CP)max productions.t. ALL CONSTRAINTS w/ fixed no/type of tasksObtain LB MIP Master Problem(MP)max productions.t. SOME CONSTRAINTS Obtain UB Fix no/type of tasks,assignment to units Add integer cuts Tasks ActivitiesUnits Unary Re

52、sources Utilities Discrete Resources States Reservoirs Zic = 1 if batch c of task i is carried out Integer Cuts INTsCSCciZZsBBSSciZBBZBjMSZDssicicicicIiticicOitsicMAXiicicMINijIicicic |, , 10)(Generalization of Decomposition Framework I Multipurpose Batch Plant S310%90%HeatS460%Reaction 3S740%Separa

53、tionReaction1Reaction3Reaction270%30%S5S6S2S1HeatMaster MIP Problem CP Sub problemZic = 1 if batch c of task i is carried out Bic = batch size of batch c of task i Ss = inventory level of state s ciMSendciTaskscisStateBconsumesciTaskscisStateBconsumesciTaskcirUtilityRrequiresciTaskcjIijjUnitrequires

54、ciTaskFPsdBciBRciBBBicspisiscisicicsOicsiciiicMAXiicMINi, ., , , ,),(, , , , INTsCSFPsdSsBBSSciZBBZBjESTSTMSZDssssicicIiticicOitsicMAXiicicMINijIicjjicic , 0)(Generalization of Decomposition Framework - General Multi-stage PlantMaster MIP Problem CP Sub problemZic = 1 if batch c of task i is carried

55、 out Bic = batch size of batch c of task i Ss = inventory level of state s ciMSendciTaskscisStateBconsumesciTaskscisStateBconsumesciTaskcjIijjUnitrequiresciTaskFPsdBciBBBicsisicsOicsMAXiicMINi, ., 1 , 1 ,),(, , , INTsCSFPsdSsBBSSciZBBZBjESTSTMSZDssssicicicicsicMAXiicicMINijIicjjicic 11, 0)(T10T20T11

56、T21T30T31F1F2F3S10S20S30S11S21S31P1P2P3T10T20T30T11T21T31T12T22T32 Generalization of Decomposition Framework - Multi-stage Plant: demand in ordersMaster MIP Problem CP Sub problem Fixed batches & batch-sizes Drop c index, B variables Task(order,stage,unit): i(o,k,j) Add assignment constraint kZj

57、oMSendjkoTaskkojkoTaskpreceedjkoTaskkZjojUnitrequiresjkoTaskokjokj, 1|, ., , 1, , 1|, ,)()(, 1)( kJjokjjOokkokjokjkoZkJjESTSTMSXDT10T20T11T21T30T31F1F2F3S10S20S30S11S21S31P1P2P3T10T20T30T11T21T31T12T22T32Generalization of Decomposition Framework: Single-stageMaster MIP Problem CP Sub problem 1|, .,1

58、|, , ., .,okokooZjkoMSendjkoTaskZjkojUnitrequiresjoTaskjodendjoTaskjorstartjoTask)()( 1 maxmaxkJjojjOooOooOoojojoZjrdXDGeneralization of Decomposition Framework IIUse problem-specific algorithm to solve sub problem (not necessarily CP) Minimization of cost of multi-stage problem for orders with rele

59、ase and due timesN orders have to be processed sequentially on K stages, where each stage consists of Mk units. Each order i has release ri and due di time that have to be met, and a processing cost cij and processing time ptij when processed on unit j. The objective is to minimize the sum of proces

60、sing costs subject to meeting the release and due times. Subproblem is a traditional OR problem (job-shop problem) There are efficient algorithmsUse Shifting Bottleneck Procedure (Adams and Balas, 1988) to solve the sub problem Master Problem: AssignmentSub problem: Sequencing Generalization of Decomposition Framework IVMILP SolverMaster