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

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

MRPII內(nèi)主要采用啟發(fā)式規(guī)則進行作業(yè)調(diào)度與優(yōu)先級控制，提供一個建議的作業(yè)計劃，在訂單下達時，包括開工日期與完工日期，但已考慮了時間余量，因此，車間調(diào)度有一定的緩沖余地。執(zhí)行中的意外即動態(tài)調(diào)度可由車間進行有限的局部調(diào)度，但當其影響到生產(chǎn)計劃時，只能反饋至計劃部門，由計劃部門統(tǒng)一調(diào)整。

車間作業(yè)調(diào)度的特點離散制造過程中，工件生產(chǎn)時間較短，工件切換加工成本低但庫存成本很高。 主要解決多個產(chǎn)品對設備的爭用問題。目的在于尋找最優(yōu)的設備加工任務次序，使得等待時間與切換時間最小。(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}

每臺設備可以多個加工任務JMi={J(1)…..J(li)}約束：順序約束：同一個產(chǎn)品的有序工序對必須在前一工序完成后才能開始占用約束：每臺機床同一時間只能加工一個產(chǎn)品的某個工序，每道工序需要在一臺給定的機器上非間斷地加工一段時間Job-shop問題

決策：工序分配給機器上某個時間段目標：總加工時間最短的調(diào)度Job-shop問題A設備B設備C設備D設備任務1任務nJSP是一類滿足任務配置和順序約束要求的資源分配問題，是最困難的組合優(yōu)化問題之一。生產(chǎn)的柔性：設備使用的柔性設備安排的柔性調(diào)度決策內(nèi)容包括：分配決策(工件的加工次序)時間決策(工件的各工序的加工時間)路徑?jīng)Q策(工件的工序的設備分配)

Flow-shop調(diào)度問題

n個工件在m臺機器上加工，一個工件分為n道工序，每道工序要求不同的機器加工。n個工件在m臺機器上的加工順序相同，工件在機器上的加工時間是給定。問題目標：求個工件在機器上最優(yōu)的加工順序，使最大流程時間最小。

M1M2M3M4P1P2設備產(chǎn)品流水車間調(diào)度問題，常用表示，即個n工件/m臺機器/流水車間/最大流程時間。Flow-shop問題示例假設有A、B、C、D四種零件，都需要進行先車后銑，其加工時間如表所示。零件名稱車床工時（時）銑床工時（時）A154B810C65D127合計4126甘特圖調(diào)度結果甘特圖(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)度結果：調(diào)度問題不同特點Flow-shop問題中各個產(chǎn)品的生產(chǎn)路徑相同，產(chǎn)品加工工序的順序與設備的順序對應，因而某個設備的加工任務順序就表示產(chǎn)品的加工順序。

Job-shop問題中各個產(chǎn)品的加工路線并不相同，設備上加工任務與總的加工任務矩陣無對應關系，即使產(chǎn)品數(shù)量與設備數(shù)量確定，也不能確定所有的加工任務，存在路徑選擇問題。

