生產(chǎn)計劃與調(diào)度

1、消費方案與調(diào)度Production Planning and Scheduling浙江大學(xué)系統(tǒng)工程研討所.OUTLINEProduction Scheduling離散制造過程(APS)流程工業(yè)間歇與延續(xù)消費調(diào)度數(shù)學(xué)模型調(diào)度問題優(yōu)化方法智能調(diào)度方法.離散制造過程消費調(diào)度消費控制的主要內(nèi)容是作業(yè)方案與動態(tài)調(diào)整，它稱為車間調(diào)度問題。包括兩個方面：其一為靜態(tài)調(diào)度，產(chǎn)生一個初始調(diào)度；其二為不測事件發(fā)生后，進(jìn)展調(diào)度的修正與調(diào)整即動態(tài)調(diào)度。 MRP II內(nèi)主要采用啟發(fā)式規(guī)那么進(jìn)展作業(yè)調(diào)度與優(yōu)先級控制，提供一個建議的作業(yè)方案，在訂單下達(dá)時，包括開工日期與完工日期，但已思索了時間余量，因此，車間調(diào)度有一定的緩沖

2、余地。執(zhí)行中的不測即動態(tài)調(diào)度可由車間進(jìn)展有限的部分調(diào)度，但當(dāng)其影響到消費方案時，只能反響至方案部門，由方案部門一致調(diào)整。 .車間作業(yè)調(diào)度的特點離散制造過程中，工件消費時間較短，工件切換加工本錢低但庫存本錢很高。 主要處理多個產(chǎn)品對設(shè)備的爭用問題。目的在于尋覓最優(yōu)的設(shè)備加工義務(wù)次序，使得等待時間與切換時間最小。(1) 單機調(diào)度問題(2) 并行機調(diào)度問題(3) Job-shop調(diào)度問題(4) Flow-shop調(diào)度問題(5) Open-shop調(diào)度問題.給定一個工件的集合P和一個機器的集合M每個工件包括多道工序 Ji=Pi1 . Pik 每臺設(shè)備可以多個加工義務(wù)JMi=J(1) . J(li) 約

3、束：順序約束：同一個產(chǎn)品的有序工序?qū)Ρ匦柙谇耙还ば蛲瓿珊蟛鸥砷_場占用約束：每臺機床同一時間只能加工一個產(chǎn)品的某個工序，每道工序需求在一臺給定的機器上非延續(xù)地加工一段時間Job-shop問題 決策：工序分配給機器上某個時間段目的：總加工時間最短的調(diào)度.Job-shop問題A設(shè)備B設(shè)備C設(shè)備D設(shè)備義務(wù)1義務(wù)nJSP是一類滿足義務(wù)配置和順序約束要求的資源分配問題，是最困難的組合優(yōu)化問題之一。消費的柔性：設(shè)備運用的柔性設(shè)備安排的柔性調(diào)度決策內(nèi)容包括：分配決策(工件的加工次序)時間決策(工件的各工序的加工時間)途徑?jīng)Q策(工件的工序的設(shè)備分配) .Flow-shop調(diào)度問題 n個工件在m臺機器上加工，一個