對于Flow-shop，若給定某一個產(chǎn)品生產(chǎn)次序，則可以計算出所有工序的完成時間以及等待時間，而對于Job-shop，由于它存在路徑選擇問題，即使給定產(chǎn)品生產(chǎn)次序，也無法計算。實際調(diào)調(diào)度問問題“因為為瓶頸頸工序序在不不斷變變化，，我們們?nèi)绾魏沃赖榔款i頸在那那里？”“能否否自動動分配配工序序？自自動動調(diào)配配人力力，設設備能能力？”“在插插入急急單時時，能能否自自動根根據(jù)目目標重重排計計劃，，一些些定單單自動動延遲遲，一一些定定單自自動提提前？”“能否否對采采購延延遲，，生產(chǎn)產(chǎn)的延延遲，，設設備的的故障障，人人員員的效效率等等意外外快速速響應應，及及自動動進行行模擬擬，調(diào)調(diào)整？”ERP作業(yè)業(yè)計劃劃ERP(MRPII)制定作作業(yè)計計劃的的方法法一般般包括括以下下幾個個步驟驟：1、確確定批批量；；2、計計算提提前期期；3、安安排優(yōu)優(yōu)先權權，安安排作作業(yè)計計劃；；4、根根據(jù)能能力限限制調(diào)調(diào)整作作業(yè)計計劃，，再重重復前前三個個步驟驟。按預先先制定定的提提前期期，用用無限限能力力計劃劃法編編制作作業(yè)計計劃。。APS先進計計劃調(diào)調(diào)度基于約約束理理論能夠處處理生生產(chǎn)類類型和和工序序約束束自動的的，可可視化化的作作業(yè)計計劃TOC約束束理論論一“約束束資源源”，，““瓶頸頸”約束資資源決決定企企業(yè)有有效產(chǎn)產(chǎn)出與與庫存存企業(yè)有有效產(chǎn)產(chǎn)出受受到企企業(yè)的的生產(chǎn)產(chǎn)能力力和市市場的的需求求量的的制約約“非約約束””應與與“約約束””同步步庫存水水平只只要能能維持持“約約束””上的的物流流連續(xù)續(xù)穩(wěn)定定即可可“非約約束””的利利用程程度不不由其其本身身決定定，而而是由由系統(tǒng)統(tǒng)的““約束束”決決定的的?！凹s束”上上一個小時時的損失則則是整個系系統(tǒng)的一個個小時的損損失?！胺羌s束””節(jié)省的一一個小時無無益于增加加系統(tǒng)有效效產(chǎn)出。APS約束束類型資源約束a，單一資資源b，無限資資源c，并發(fā)資資源d，共享資資源e，可調(diào)調(diào)整共享資資源順序約束庫存約束特別約束APS計劃劃算法一有限能力計計劃a，算法順順序計劃b，向前順順序計劃c，向后順順序計劃b，雙向計計劃或瓶頸頸計劃基于模擬的的計劃基于模擬規(guī)規(guī)則產(chǎn)生一一個優(yōu)化的的計劃APS計劃劃算法二向前順序計計劃固定了了開始時間間，決定結結束時間，，也許會違違反完成日日期。向后順序計計劃固定結結束時間，，決定開始始時間，產(chǎn)產(chǎn)生一個不不會延遲的的計劃，然然而，計劃劃也許有不不可行的開開始時間。。雙向計劃或或瓶頸計劃劃，先安排排約束資源源上加工的的關鍵件的的生產(chǎn)進度度計劃，以以約束資源源為基準，，把約束資資源之前、、之間、之之后的工序序分別按拉拉動、工藝藝順序、推推動的方式式排定，并并進行一定定優(yōu)化，接接下來編制制非關鍵件件的作業(yè)計計劃。特點：與ERP不不同，瓶頸頸算法順序序計劃中的的提前期是是批量、優(yōu)優(yōu)先權和其其它許多因因素的函數(shù)數(shù)，是編制制作業(yè)計劃劃產(chǎn)生的結結果。啟發(fā)式規(guī)則則主要的優(yōu)點點是啟發(fā)式式規(guī)則往往往利用與該該問題相關關的知識，，因此，在在通常情況況下能夠在在較短的時時間內(nèi)得到到較好方案案。啟發(fā)式規(guī)則則無法分析析與判斷其其方案的質(zhì)質(zhì)量。APS中的的啟發(fā)式規(guī)規(guī)則1、預先先確定任務務的參數(shù)類類規(guī)則如升序定單單屬性值，，優(yōu)先級、、反向優(yōu)優(yōu)先級2、最小小化任務延延遲類規(guī)則則如先到先服服務3、最小小化任務流流程時間類類規(guī)則適用于最小小時間的控控制，提高高工時利用用率。如完完成日期4、最大大設備能力力類規(guī)則適用于是計計劃設備效效率來最大大化整個設設備的生產(chǎn)產(chǎn)能力。如如閑散時間間5、定制制規(guī)則流程工業(yè)調(diào)調(diào)度特點產(chǎn)品配方、、產(chǎn)品混合合、物料平平衡等問題題需要考慮主主產(chǎn)品、副副產(chǎn)品、協(xié)協(xié)產(chǎn)品、半半成品循環(huán)和回流流熱蒸汽、冷冷凍水、壓壓縮空氣、、水、電等等動力能源源輔助系統(tǒng)統(tǒng)也應納入入調(diào)度生產(chǎn)調(diào)度流程工業(yè)中中生產(chǎn)過程程的柔性是是靠改變各各裝置間的的物流分配配和生產(chǎn)裝裝置的工作作點來實現(xiàn)現(xiàn)的，必須須由先進的的在線優(yōu)化化、控制技技術來保證證。靜態(tài)調(diào)度：：它考慮工工廠生產(chǎn)資資源優(yōu)化分分配，屬于于在確定性性環(huán)境下靜靜態(tài)組合優(yōu)優(yōu)化問題；；動態(tài)調(diào)度：：它是在生生產(chǎn)過程出出現(xiàn)各種動動態(tài)變化因因素時進行行的再調(diào)度度。靜態(tài)調(diào)度主要的決策策變量為：：各個操作作的開始時時間，持續(xù)續(xù)時間、執(zhí)執(zhí)行的單元元設備，以以及容量。。調(diào)度期變化化范圍為2－3天至至2－6月月。受到單單元設備的的操作周期期、產(chǎn)品的的生產(chǎn)周期期以及原料料準備所需需的時間影影響。聯(lián)系：產(chǎn)品生產(chǎn)率率和產(chǎn)品質(zhì)質(zhì)量指標直直接由調(diào)度度下達至先先進控制。。先進控制將將生產(chǎn)過程程的狀態(tài)、、過程模型型的參數(shù)的的更新反饋饋至生產(chǎn)調(diào)調(diào)度。動態(tài)調(diào)度動態(tài)調(diào)度又又稱再調(diào)度度：處理突突發(fā)事件，，如某項生生產(chǎn)控制指指標超出臨臨界值，設設備的故障障、資源突突然短缺以以及能源供供應中斷等等。它在生生產(chǎn)過程中中出現(xiàn)的意意外事件進進行，保證證生產(chǎn)的平平穩(wěn)進行。。動態(tài)調(diào)度依依據(jù)生產(chǎn)計計劃和實際際工況響應應進行調(diào)度度，與靜態(tài)態(tài)調(diào)度不同同，需要考考慮實時性性。動態(tài)生產(chǎn)調(diào)調(diào)度對生產(chǎn)產(chǎn)運行控制制的性能具具有重大影影響，但大大規(guī)模的具具有工業(yè)意意義的動態(tài)態(tài)生產(chǎn)調(diào)度度問題由于于其復雜性性，單純依依靠人（即即使是有經(jīng)經(jīng)驗的生產(chǎn)產(chǎn)調(diào)度人員員）來解決決已被實踐踐經(jīng)驗證明明是不現(xiàn)實實的。最優(yōu)調(diào)度問問題描述給定：生產(chǎn)過程的的工藝、設設備及全部部相關信息息；一個個感感興興趣趣的的時時間間段段；；用戶戶定定單單及及原原料料到到貨貨信信息息或或生生產(chǎn)產(chǎn)計計劃劃信信息息決定定：：每個個設設備備單單元元的的操操作作時時間間（（例例如如，，在在感感興興趣趣的的時時間間段段內(nèi)內(nèi)設設備備在在每每個個時時刻刻執(zhí)執(zhí)行行哪哪個個任任務務））；；工工廠廠的的物物料料流流。。使得得：：目標標函函數(shù)數(shù)最最優(yōu)優(yōu)。。生產(chǎn)產(chǎn)過過程程的的約約束束約束束條條件件：：生產(chǎn)產(chǎn)調(diào)調(diào)度度受受到到諸諸多多因因素素的的限限制制，，一一般般有有：：產(chǎn)產(chǎn)品品的的投投產(chǎn)產(chǎn)期期，，交交貨貨期期（（完完成成期期）），，生生產(chǎn)產(chǎn)能能力力，，加加工工順順序序，，加加工工設設備備和和原原料料的的可可用用性性，，批批量量大大小小，，加加工工路路徑徑，，成成本本限限制制等等，，這這些些都都是是所所謂謂的的約約束束條條件件。。硬約約束束與與軟軟約約束束：：硬約約束束是是必必須須要要滿滿足足的的，，如如交交貨貨期期，，生生產(chǎn)產(chǎn)能能力力等等，，而而軟軟約約束束只只需需達達到到一一定定的的滿滿意意度度即即可可，，如如生生產(chǎn)產(chǎn)成成本本等等。。這這些些約約束束一一般般情情況況是是確確定定的的，，在在進進行行調(diào)調(diào)度度時時大大都都作作為為確確定定性性因因素素考考慮慮。。不確確定定性性因因素素：：設備備故故障障，，原原料料供供應應變變化化，，生生產(chǎn)產(chǎn)任任務務變變化化等等非非正正常常情情況況，，都都是是事事先先不不能能預預見見的的，，大大都都作作為為不不確確定定性性因因素素考考慮慮。。SchedulingmodelConstraintsTimerelationsstart(A)+p(A)=end(A)sequencingB<<Aend(B)≤≤start(A)Resourcecapacityconstraintsunaryresource(activitiescannotoverlap)A<<B∨B<<Aend(A)≤start(B)∨end(B)≤start(A)BA優(yōu)化化目目標標生產(chǎn)產(chǎn)調(diào)調(diào)度度的的性性能能指指標標可可以以是是成成本本最最低低、、庫庫存存費費用用最最少少（（減減少少流流動動資資金金占占用用））、、生生產(chǎn)產(chǎn)周周期期最最短短、、生生產(chǎn)產(chǎn)切切換換最最少少、、設設備備利利用用率率最最高高、、三三廢廢最最少少等等。。生生產(chǎn)產(chǎn)調(diào)調(diào)度度的的性性能能指指標標大大致致可可以以歸歸結結為為三三類類：：最大大能能力力指指標標成本本指指標標客戶滿意度指指標間歇型生產(chǎn)過過程調(diào)度間歇型生產(chǎn)過過程適用于中中小批量且產(chǎn)產(chǎn)出價值較高高的產(chǎn)品。一般是由一些些通用型的設設備組成，通通過對設備、、原材料等資資源的共享，，在同一組設設備上實現(xiàn)多多種產(chǎn)品的生生產(chǎn)，并且可可以實現(xiàn)較為為復雜的合成成過程。間歇型生產(chǎn)過過程的靈活性性，對生產(chǎn)調(diào)調(diào)度提出了更更高的要求。。由于設備可由由多項流程共共享，工藝描描述與設備描描述是不同且且獨立的，在在設備管理的的同時還亟需需工藝管理。。為了在特定定的時間段上上將設備分配配給特定的工工藝流程，調(diào)調(diào)度成為最重重要的功能。。中間貯罐協(xié)調(diào)調(diào)工序間差異異中間貯罐：某些需要較長長加工時間的的工序成為生生產(chǎn)過程的瓶瓶頸，它屬于于時間瓶頸。。為解決瓶頸頸問題，往往往在工序間加加入中間貯罐罐，使得上、、下游的物料料流分離，協(xié)協(xié)調(diào)工序間生生產(chǎn)能力、加加工時間差異異。中間貯罐并不不能夠完全地地解決時間與與能力瓶頸。。由于中間產(chǎn)品品往往具有不不穩(wěn)定的特點點，它在加工工完成后，必必須立即由下下一道工序加加工，而不允允許等待。導導致了工序間間存在大量的的空閑時間，，降低了設備備的使用率和和生產(chǎn)率，中間存儲策略略不同性質(zhì)的化化工產(chǎn)品(中中間品)具有有不同的中間間存儲策略：：NIS無限存儲策略略FIS有限存儲策略略NIS無中間存儲ZW零等待策略MIS混合存儲策略略成品與原料一一般為無限存存儲，不穩(wěn)定定中間品必須須采用ZW策略，而穩(wěn)定定中間品可采采用FIS(有限能力的的貯罐)或NIS(設備自身存存儲)。連續(xù)型流程工工業(yè)生產(chǎn)調(diào)度度連續(xù)型生產(chǎn)過過程適合于固固定的大批量量產(chǎn)品的生產(chǎn)產(chǎn)，其特點是是生產(chǎn)過程工工藝流程基本本不變，物料料流是連續(xù)的的。物流與能源流流的連續(xù)、操操作任務連續(xù)續(xù)執(zhí)行是連續(xù)續(xù)過程的本質(zhì)質(zhì)特點。連續(xù)過程的特特點為其物料料(中間品)可以為多個個工序使用，，并生產(chǎn)不同同的產(chǎn)品，調(diào)調(diào)度問題的目目的在于合理理調(diào)配物料，，使之能夠獲獲得最大的經(jīng)經(jīng)濟效益。由于關鍵中間間品的生產(chǎn)能能力存在瓶頸頸，可稱為有有限能力下最最大利潤問題題。連續(xù)型流程工工業(yè)生產(chǎn)調(diào)度度調(diào)度方法：優(yōu)化目標在于于充分利用有有限的生產(chǎn)能能力進行物料料的調(diào)配與平平衡。由于產(chǎn)品的變變化是由裝置置加工方案和和工藝操作條條件決定的，，生產(chǎn)過程的的一定限度內(nèi)內(nèi)的柔性是靠靠改變各裝置間物流流的分配和改變裝置運行行的工作點即工藝操作參參數(shù)來實現(xiàn)的的。前者通過過生產(chǎn)調(diào)度系系統(tǒng)來確定，，后者則通過過操作優(yōu)化，，由先進控制制來保證。實時性要求：：由于生產(chǎn)是在在連續(xù)不斷的的進行之中，，調(diào)度問題也也隨著生產(chǎn)流流程的變化而而變化，在時時間上要求調(diào)調(diào)度決策迅速速及時，與生生產(chǎn)流程保持持同步，要求求滯后時間在在一定的域值值范圍之內(nèi)。。SchedulingProblemsTypeIOnemachineMultiplemachine(Single-stage)SchedulingProblemsTypeIIMulti-stageMulti-purposeS310%90%HeatS460%Reaction3S740%SeparationReaction1Reaction3Reaction270%30%S5S6S2S1Heat過程調(diào)度類型型生產(chǎn)過程生產(chǎn)產(chǎn)調(diào)度問題可可按其產(chǎn)品生生產(chǎn)工藝的相相似程度分為為兩類：多產(chǎn)品(Multi-Stage)過程，類似于于Flowshop整個生產(chǎn)過程程分為若干個個生產(chǎn)階段，，每個階段內(nèi)內(nèi)包括若干個個并行生產(chǎn)設設備，每個產(chǎn)產(chǎn)品都需要順順序經(jīng)過所有有的生產(chǎn)階段段。多用途(Multi-Purpose)過程調(diào)度。類類似于Jobshop各個產(chǎn)品的生生產(chǎn)工藝不相相同，同一產(chǎn)產(chǎn)品生產(chǎn)存在在多個備選生生產(chǎn)路徑，其其生產(chǎn)路途并并不是預先確確定的，可以以通過設備的的組織安排來來調(diào)整，因此此其調(diào)度問題題比多產(chǎn)品過過程更復雜。。ExampleABB1CABC原生產(chǎn)過程中中，A加工時間1h，B加工時間4h，C加工時間2h，原來每批次次循環(huán)時間為為4小時，現(xiàn)增加加一個設備B1，批次循環(huán)時時間降為2小時；A工序上的等待待時間減少了了2h，C設備上空閑時時間由原來的的2小時降為零0１１２２３３45678910110１１２２３３456789SchedulingProblemsPropertyDifferentConstraints?Sequence(in)dependentsetuptimes?Release/duetimesDifferentObjectiveFunctions?Maximizethroughputoverafixedperiodoftime?Minimizecompletiontime(makespan)foragivensetofordersSchedulinginChemicalIndustryVariablebatchsizesRecyclestreams,batchsplitting/mixingDifferentstoragepolicies;sharedstoragetanksUtilities(coolingwater,steam,etc.)S310%90%HeatS460%Reaction3S740%SeparationReaction1Reaction3Reaction270%30%S5S6S2S1HeatState-TaskNetwork(STN)RepresentationS3HeatReaction11h2hSeparationS4S1S2Reaction23hS5S62hReaction3S71hSTN網(wǎng)是一個具有有兩類節(jié)點的的有向圖，分分別表示狀態(tài)態(tài)與任務，狀狀態(tài)指生產(chǎn)過過程的各種物物料，而任務務表示物料從從一種狀態(tài)轉轉換至另一狀狀態(tài)的操作，，通過各個狀狀態(tài)的存儲能能力屬性來表表示各種中間間存儲策略。。State-TaskNetwork(STN)RepresentationBsA2=BsA4=20S140%25%S3S260%S475%BIA,S1,2=8BOA,S3,4=5BIA,S2,2=12BOA,S4,4=15State-TaskNetwork(STN)RepresentationInventoryS2S30123456Time(h)Reactor1Reactor2Reactor3ColumnHeatingReaction1Reaction2Reaction3Separation0123456Time(h)優(yōu)化化調(diào)調(diào)度度模模型型－－時間間表表示示方方式式Kondili,Pantelides&Sargent(1993);Shah,Pantelides&Sargent(1993):STN-DiscretePantelides(1994):RTN-DiscreteGeneralframeworkforhandlingwiderangeofschedulingproblems.MILPwithmanybinaries.Zhang&Sargent(1995);Mockus&Reklaitis(1999):STN/RTN-ContinuousSchilling&Pantelides(1996):RTN-ContinuousGeneralMINLPformulationfordesignandscheduling.ReducestoMILPforfixedrecipes.Ierapetritou&Floudas(1998):STN––ContinuousEvent-BasedFormulationNewcontinuous-timerepresentationwithdifferenteventsforeachprocessunit.CerdaandMendez(2000);Rodriguezetal.(2001);Leeetal.(2001);Castroetal.(2001)Specialcases:Nobatchsplitting/mixing,noresourceconstraintsotherthanunits.優(yōu)化化調(diào)調(diào)度度模模型型－－時間間表表示示方方式式標準準時時間間分分布布(UDM)，以以所所有有的的工工廠廠任任務務的的最最短短操操作作時時間間為為劃劃分分標標準準等等分分時時間間，，并并假假定定所所有有操操作作(生生產(chǎn)產(chǎn)任任務務開開始始、、約約束束、、資資源源的的變變化化、、設設備備失失效效等等)均均發(fā)發(fā)生生在在各各時時間間段段的的邊邊界界上上。。非標準連連續(xù)時間間分布(NUDM)，將時間間表達為為連續(xù)變變量，時時間段的的劃分為為非均勻勻方式，，時間段段的個數(shù)數(shù)與長度度非預先先確定，，它可以以在整個個調(diào)度期期內(nèi)的任任意一點點開始。。離散事件件表示，，不存在在時間段段的劃分分，直接接以任務務和設備備上事件件的開始始、結束束時間來來表示。。FixedtimepointsFixedtimeintervalVariabletimepointsVariabletimeintervalsNocommontimeintervalsTimeRepresentations-DiscreteTimeRepresentation2hr1hr30min3hr?T=30minT1T2T3ApproximationsoftenneededConstantprocessingtimesT1T2T3012345678t(hr)2hr1hr40min3hr?T=20min012345678t(hr)TimeRepresentations-ContinuousTimeRepresentationNoapproximationsneededAccountsforvariableprocessingtimesFewertimeperiods??Fewervariables&constraintsDurationandnumberoftimeperiodsunknownT1T2T3012345678t(hr)ContinuousTimeRepresentationITimeRepresentations-Event-BasedRepresentationT1T2T3012345678t(hr)122233Event-BasedRepresentation決策變變量為為設備備事件件分配配與任任務事事件分分配在某一一事件件上使使用邏邏輯約約束使使得若若任務務事件件發(fā)生生，必必然使使得某某個設設備事事件發(fā)發(fā)生。。此方方法避避免使使用時時間分分配變變量模型為為MILP優(yōu)化模模型，，但需需要預預先估估算事事件的的個數(shù)數(shù)。時間表表達方方式差差異UDM直觀，，簡單單，將將調(diào)度度水平平分成成的等等間隔隔時間間段。。問題題可以以表示示為一一個多多時段段的MILP模型。。但模模型規(guī)規(guī)模與與加工工時間間有關關，可可能產(chǎn)產(chǎn)生計計算復復雜性性問題題。NUDM直接通通過使使用連連續(xù)變變量來來表示示所有有事件件（如如：任任務的的開始始和結結束））的發(fā)發(fā)生時時間，，而不不是分分布在在每個個人為為分成成的等等間隔隔時間間段上上，從從而達達到減減少變變量的的數(shù)目目的目目的。。問題題最后后表示示為MINLP，模型型較為為復雜雜。模模型規(guī)規(guī)模與與加工工時間間無關關。在事件件數(shù)目目遠小小于時時間段段數(shù)目目時，，NUDM的性能能明顯顯優(yōu)于于UDM。COMPUTATIONALEFFICIENCYAvoidtimepartitioningFewtimeintervalsAvoidbig-MconstraintsNoutilityconstraintsGENERALITYRecyclestreamsBatchsplitting/mixingDifferentstoragepoliciesUtilityconstraintsExample1Given:thetimehorizontheavailableunitsandstoragetanks,andtheircapacitiestheavailableutilities(steam,coolingwater)theproductionrecipe(massbalancecoefficients,utilityrequirements)thepricesofrawmaterialsandfinalproductsDetermine:thesequenceandthetimingoftaskstakingplaceineachunitthebatchsizeoftasks(i.e.theprocessingtimeandtheallocatedresources)theamountofrawmaterialspurchasedandfinalproductssoldExample2MaximizeProductionoverafixedtimehorizonExample2-RemarkExample3UnlimitedStorageFiniteStorageNoIntermediateStorageZero-WaitCoolingWaterLowPressureSteamHighPressureSteamDifferentStoragePolicies––UtilityConstraintsExample3-ResultBinaries:249Nodes:690Continuous:1,711CPUsec:22.7Constraints3,382EquipmentGanttChart-UtilityConsumptionGraph基于UDM的調(diào)調(diào)度優(yōu)優(yōu)化模模型基于UDM的調(diào)調(diào)度優(yōu)優(yōu)化模模型AssignmentConstraintsCalculationofdurationandfinishtimeoftaskiMassbalancesUtilityConstraintTighteningConstraints計劃調(diào)調(diào)度優(yōu)優(yōu)化方方法－－數(shù)學學規(guī)劃劃數(shù)學規(guī)規(guī)劃理理論包包括：：排隊網(wǎng)網(wǎng)絡方方法(QueingNetwork)線性規(guī)規(guī)劃(LinearProgramming,LP)非線性性規(guī)劃劃(Non-linearProgramming,NLP)動態(tài)規(guī)規(guī)劃(DynamicalProgramming,DP)混合整整數(shù)線線性規(guī)規(guī)劃(MixedIntegerLinearProgramming,MILP)工業(yè)中中的應應用最最為廣廣泛的的是混混合整整數(shù)規(guī)規(guī)劃。。計劃調(diào)度優(yōu)優(yōu)化方法－－數(shù)學規(guī)劃劃優(yōu)點：主要優(yōu)點是是其全局優(yōu)優(yōu)化的觀點點，對所有有的分配與與次序決策策都同時做做出，能夠夠有效地評評價方案的的質(zhì)量。對于凸問題題能夠得到到全局最優(yōu)優(yōu)解。即使使求解過程程在達到到到最佳解之之前終止，，對于凸問問題也能夠夠得到達到到全局最優(yōu)優(yōu)解的范圍圍，能夠有有效地評價價方案的質(zhì)質(zhì)量。缺點：盡管通用算算法很有效效，但也往往往不能在在可行時間間內(nèi)得到一一個可行解解。必須針針對特定問問題，開發(fā)發(fā)和使用特特殊的算法法。而且問問題發(fā)生輕輕微變化后后，原先的的算法就可可能失效。。用戶必須將將問題抽象象為形式化化的模型。。相同的問問題可以描描述為不同同的模型。。計劃調(diào)度優(yōu)優(yōu)化方法－－人工智能能生產(chǎn)過程是是高維對象象，采用規(guī)規(guī)劃模型求求解調(diào)度問問題，隨著著維數(shù)的增增加，計算算量呈指數(shù)數(shù)增長。為了提高求求解效率、、減少計算算工作量，，提出了不不少基于規(guī)規(guī)則的優(yōu)化化方法。對對于提高計計算效率起起到了重要要的作用；；采用人工智智能的方法法(如各各種搜索的的方法、專專家系統(tǒng)的的方法等)對于解解決具體的的調(diào)度問題題，不僅可可以簡化問問題，而且且能獲得合合乎實際的的滿意解。。運籌學和人人工智能融融合兩類方法采采用了不同同的模型，，不同的術術語，各有有其特點，，但都未能能真正解決決調(diào)度與計計劃決策問問題。由于生產(chǎn)環(huán)環(huán)境的動態(tài)態(tài)性，生產(chǎn)產(chǎn)領域知識識的多樣性性，調(diào)度問問題的復雜雜性，必須須將人、數(shù)數(shù)學方法和和信息技術術結合起來來研究生產(chǎn)產(chǎn)領域的管管理調(diào)度問問題。注重算法在在實際問題題中的應用用，以及實實際調(diào)度與與計劃問題題的解決。。分解BasicDecompositionIdeaComparedto““manufacturing”problems:1.Unknowntypeandnumberofbatches(tasks);unknownassignmentsoftaskstounits2.Mixingofintermediates;variablebatch-sizeandprocessingtimeTherearegoodalgorithmsforproblemswithfixedtypeandnumberoftasksandfixedassignmentsDecomposeproblemintwosubproblems1.Determinetypeandnumberoftasksandassignmentsofunitstotasks2.Solvereducedproblemwithanefficient,problem-specificalgorithm分解BasicDecompositionIdeaAlgebrax1+2x2+2x3=62x1+x2+x3=63x2+4x3=7x3+3x4+x5=8x4+2x5=8x1=2x2=1x3=1x4=2x5=3OptimizationM2M2M1Underdetermined?Manysolutions?Solve(S1)&(S2)manytimesSolutiontime:2(M1)→→210=1024sec(M1)&(M2)→→25+25=64sec1stSubproblem(M1):MathematicalProgramming→MILP2ndSubproblem(M2):ConstraintProgrammingModelingandSolutionParadigmsMathematicalProgrammingWellknown&widelyappliedEfficientalgorithmsformoderatelysizedproblems(branch-andbound,cuttingplanes)SearchisbasedonsolutionofrelaxedproblemsConstraintProgrammingNewModelingandSolutionParadigm?Developedinearly90’sinAI?VeryeffectiveforclassesofoptimizationproblemsHighlyconstrained(feasibility)problems;someschedulingproblemsSpecial““constructs”andconstraintsforclassesofproblems?Constructs:activityX,unaryresourceY?Constraints:XrequiresY(GLOBAL)A→B,A∨B(LOGIC)?HighlyExpressive?EffectivelocalsearchSearchisbasedonconstraintpropagationMathematicalvs.ConstraintProgrammingConstraintProgrammingFastalgorithmsforspecialproblemsComputationallyeffectiveforhighlyconstrained,feasibilityandmachinesequencingproblemsNoteffectiveforoptimizationproblemswithcomplexstructureandmanyfeasiblesolutionsMathematicalProgrammingIntelligentsearchstrategybutcomputationallyexpensiveforlargeproblemsComputationallyeffectiveforoptimizationproblemswithmanyfeasiblesolutionsNoteffectiveforfeasibilityproblemsandmachinesequencingproblemsMAINIDEADecomposeproblemintotwopartsUseMPforhigh-leveloptimizationdecisionsUseCPforlow-levelsequencingdecisionsProposedStrategyProductionZ*×××××UpperboundFeasiblesolution0246810Iterations

Fixno/typeoftasksandassignmentdecisions

Problemishighlyconstrained:suitableforCP

Iffeasible,obtainlowerbound

Addintegercutandcontinueuntilboundsconverge?ExpressprobleminanaggregatedMPform?UseMPtoidentifypotentiallygoodsolutions?Fixno/typeoftasks,assignmentoftaskstounits?Fixno/typeoftasksandassignmentdecisions?Problemishighlyconstrained:suitableforCP?Iffeasible,obtainlowerbound?AddintegercutandcontinueuntilboundsconvergeSolveMIPMasterProblemmaxproductions.t.RELAXATIONObtainUBSolveCPSubproblemmaxproductions.t.ALLCONSTRAINTSw/fixedno/typeoftasksObtainLB

SolveMIPMasterProblemmaxproductions.t.RELAXATIONObtainUB

Fixno/typeoftasks,assignmenttounits

Addintegercuts

Fixno/typeoftasksandassignmentdecisions

Problemishighlyconstrained:suitableforCP

Iffeasible,obtainlowerbound

AddintegercutandcontinueuntilboundsconvergeProposedFormulationSolveMIPMasterProblemmaxproductions.t.RELAXATIONObtainUBCPSubproblem(CP)maxproductions.t.ALLCONSTRAINTSw/fixedno/typeoftasksObtainLB