4、工件分為n道工序，每道工序要求不同的機器加工。n個工件在m臺機器上的加工順序一樣，工件在機器上的加工時間是給定。問標(biāo)題的：求個工件在機器上最優(yōu)的加工順序，使最大流程時間最小。 M1M2M3M4P1P2設(shè)備產(chǎn)品流水車間調(diào)度問題，常用 表示，即個n工件/m臺機器/流水車間/最大流程時間。.Flow-shop問題例如假設(shè)有A、B、C、D四種零件，都需求進(jìn)展先車后銑，其加工時間如表所示。零件稱號車床工時時銑床工時時A154B810C65D127合計4126甘特圖.調(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

5、,2,2)18274526M1車床M2銑床優(yōu)化調(diào)度結(jié)果：.調(diào)度問題不同特點Flow-shop 問題中各個產(chǎn)品的消費途徑一樣，產(chǎn)品加工工序的順序與設(shè)備的順序?qū)?yīng)，因此某個設(shè)備的加工義務(wù)順序就表示產(chǎn)品的加工順序。 Job-shop問題中各個產(chǎn)品的加工道路并不一樣，設(shè)備上加工義務(wù)與總的加工義務(wù)矩陣無對應(yīng)關(guān)系，即使產(chǎn)品數(shù)量與設(shè)備數(shù)量確定，也不能確定一切的加工義務(wù)，存在途徑選擇問題。 對于Flow-shop，假設(shè)給定某一個產(chǎn)品消費次序，那么可以計算出一切工序的完成時間以及等待時間，而對于Job-shop，由于它存在途徑選擇問題，即使給定產(chǎn)品消費次序，也無法計算。 .實踐調(diào)度問題“由于瓶頸工序在不斷變化，

6、我們?nèi)绾沃榔款i在那里？“能否自動分配工序？ 自動調(diào)配人力，設(shè)備才干？“在插入急單時，能否自動根據(jù)目的重排方案，一些定單自動延遲，一些定單自動提早？“能否對采購延遲，消費的延遲， 設(shè)備的缺點， 人員的效率等不測快速呼應(yīng)，及自動進(jìn)展模擬，調(diào)整？.ERP作業(yè)方案ERP(MRPII)制定作業(yè)方案的方法普通包括以下幾個步驟：1、確定批量；2、計算提早期；3、安排優(yōu)先權(quán)，安排作業(yè)方案；4、根據(jù)才干限制調(diào)整作業(yè)方案，再反復(fù)前三個步驟。按預(yù)先制定的提早期，用無限才干方案法編制造業(yè)方案。.APS先進(jìn)方案調(diào)度基于約束實際可以處置消費類型和工序約束自動的，可視化的作業(yè)方案.TOC約束實際一“約束資源， “瓶頸約束

7、資源決議企業(yè)有效產(chǎn)出與庫存企業(yè)有效產(chǎn)出遭到企業(yè)的消費才干和市場的需求量的制約“非約束應(yīng)與“約束同步庫存程度只需能維持“約束上的物流延續(xù)穩(wěn)定即可“非約束的利用程度不由其本身決議，而是由系統(tǒng)的“約束決議的。 “約束上一個小時的損失那么是整個系統(tǒng)的一個小時的損失。 “非約束節(jié)省的一個小時無益于添加系統(tǒng)有效產(chǎn)出。.APS約束類型 資源約束 a，單一資源 b，無限資源 c，并發(fā)資源 d，共享資源 e，可調(diào)整共享資源 順序約束 庫存約束 特別約束 .APS方案算法一有限才干方案 a，算法順序方案b，向前順序方案c，向后順序方案b，雙向方案或瓶頸方案 基于模擬的方案 基于模擬規(guī)那么產(chǎn)生一個優(yōu)化的方案 .AP

8、S方案算法二向前順序方案固定了開場時間，決議終了時間，也許會違反完成日期。 向后順序方案固定終了時間，決議開場時間，產(chǎn)生一個不會延遲的方案，然而，方案也許有不可行的開場時間。雙向方案或瓶頸方案，先安排約束資源上加工的關(guān)鍵件的消費進(jìn)度方案，以約束資源為基準(zhǔn)，把約束資源之前、之間、之后的工序分別按拉動、工藝順序、推進(jìn)的方式排定，并進(jìn)展一定優(yōu)化，接下來編制非關(guān)鍵件的作業(yè)方案。特點：與ERP不同，瓶頸算法順序方案中的提早期是批量、優(yōu)先權(quán)和其它許多要素的函數(shù)，是編制造業(yè)方案產(chǎn)生的結(jié)果。.啟發(fā)式規(guī)那么 主要的優(yōu)點是啟發(fā)式規(guī)那么往往利用與該問題相關(guān)的知識，因此，在通常情況下可以在較短的時間內(nèi)得到較好方案。

9、啟發(fā)式規(guī)那么無法分析與判別其方案的質(zhì)量。.APS中的啟發(fā)式規(guī)那么1、 預(yù)先確定義務(wù)的參數(shù)類規(guī)那么 如升序定單屬性值，優(yōu)先級 、反向優(yōu)先級 2、 最小化義務(wù)延遲類規(guī)那么 如先到先效力3、 最小化義務(wù)流程時間類規(guī)那么 適用于最小時間的控制，提高工時利用率。如完成日期 4、 最大設(shè)備才干類規(guī)那么 適用于是方案設(shè)備效率來最大化整個設(shè)備的消費才干。如閑散時間 5、 定制規(guī)那么.流程工業(yè)調(diào)度特點產(chǎn)品配方、產(chǎn)品混合、物料平衡等問題需求思索主產(chǎn)品、副產(chǎn)品、協(xié)產(chǎn)品、半廢品循環(huán)和回流熱蒸汽、冷凍水、緊縮空氣、水、電等動力能源輔助系統(tǒng)也應(yīng)納入調(diào)度.消費調(diào)度流程工業(yè)中消費過程的柔性是靠改動各安裝間的物流分配和消費安裝

10、的任務(wù)點來實現(xiàn)的，必需由先進(jìn)的在線優(yōu)化、控制技術(shù)來保證。靜態(tài)調(diào)度：它思索工廠消費資源優(yōu)化分配，屬于在確定性環(huán)境下靜態(tài)組合優(yōu)化問題；動態(tài)調(diào)度：它是在消費過程出現(xiàn)各種動態(tài)變化要素時進(jìn)展的再調(diào)度。 .靜態(tài)調(diào)度主要的決策變量為：各個操作的開場時間，繼續(xù)時間、執(zhí)行的單元設(shè)備，以及容量。調(diào)度期變化范圍為23天至26月。遭到單元設(shè)備的操作周期、產(chǎn)品的消費周期以及原料預(yù)備所需的時間影響。聯(lián)絡(luò)：產(chǎn)品消費率和產(chǎn)質(zhì)量量目的直接由調(diào)度下達(dá)至先進(jìn)控制。先進(jìn)控制將消費過程的形狀、過程模型的參數(shù)的更新反響至消費調(diào)度。 .動態(tài)調(diào)度動態(tài)調(diào)度又稱再調(diào)度：處置突發(fā)事件，如某項消費控制目的超出臨界值，設(shè)備的缺點、資源忽然短缺以及能源

11、供應(yīng)中斷等。它在消費過程中出現(xiàn)的不測事件進(jìn)展，保證消費的平穩(wěn)進(jìn)展。動態(tài)調(diào)度根據(jù)消費方案和實踐工況呼應(yīng)進(jìn)展調(diào)度，與靜態(tài)調(diào)度不同，需求思索實時性。 動態(tài)消費調(diào)度對消費運轉(zhuǎn)控制的性能具有艱苦影響，但大規(guī)模的具有工業(yè)意義的動態(tài)消費調(diào)度問題由于其復(fù)雜性，單純依托人即使是有閱歷的消費調(diào)度人員來處理已被實際閱歷證明是不現(xiàn)實的。.最優(yōu)調(diào)度問題描畫給定：消費過程的工藝、設(shè)備及全部相關(guān)信息；一個感興趣的時間段；用戶定單及原料到貨信息或消費方案信息決議：每個設(shè)備單元的操作時間例如，在感興趣的時間段內(nèi)設(shè)備在每個時辰執(zhí)行哪個義務(wù)；工廠的物料流。使得：目的函數(shù)最優(yōu)。.消費過程的約束 約束條件：消費調(diào)度遭到諸多要素的限制，