MIPMasterProblem(MP)maxproductions.t.SOMECONSTRAINTS

ObtainUB

Fixno/typeoftasks,assignmenttounits

Addintegercuts

Tasks ?

ActivitiesUnits ?

UnaryResourcesUtilities?

DiscreteResourcesStates ?

Reservoirs

Zic=1ifbatchcoftaskiiscarriedoutIntegerCutsGeneralizationofDecompositionFrameworkIMultipurposeBatchPlantS310%90%HeatS460%Reaction3S740%SeparationReaction1Reaction3Reaction270%30%S5S6S2S1HeatMasterMIPProblemCPSubproblemZic=1ifbatchcoftaskiiscarriedoutBic=batchsizeofbatchcoftaskiSs=inventorylevelofstatesGeneralizationofDecompositionFramework-GeneralMulti-stagePlantMasterMIPProblemCPSubproblemZic=1ifbatchcoftaskiiscarriedoutBic=batchsizeofbatchcoftaskiSs=inventorylevelofstatesT10T20T11T21T30T31F1F2F3S10S20S30S11S21S31P1P2P3T10T20T30T11T21T31T12T22T32GeneralizationofDecompositionFramework-Multi-stagePlant:demandinordersMasterMIPProblemCPSubproblemFixedbatches&batch-sizesDropcindex,BvariablesTask→(order,stage,unit):i→(o,k,j)AddassignmentconstraintT10T20T11T21T30T31F1F2F3S10S20S30S11S21S31P1P2P3T10T20T30T11T21T31T12T22T32GeneralizationofDecompositionFramework:Single-stageMasterMIPProblemCPSubproblemGeneralizationofDecompositionFrameworkIIUseproblem-specificalgorithmtosolvesubproblem(notnecessarilyCP)Minimizationofcostofmulti-stageproblemfororderswithreleaseandduetimesNordershavetobeprocessedsequentiallyonKstages,whereeachstageconsistsofMkunits.Eachorderihasreleaserianddueditimethathavetobemet,andaprocessingcostcijandprocessingtimeptijwhenprocessedonunitj.Theobjectiveistominimizethesumofprocessingcostssubjecttomeetingthereleaseandduetimes.SubproblemisatraditionalORproblem(job-shopproblem)?ThereareefficientalgorithmsUseShiftingBottleneckProcedure(AdamsandBalas,1988)tosolvethesubproblemMasterProblem:AssignmentSubproblem:SequencingGeneralizationofDecompositionFrameworkIVMILPSolverMaster(MP)Subproblem(SP)ProgramControlIntegerCut1IntegerCut2IntegerCut3ConstraintProgrammingShiftingBottleneckProcedurePreprocessing1Preprocessing2Preprocessing3ProgramControlMaster(MP)