12、普通有：產(chǎn)品的投產(chǎn)期，交貨期完成期，消費才干，加工順序，加工設(shè)備和原料的可用性，批量大小，加工途徑，本錢限制等，這些都是所謂的約束條件。硬約束與軟約束：硬約束是必需求滿足的，如交貨期，消費才干等，而軟約束只需到達(dá)一定的稱心度即可，如消費本錢等。這些約束普通情況是確定的，在進(jìn)展調(diào)度時大都作為確定性要素思索。不確定性要素：設(shè)備缺點，原料供應(yīng)變化，消費義務(wù)變化等非正常情況，都是事先不能預(yù)見的，大都作為不確定性要素思索。.Scheduling modelConstraintsTime relations start(A)+p(A)=end(A) sequencing BA end(B)start(A)

13、 Resource capacity constraints unary resource (activities cannot overlap) AB BA end(A)start(B) end(B)start(A)BA.優(yōu)化目的 消費調(diào)度的性能目的可以是本錢最低、庫存費用最少減少流動資金占用、消費周期最短、消費切換最少、設(shè)備利用率最高、三廢最少等。消費調(diào)度的性能目的大致可以歸結(jié)為三類： 最大才干目的本錢目的 客戶稱心度目的 .間歇型消費過程調(diào)度間歇型消費過程適用于中小批量且產(chǎn)出價值較高的產(chǎn)品。 普通是由一些通用型的設(shè)備組成，經(jīng)過對設(shè)備、原資料等資源的共享，在同一組設(shè)備上實現(xiàn)多種產(chǎn)品的消費，

14、并且可以實現(xiàn)較為復(fù)雜的合成過程。間歇型消費過程的靈敏性，對消費調(diào)度提出了更高的要求。 由于設(shè)備可由多項流程共享，工藝描畫與設(shè)備描畫是不同且獨立的，在設(shè)備管理的同時還亟需工藝管理。為了在特定的時間段上將設(shè)備分配給特定的工藝流程，調(diào)度成為最重要的功能。.中間貯罐協(xié)調(diào)工序間差別中間貯罐： 某些需求較長加工時間的工序成為消費過程的瓶頸，它屬于時間瓶頸。為處理瓶頸問題，往往在工序間參與中間貯罐，使得上、下游的物料流分別，協(xié)調(diào)工序間消費才干、加工時間差別。 中間貯罐并不可以完全地處理時間與才干瓶頸。 由于中間產(chǎn)品往往具有不穩(wěn)定的特點，它在加工完成后，必需立刻由下一道工序加工，而不允許等待。導(dǎo)致了工序間存在

15、大量的空閑時間，降低了設(shè)備的運用率和消費率，.中間存儲戰(zhàn)略不同性質(zhì)的化工產(chǎn)品(中間品)具有不同的中間存儲戰(zhàn)略： NIS無限存儲戰(zhàn)略 FIS有限存儲戰(zhàn)略 NIS無中間存儲 ZW零等待戰(zhàn)略 MIS混合存儲戰(zhàn)略廢品與原料普通為無限存儲，不穩(wěn)定中間品必需采用ZW戰(zhàn)略，而穩(wěn)定中間品可采用FIS(有限才干的貯罐)或NIS(設(shè)備本身存儲)。 .延續(xù)型流程工業(yè)消費調(diào)度延續(xù)型消費過程適宜于固定的大批量產(chǎn)品的消費，其特點是消費過程工藝流程根本不變，物料流是延續(xù)的。物流與能源流的延續(xù)、操作義務(wù)延續(xù)執(zhí)行是延續(xù)過程的本質(zhì)特點。延續(xù)過程的特點為其物料(中間品)可以為多個工序運用，并消費不同的產(chǎn)品，調(diào)度問題的目的在于合理調(diào)

16、配物料，使之可以獲得最大的經(jīng)濟效益。由于關(guān)鍵中間品的消費才干存在瓶頸，可稱為有限才干下最大利潤問題。 .延續(xù)型流程工業(yè)消費調(diào)度調(diào)度方法：優(yōu)化目的在于充分利用有限的消費才干進(jìn)展物料的調(diào)配與平衡。 由于產(chǎn)品的變化是由安裝加工方案和工藝操作條件決議的，消費過程的一定限制內(nèi)的柔性是靠改動各安裝間物流的分配和改動安裝運轉(zhuǎn)的任務(wù)點即工藝操作參數(shù)來實現(xiàn)的。前者經(jīng)過消費調(diào)度系統(tǒng)來確定，后者那么經(jīng)過操作優(yōu)化，由先進(jìn)控制來保證。實時性要求：由于消費是在延續(xù)不斷的進(jìn)展之中，調(diào)度問題也隨著消費流程的變化而變化，在時間上要求調(diào)度決策迅速及時，與消費流程堅持同步，要求滯后時間在一定的域值范圍之內(nèi)。.Scheduling

17、Problems Type IOne machineMultiple machine (Single-stage).Scheduling Problems Type IIMulti-stageMulti-purposeS310%90%HeatS460%Reaction 3S740%SeparationReaction1Reaction3Reaction270%30%S5S6S2S1Heat.過程調(diào)度類型消費過程消費調(diào)度問題可按其產(chǎn)品消費工藝的類似程度分為兩類：多產(chǎn)品(Multi-Stage)過程，類似于Flowshop 整個消費過程分為假設(shè)干個消費階段，每個階段內(nèi)包括假設(shè)干個并行消費設(shè)備，每個

18、產(chǎn)品都需求順序經(jīng)過一切的消費階段。多用途(Multi-Purpose) 過程調(diào)度。類似于Jobshop 各個產(chǎn)品的消費工藝不一樣，同一產(chǎn)品消費存在多個備選消費途徑，其消費路途并不是預(yù)先確定的，可以經(jīng)過設(shè)備的組織安排來調(diào)整，因此其調(diào)度問題比多產(chǎn)品過程更復(fù)雜。 .ExampleABB1CABC原消費過程中，A加工時間1h，B加工時間4h，C加工時間2h，原來每批次循環(huán)時間為4小時，現(xiàn)添加一個設(shè)備B1，批次循環(huán)時間降為2小時；A工序上的等待時間減少了2h ，C設(shè)備上空閑時間由原來的2小時降為零 0 4 5 6 7 8 9 10 11 0 4 5 6 7 8 9.Scheduling Problems

19、 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 of orders.Scheduling in Chemical IndustryVariable batch sizesRecycle streams, batch spl

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

21、有兩類節(jié)點的有向圖，分別表示形狀與義務(wù)，形狀指消費過程的各種物料，而義務(wù)表示物料從一種形狀轉(zhuǎn)換至另一形狀的操作，經(jīng)過各個形狀的存儲才干屬性來表示各種中間存儲戰(zhàn)略。 .State-Task Network (STN) RepresentationBsA2=BsA4=20S140%25%S3S260%S475%BIA,S1,2=8BOA,S3,4=5BIA,S2,2=12BOA,S4,4=15.State-Task Network (STN) RepresentationInventoryS2S30 1 2 3 4 5 6 Time (h) Reactor 1Reactor 2Reactor 3C

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

23、hang & 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 FormulationNew continuous-time represe

24、ntation 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)度模型時間表示方式 規(guī)范時間分布(UDM)， 以一切的工廠義務(wù)的最短操作時間為劃分規(guī)范等分時間，并假定一切操作(消費義務(wù)開場、約束、資源的變化、設(shè)

25、備失效等)均發(fā)生在各時間段的邊境上。非規(guī)范延續(xù)時間分布(NUDM)，將時間表達(dá)為延續(xù)變量，時間段的劃分為非均勻方式，時間段的個數(shù)與長度非預(yù)先確定，它可以在整個調(diào)度期內(nèi)的恣意一點開場。離散事件表示，不存在時間段的劃分，直接以義務(wù)和設(shè)備上事件的開場、終了時間來表示。Fixed time pointsFixed time intervalVariable time pointsVariable time intervals No common time intervals.Time Representations -Discrete Time Representation2 hr1 hr 30 mi