Subproblem(SP)Data?PlantConfiguration?Units,tasks,states?Yields,massfractions?Processingtimes?Setuptimes,costs?Release/duetimesIntegratedFramework智能方法－約約束規(guī)劃highlyeffectivetechnologythatusesdomainreductionandconstraintpropagationtoefficientlysolveproblemsthatarehighlycombinatorialwithhighlylogicalcontent.Theseproblemsareusuallydifficultorimpossibletorepresentwithlinearexpressions.Constraintprogrammingusesinformationcontainedintheproblemto“prune”thesearchspace,rapidlyidentifyingfeasiblesolutions.約束規(guī)劃－Constraintprogramming約束規(guī)劃的前前提是有效地地收縮搜索空空間與求解一一個可行的或或最優(yōu)的方案案同樣重要。。約束規(guī)劃適合合于實現(xiàn)柔性性化，高效率率的調(diào)度系統(tǒng)統(tǒng)。通過為約約束傳播者封封裝不同的算算法，能把適適合特定的問問題的求解算算法考慮進去去，使得柔性性成為可能。。約束規(guī)劃適合合于處理含有有大量約束的的調(diào)度與再調(diào)調(diào)度問題。約束規(guī)劃－收縮Domainfiltering…Da={1,2},Db={1,2,3}…a<bValue1canbesafelyremovedfromDb.Constraintsareusedactivelytoremoveinconsistenciesfromtheproblem.Arcconsistency約束規(guī)劃－搜索Consistencytechniquesare(usually)incomplete.Weneedasearchalgorithmtoresolvetherest!depth-firstsearchassignavaluetothevariablepropagate=maketheproblemlocallyconsistentbacktrackuponfailure…Xin1..5≈X=1∨X=2∨∨X=3∨∨X=4∨X=5Ingeneral,searchalgorithmresolvesremainingdisjunctions!X=1∨X≠1(standardlabeling)X<3∨X≥3(domainsplitting)X<Y∨X≥Y(variableordering)constraintsatisfactiontreesearchalgorithmswhilenotsolvedandnotinfeasibledocheckconsistencyifadeadendisdetectedthentrytoescapefromdeadendelseselectvariableselectvalueforvariableendifendwhileThealgorithmCheckConsistencyprocCheckConsistencyForwardCheck;whiledomainshavechangeddo2-ConsCheck;SequencingCheck;RCPCheck;endwhileendproc智能方法-遺遺傳算法遺傳算法是一一種隨機搜索索算法，能夠夠在比較短的的時間在解空空間的不同區(qū)區(qū)域內(nèi)搜索。。由于它一次產(chǎn)產(chǎn)生一組方案案，它也適合合于使用并行行處理。方案的質(zhì)量因因為成本函數(shù)數(shù)上的界限不不能獲得，所所以估價起來來有困難。算法的收斂速速度很難預測測。智能方法－Agent自主性：根據(jù)據(jù)自己的需要要，自主地控控制其行為合作性：可與與其他Agent交互協(xié)商，通通過合作共同同完成感應性：可以以主動而有選選擇地觀察外外部環(huán)境，及及時采取動作作存在性：不斷斷觀察環(huán)境，，更新內(nèi)態(tài)，，選擇并執(zhí)行行相應的動作作MAS是由若若干具有一個個或多個目標標的Agent按照一定定的信息關系系、控制關系系以及問題求求解能力的分分布模式而組組成的，是一一個松散耦合合的Agent網(wǎng)絡，其其內(nèi)部Agent之間的的組織結構可可靈活改變。?！搬槍r間而而設計(design-to-time)”的的實時Agent調(diào)度方方案ExPlanTechExPlanTech–aproductionplanningsystemwithafunctionalityto:estimatingduedatesandresourcesrequirementsprovidingaprojectplanimplementingre-planningMultiAgentsystem(MAS)MultiAgentsystem(MAS)operator:aninstanceoftheppaandpmaclasses–projectconfigurationanddecomposition,managementoftheoverallprojectworkshop:aninstanceofthepaclass––schedulingandresourceallocationonadepartmentorCNCmachinedatabaseagent:aninstanceofthepaclass––anintegrationagent,integratesExPlanTechwithfactoryERPmaterialagent:aninstanceofthepaclass––integratesanMRP-materialresourceplanningsystemSpecialvisualizationandusermanipulationmeta-agent仿真模擬仿真模擬提供供對全部任務務，次序,先先后和時間選選擇決定的結結果的直接觀觀察，能夠以以較低的計算算成本對方案案進行快速而而詳細的分析析。仿真模擬的方方法能夠用來來測試用戶提提出的各種候候選方案。如果它與一個個較為粗略但但卻快速的調(diào)調(diào)度求解方法法結合，通過過不斷的重復復仿真與求解解，從而能夠夠實現(xiàn)在線調(diào)調(diào)度。SupplyChainCustomersRetailersDistributioncentersWarehouses/AssemblypointsProductionFacilitiesMaterialFlowOrderFlowSchedulingwithinSupplyChainIExcesscapacity:Changeoverto““idle”sometimesveryexpensive(e.g.furnaces,mills)Heavily-loadedplants:Includebacklogcosts(usuallyasmultipleofholdingcost)LongplanninghorizonsProductionTargetsDeliveriesonlyatspecifieddatesHighpeaksindemand(productiontargets)MajorTrade-off:ChangeoverCostvs.InventoryCost024681012(months)SchedulingwithinSupplyChainIIMinimizationofcostoveralongtimehorizonwithduedatesExistingModelsinChemELiteratureMathematicalProgrammingModels(95%)?Maximizationofproduction;minimizationofmakespan?Shorttimehorizons?VeryexpensivewhenaccountforduedatesOtherModels(5%)?Minimizationofmakespan?Shorttimeh