26、n3 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).Time Representations -Continuous Time Representation No approximations needed Accounts for variable processing times Fewer time periods Fewer

27、 variables & constraints Duration and number of time periods unknownT1T2T30 1 2 3 4 5 6 7 8 t (hr)Continuous Time Representation I.Time Representations - Event-Based Representation T1T2T30 1 2 3 4 5 6 7 8 t (hr)122233Event-Based Representation 決策變量為設(shè)備事件分配與義務(wù)事件分配在某一事件上運用邏輯約束使得假設(shè)義務(wù)事件發(fā)生，必然使得某個設(shè)備事件發(fā)生。此方

28、法防止運用時間分配變量模型為MILP優(yōu)化模型，但需求預(yù)先估算事件的個數(shù)。 .時間表達(dá)方式差別UDM直觀，簡單，將調(diào)度程度分成的等間隔時間段。問題可以表示為一個多時段的MILP模型。但模型規(guī)模與加工時間有關(guān)，能夠產(chǎn)生計算復(fù)雜性問題。NUDM直接經(jīng)過運用延續(xù)變量來表示一切事件如：義務(wù)的開場和終了的發(fā)生時間，而不是分布在每個人為分成的等間隔時間段上，從而到達(dá)減少變量的數(shù)目的目的。問題最后表示為MINLP，模型較為復(fù)雜。模型規(guī)模與加工時間無關(guān)。在事件數(shù)目遠(yuǎn)小于時間段數(shù)目時，NUDM的性能明顯優(yōu)于UDM。COMPUTATIONAL EFFICIENCYAvoid time partitioningFew

29、 time intervalsAvoid big-M constraintsNo utility constraintsGENERALITYRecycle streamsBatch splitting/mixingDifferent storage policiesUtility constraints.Example1Given:the time horizonthe available units and storage tanks, and their capacitiesthe available utilities (steam, cooling water)the producti

30、on 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 and the allocated resources)the amount of raw materials purchased and fin

31、al products sold.Example2Maximize Production over a fixed time horizon.Example2-Remark.Example3Unlimited StorageFinite StorageNo Intermediate StorageZero-WaitCooling WaterLow Pressure SteamHigh Pressure SteamDifferent Storage Policies Utility Constraints.Example3-ResultBinaries: 249 Nodes:690 Contin

32、uous: 1,711 CPU sec: 22.7 Constraints 3,382Equipment Gantt Chart -Utility Consumption Graph.基于UDM的調(diào)度優(yōu)化模型.基于UDM的調(diào)度優(yōu)化模型Assignment Constraints Calculation of duration and finish time of task i Mass balances Utility Constraint Tightening Constraints .方案調(diào)度優(yōu)化方法數(shù)學(xué)規(guī)劃數(shù)學(xué)規(guī)劃實際包括：排隊網(wǎng)絡(luò)方法(Queing Network)線性規(guī)劃(Linea

33、r Programming, LP)非線性規(guī)劃(Non-linear Programming, NLP)動態(tài)規(guī)劃(Dynamical Programming, DP)混合整數(shù)線性規(guī)劃(Mixed Integer Linear Programming , MILP)工業(yè)中的運用最為廣泛的是混合整數(shù)規(guī)劃。.方案調(diào)度優(yōu)化方法數(shù)學(xué)規(guī)劃優(yōu)點：主要優(yōu)點是其全局優(yōu)化的觀念，對一切的分配與次序決策都同時做出，可以有效地評價方案的質(zhì)量。對于凸問題可以得到全局最優(yōu)解。即使求解過程在到到達(dá)最正確解之前終止，對于凸問題也可以得到到達(dá)全局最優(yōu)解的范圍，可以有效地評價方案的質(zhì)量。缺陷：雖然通用算法很有效，但也往往不能在可

34、行時間內(nèi)得到一個可行解。必需針對特定問題，開發(fā)和運用特殊的算法。而且問題發(fā)生細(xì)微變化后，原先的算法就能夠失效。用戶必需將問題籠統(tǒng)為方式化的模型。一樣的問題可以描畫為不同的模型 。 .方案調(diào)度優(yōu)化方法人工智能消費過程是高維對象，采用規(guī)劃模型求解調(diào)度問題，隨著維數(shù)的添加，計算量呈指數(shù)增長。為了提高求解效率、減少計算任務(wù)量，提出了不少基于規(guī)那么的優(yōu)化方法。對于提高計算效率起到了重要的作用；采用人工智能的方法 (如各種搜索的方法、專家系統(tǒng)的方法等) 對于處理詳細(xì)的調(diào)度問題，不僅可以簡化問題，而且能獲得符合實踐的稱心解。 .運籌學(xué)和人工智能交融 兩類方法采用了不同的模型，不同的術(shù)語，各有其特點，但都未能

35、真正處理調(diào)度與方案決策問題。由于消費環(huán)境的動態(tài)性，消費領(lǐng)域知識的多樣性，調(diào)度問題的復(fù)雜性，必需將人、數(shù)學(xué)方法和信息技術(shù)結(jié)合起來研討消費領(lǐng)域的管理調(diào)度問題。 注重算法在實踐問題中的運用，以及實踐調(diào)度與方案問題的處理。 .分解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-si

36、ze and processing time There are good algorithms for 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 .分

37、解Basic Decomposition IdeaAlgebrax1+2x2+2x3= 62x1+ x2 + x3= 63x2+4x3= 7 x3+3x4+ x5= 8 x4+2x5= 8 x1=2 x2=1 x3=1 x4=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 Progr

38、amming MILP2nd Subproblem (M2): 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 Ne

39、w Modeling and Solution Paradigm 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 requ

40、ires Y(GLOBAL)A B, A B(LOGIC) Highly Expressive Effective local search Search is based on constraint propagation .Mathematical vs. Constraint ProgrammingConstraint Programming Fast algorithms for special problemsComputationally effective for highly constrained, feasibility and machine sequencing pro

41、blemsNot effective for optimization 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 fea

42、sibility problems and machine sequencing problems MAIN IDEADecompose problem into two partsUse MP for high-level optimization decisionsUse CP for low-level sequencing decisions . Proposed Strategy ProductionZ*Upper boundFeasible solution0 2 4 6 8 10Iterations Fix no/type of tasks and assignment deci

43、sions Problem is highly constrained: 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 a

44、ssignment decisions Problem 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 L

45、B Solve MIP Master Problemmax 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 converg

46、eProposed Formulation Solve 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 Ta

47、sks ActivitiesUnits Unary Resources Utilities Discrete Resources States Reservoirs Zic = 1 if batch c of task i is carried out Integer Cuts .Generalization of Decomposition Framework I Multipurpose Batch Plant S310%90%HeatS460%Reaction 3S740%SeparationReaction1Reaction3Reaction270%30%S5S6S2S1HeatMas

48、ter 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 .Generalization of Decomposition Framework - General Multi-stage PlantMaster MIP Problem CP Sub problemZic = 1 if batch c of task i is carried out Bic = bat

49、ch size of batch c of task i Ss = inventory level of state s T10T20T11T21T30T31F1F2F3S10S20S30S11S21S31P1P2P3T10T20T30T11T21T31T12T22T32. Generalization of Decomposition Framework - Multi-stage Plant: demand in ordersMaster MIP Problem CP Sub problem Fixed batches & batch-sizes Drop c index, B varia

50、bles Task(order,stage,unit): i(o,k,j) Add assignment constraint T10T20T11T21T30T31F1F2F3S10S20S30S11S21S31P1P2P3T10T20T30T11T21T31T12T22T32.Generalization of Decomposition Framework: Single-stageMaster MIP Problem CP Sub problem.Generalization of Decomposition Framework IIUse problem-specific algori

51、thm to solve sub problem (not necessarily CP) Minimization of cost of multi-stage problem for orders with release 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 process

52、ing cost cij and processing time ptij when processed on unit j. The objective is to minimize the sum of processing 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

53、Balas, 1988) to solve the sub problem Master Problem: AssignmentSub problem: Sequencing .Generalization of Decomposition Framework IVMILP SolverMaster (MP)Subproblem (SP)ProgramControlInteger Cut 1Integer Cut 2Integer Cut 3ConstraintProgrammingShifting Bottleneck ProcedurePreprocessing1Preprocessing

54、2Preprocessing3ProgramControlMaster (MP) Sub problem (SP) Data Plant Configuration Units, tasks, states Yields, mass fractions Processing times Setup times, costs Release/due times Integrated Framework .智能方法約束規(guī)劃highly effective technology that uses domain reduction and constraint propagation to effi

55、ciently solve problems that are highly combinatorial with highly logical content. These problems are usually difficult or impossible to represent with linear expressions. Constraint programming uses information contained in the problem to “prune the search space, rapidly identifying feasible solutio

56、ns. .約束規(guī)劃Constraint programming 約束規(guī)劃的前提是有效地收縮搜索空間與求解一個可行的或最優(yōu)的方案同樣重要。 約束規(guī)劃適宜于實現(xiàn)柔性化，高效率的調(diào)度系統(tǒng)。經(jīng)過為約束傳播者封裝不同的算法，能把適宜特定的問題的求解算法思索進(jìn)去，使得柔性成為能夠。 約束規(guī)劃適宜于處置含有大量約束的調(diào)度與再調(diào)度問題。 .約束規(guī)劃收縮Domain filtering Da=1,2, Db=1,2,3 abValue 1 can be safely removed from Db.Constraints are used actively to remove inconsistencies f

57、rom the problem.Arc consistency .約束規(guī)劃搜索Consistency techniques are (usually) incomplete.We need a search algorithm to resolve the rest!depth-first searchassign a value to the variablepropagate = make the problem locally consistentbacktrack upon failure X in 1.5X=1 X=2 X=3 X=4 X=5In general, search al

58、gorithm resolves remaining disjunctions!X=1 X1(standard labeling)X3 X3(domain splitting)XY XY(variable ordering).constraint satisfaction tree search algorithmswhile not solved and not infeasible docheck consistencyif a dead end is detected thentry to escape from dead endelseselect variableselect val

59、ue for variableendifendwhile.The algorithm CheckConsistencyproc CheckConsistencyForwardCheck;while domains have changed do2-ConsCheck;SequencingCheck;RCPCheck;endwhileendproc.智能方法-遺傳算法 遺傳算法是一種隨機搜索算法，可以在比較短的時間在解空間的不同區(qū)域內(nèi)搜索。 由于它一次產(chǎn)生一組方案，它也適宜于運用并行處置。方案的質(zhì)量由于本錢函數(shù)上的界限不能獲得，所以估價起來有困難。算法的收斂速度很難預(yù)測。 .智能方法Agent自

60、主性：根據(jù)本人的需求，自主地控制其行為協(xié)作性：可與其他Agent交互協(xié)商，經(jīng)過協(xié)作共同完成感應(yīng)性：可以自動而有選擇地察看外部環(huán)境，及時采取動作存在性：不斷察看環(huán)境，更新內(nèi)態(tài)，選擇并執(zhí)行相應(yīng)的動作MAS是由假設(shè)干具有一個或多個目的的Agent按照一定的信息關(guān)系、控制關(guān)系以及問題求解才干的分布方式而組成的，是一個松散耦合的Agent網(wǎng)絡(luò)，其內(nèi)部Agent之間的組織構(gòu)造可靈敏改動?！搬槍r間而設(shè)計(design-to-time)的實時Agent調(diào)度方案.ExPlanTechExPlanTech a production planning system with a functionality to: