生產計劃與調度

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

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

車間作業(yè)調度的特點離散制造過程中，工件生產時間較短，工件切換加工成本低但庫存成本很高。 主要解決多個產品對設備的爭用問題。目的在于尋找最優(yōu)的設備加工任務次序，使得等待時間與切換時間最小。(1)單機調度問題(2)并行機調度問題(3)Job-shop調度問題(4)Flow-shop調度問題(5)Open-shop調度問題給定一個工件的集合P和一個機器的集合M每個工件包括多道工序Ji={Pi1…..Pik}

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

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

Flow-shop調度問題

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

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

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

對于Flow-shop，若給定某一個產品生產次序，則可以計算出所有工序的完成時間以及等待時間，而對于Job-shop，由于它存在路徑選擇問題，即使給定產品生產次序，也無法計算。實際際調調度度問問題題“因因為為瓶瓶頸頸工工序序在在不不斷斷變變化化，，我我們們如如何何知知道道瓶瓶頸頸在在那那里里？”“能能否否自自動動分分配配工工序序？？自自動動調調配配人人力力，，設設備備能能力力？”“在在插插入入急急單單時時，，能能否否自自動動根根據據目目標標重重排排計計劃劃，，一一些些定定單單自自動動延延遲遲，，一一些些定定單單自自動動提提前前？”“能否否對采采購延延遲，，生產產的延延遲，，設設備的的故障障，人人員員的效效率等等意外外快速速響應應，及及自動動進行行模擬擬，調調整？”ERP作業(yè)業(yè)計劃劃ERP(MRPII)制定作作業(yè)計計劃的的方法法一般般包括括以下下幾個個步驟驟：1、確確定批批量；；2、計計算提提前期期；3、安安排優(yōu)優(yōu)先權權，安安排作作業(yè)計計劃；；4、根根據能能力限限制調調整作作業(yè)計計劃，，再重重復前前三個個步驟驟。按預先先制定定的提提前期期，用用無限限能力力計劃劃法編編制作作業(yè)計計劃。。APS先進計計劃調調度基于約約束理理論能夠處處理生生產類類型和和工序序約束束自動的的，可可視化化的作作業(yè)計計劃TOC約束束理論論一“約束束資源源”，，““瓶頸頸”約束資資源決決定企企業(yè)有有效產產出與與庫存存企業(yè)有有效產產出受受到企企業(yè)的的生產產能力力和市市場的的需求求量的的制約約“非約約束””應與與“約約束””同步步庫存水水平只只要能能維持持“約約束””上的的物流流連續(xù)續(xù)穩(wěn)定定即可可“非約約束””的利利用程程度不不由其其本身身決定定，而而是由由系統(tǒng)統(tǒng)的““約束束”決決定的的?！凹s束束”上上一個個小時時的損損失則則是整整個系系統(tǒng)的的一個個小時時的損損失。?！胺羌s約束””節(jié)省省的一一個小小時無無益于于增加加系統(tǒng)統(tǒng)有效效產出出。APS約束束類型型資源約約束a，單單一資資源b，無無限資資源c，并并發(fā)資資源d，共共享資資源e，，可調調整共共享資資源順序約約束庫存約約束特別約約束APS計劃劃算法法一有限能能力計計劃a，算算法順順序計計劃b，向向前順順序計計劃c，向向后順順序計計劃b，雙雙向計計劃或或瓶頸頸計劃劃基于模模擬的的計劃劃基于模模擬規(guī)規(guī)則產產生一一個優(yōu)優(yōu)化的的計劃劃APS計劃劃算法法二向前順順序計計劃固固定了了開始始時間間，決決定結結束時時間，，也許許會違違反完完成日日期。。向后順順序計計劃固固定結結束時時間，，決定定開始始時間間，產產生一一個不不會延延遲的的計劃劃，然然而，，計劃劃也許許有不不可行行的開開始時時間。。雙向計計劃或或瓶頸頸計劃劃，先先安排排約束束資源源上加加工的的關鍵鍵件的的生產產進度度計劃劃，以以約束束資源源為基基準，，把約約束資資源之之前、、之間間、之之后的的工序序分別別按拉拉動、、工藝藝順序序、推推動的的方式式排定定，并并進行行一定定優(yōu)化化，接接下來來編制制非關關鍵件件的作作業(yè)計計劃。。特點：：與ERP不不同，，瓶頸頸算法法順序序計劃劃中的的提前前期是是批量量、優(yōu)優(yōu)先權權和其其它許許多因因素的的函數(shù)數(shù)，是是編制制作業(yè)業(yè)計劃劃產生生的結結果。。啟發(fā)式式規(guī)則則主要的的優(yōu)點點是啟啟發(fā)式式規(guī)則則往往往利用用與該該問題題相關關的知知識，，因此此，在在通常常情況況下能能夠在在較短短的時時間內內得到到較好好方案案。啟發(fā)式式規(guī)則則無法法分析析與判判斷其其方案案的質質量。。APS中的的啟發(fā)發(fā)式規(guī)規(guī)則1、預預先先確定定任務務的參參數(shù)類類規(guī)則則如升序序定單單屬性性值，，優(yōu)先先級、、反反向優(yōu)優(yōu)先級級2、最最小小化任任務延延遲類類規(guī)則則如先到到先服服務3、最最小小化任任務流流程時時間類類規(guī)則則適用于于最小小時間間的控控制，，提高高工時時利用用率。。如完完成日日期4、最最大大設備備能力力類規(guī)規(guī)則適用于于是計計劃設設備效效率來來最大大化整整個設設備的的生產產能力力。如如閑散散時間間5、定定制制規(guī)則則流程工工業(yè)調調度特特點產品配配方、、產品品混合合、物物料平平衡等等問題題需要考考慮主主產品品、副副產品品、協(xié)協(xié)產品品、半半成品品循環(huán)和和回流流熱蒸汽汽、冷冷凍水水、壓壓縮空空氣、、水、、電等等動力力能源源輔助助系統(tǒng)統(tǒng)也應應納入入調度度生產調調度流程工工業(yè)中中生產產過程程的柔柔性是是靠改改變各各裝置置間的的物流流分配配和生生產裝裝置的的工作作點來來實現(xiàn)現(xiàn)的，，必須須由先先進的的在線線優(yōu)化化、控控制技技術來來保證證。靜態(tài)調調度：：它考考慮工工廠生生產資資源優(yōu)優(yōu)化分分配，，屬于于在確確定性性環(huán)境境下靜靜態(tài)組組合優(yōu)優(yōu)化問問題；；動態(tài)調調度：：它是是在生生產過過程出出現(xiàn)各各種動動態(tài)變變化因因素時時進行行的再再調度度。靜態(tài)調調度主要的的決策策變量量為：：各個個操作作的開開始時時間，，持續(xù)續(xù)時間間、執(zhí)執(zhí)行的的單元元設備備，以以及容容量。。調度期期變化化范圍圍為2－3天至至2－－6月月。受受到單單元設設備的的操作作周期期、產產品的的生產產周期期以及及原料料準備備所需需的時時間影影響。。聯(lián)系：：產品生生產率率和產產品質質量指指標直直接由由調度度下達達至先先進控控制。。先進控控制將將生產產過程程的狀狀態(tài)、、過程程模型型的參參數(shù)的的更新新反饋饋至生生產調調度。。動態(tài)調度動態(tài)調度又又稱再調度度：處理突突發(fā)事件，，如某項生生產控制指指標超出臨臨界值，設設備的故障障、資源突突然短缺以以及能源供供應中斷等等。它在生生產過程中中出現(xiàn)的意意外事件進進行，保證證生產的平平穩(wěn)進行。。動態(tài)調度依依據生產計計劃和實際際工況響應應進行調度度，與靜態(tài)態(tài)調度不同同，需要考考慮實時性性。動態(tài)生產調調度對生產產運行控制制的性能具具有重大影影響，但大大規(guī)模的具具有工業(yè)意意義的動態(tài)態(tài)生產調度度問題由于于其復雜性性，單純依依靠人（即即使是有經經驗的生產產調度人員員）來解決決已被實踐踐經驗證明明是不現(xiàn)實實的。最優(yōu)調度問問題描述給定：生產過程的的工藝、設設備及全部部相關信息息；一個感興趣趣的時間段段；用戶定單及及原料到貨貨信息或生生產計劃信信息決定：每個設備單單元的操作作時間（例例如，在感感興趣的時時間段內設設備在每個個時刻執(zhí)行行哪個任務務）；工廠廠的物料流流。使得：目標函數(shù)最最優(yōu)。生產過程的的約束約束條件：：生產調度受受到諸多因因素的限制制，一般有有：產品的的投產期，，交貨期（（完成期）），生產能能力，加工工順序，加加工設備和和原料的可可用性，批批量大小，，加工路徑徑，成本限限制等，這這些都是所所謂的約束束條件。硬約束與軟軟約束：硬約束是必必須要滿足足的，如交交貨期，生生產能力等等，而軟約約束只需達達到一定的的滿意度即即可，如生生產成本等等。這些約約束一般情情況是確定定的，在進進行調度時時大都作為為確定性因因素考慮。。不確定性因因素：設備故障，，原料供應應變化，生生產任務變變化等非正正常情況，，都是事先先不能預見見的，大都都作為不確確定性因素素考慮。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)化目標生產調度的的性能指標標可以是成成本最低、、庫存費用用最少（減減少流動資資金占用））、生產周周期最短、、生產切換換最少、設設備利用率率最高、三三廢最少等等。生產調調度的性能能指標大致致可以歸結結為三類：：最大能力指指標成本指標客戶滿意度度指標間歇型生產產過程調度度間歇型生產產過程適用用于中小批批量且產出出價值較高高的產品。。一般是由一一些通用型型的設備組組成，通過過對設備、、原材料等等資源的共共享，在同同一組設備備上實現(xiàn)多多種產品的的生產，并并且可以實實現(xiàn)較為復復雜的合成成過程。間歇型生產產過程的靈靈活性，對對生產調度度提出了更更高的要求求。由于設備可可由多項流流程共享，，工藝描述述與設備描描述是不同同且獨立的的，在設備備管理的同同時還亟需需工藝管理理。為了在在特定的時時間段上將將設備分配配給特定的的工藝流程程，調度成成為最重要要的功能。。中間貯罐協(xié)協(xié)調工序間間差異中間貯罐：：某些需要較較長加工時時間的工序序成為生產產過程的瓶瓶頸，它屬屬于時間瓶瓶頸。為解解決瓶頸問問題，往往往在工序間間加入中間間貯罐，使使得上、下下游的物料料流分離，，協(xié)調工序序間生產能能力、加工工時間差異異。中間貯罐并并不能夠完完全地解決決時間與能能力瓶頸。。由于中間產產品往往具具有不穩(wěn)定定的特點，，它在加工工完成后，，必須立即即由下一道道工序加工工，而不允允許等待。。導致了工工序間存在在大量的空空閑時間，，降低了設設備的使用用率和生產產率，中間存儲策策略不同性質的的化工產品品(中間品品)具有不不同的中間間存儲策略略：NIS無限存儲策策略FIS有限存儲策策略NIS無中間存儲儲ZW零等待策略略MIS混合存儲策策略成品與原料料一般為無無限存儲，，不穩(wěn)定中中間品必須須采用ZW策略，而穩(wěn)穩(wěn)定中間品品可采用FIS(有限能力力的貯罐)或NIS(設備自身身存儲)。。連續(xù)型流程程工業(yè)生產產調度連續(xù)型生產產過程適合合于固定的的大批量產產品的生產產，其特點點是生產過過程工藝流流程基本不不變，物料料流是連續(xù)續(xù)的。物流與能源源流的連續(xù)續(xù)、操作任任務連續(xù)執(zhí)執(zhí)行是連續(xù)續(xù)過程的本本質特點。。連續(xù)過程的的特點為其其物料(中中間品)可可以為多個個工序使用用，并生產產不同的產產品，調度度問題的目目的在于合合理調配物物料，使之之能夠獲得得最大的經經濟效益。。由于關關鍵中中間品品的生生產能能力存存在瓶瓶頸，，可稱稱為有有限能能力下下最大大利潤潤問題題。連續(xù)型型流程程工業(yè)業(yè)生產產調度度調度方方法：：優(yōu)化目目標在在于充充分利利用有有限的的生產產能力力進行行物料料的調調配與與平衡衡。由于產產品的的變化化是由由裝置置加工工方案案和工工藝操操作條條件決決定的的，生生產過過程的的一定定限度度內的的柔性性是靠靠改變變各裝置置間物物流的的分配配和改變變裝裝置置運運行行的的工工作作點點即工工藝藝操操作作參參數(shù)數(shù)來來實實現(xiàn)現(xiàn)的的。。前前者者通通過過生生產產調調度度系系統(tǒng)統(tǒng)來來確確定定，，后后者者則則通通過過操操作作優(yōu)優(yōu)化化，，由由先先進進控控制制來來保保證證。。實時時性性要要求求：：由于于生生產產是是在在連連續(xù)續(xù)不不斷斷的的進進行行之之中中，，調調度度問問題題也也隨隨著著生生產產流流程程的的變變化化而而變變化化，，在在時時間間上上要要求求調調度度決決策策迅迅速速及及時時，，與與生生產產流流程程保保持持同同步步，，要要求求滯滯后后時時間間在在一一定定的的域域值值范范圍圍之之內內。。SchedulingProblemsTypeIOnemachineMultiplemachine(Single-stage)SchedulingProblemsTypeIIMulti-stageMulti-purposeS310%90%HeatS460%Reaction3S740%SeparationReaction1Reaction3Reaction270%30%S5S6S2S1Heat過程程調調度度類類型型生產產過過程程生生產產調調度度問問題題可可按按其其產產品品生生產產工工藝藝的的相相似似程程度度分分為為兩兩類類：：多產產品品(Multi-Stage)過程程，，類類似似于于Flowshop整個個生生產產過過程程分分為為若若干干個個生生產產階階段段，，每每個個階階段段內內包包括括若若干干個個并并行行生生產產設設備備，，每每個個產產品品都都需需要要順順序序經經過過所所有有的的生生產產階階段段。。多用用途途(Multi-Purpose)過程程調調度度。。類類似似于于Jobshop各個產品品的生產產工藝不不相同，，同一產產品生產產存在多多個備選選生產路路徑，其其生產路路途并不不是預先先確定的的，可以以通過設設備的組組織安排排來調整整，因此此其調度度問題比比多產品品過程更更復雜。。ExampleABB1CABC原生產過過程中，，A加工時間間1h，B加工時間間4h，C加工時間間2h，原來每每批次循循環(huán)時間間為4小時，現(xiàn)現(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網是一個個具有兩兩類節(jié)點點的有向向圖，分分別表示示狀態(tài)與與任務，，狀態(tài)指指生產過過程的各各種物料料，而任任務表示示物料從從一種狀狀態(tài)轉換換至另一一狀態(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)化調度度模型－－時間表示示方式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)化調度度模型－－時間表示示方式標準時間間分布(UDM)，以所所有的工工廠任務務的最短短操作時時間為劃劃分標準準等分時時間，并并假定所所有操作作(生產產任務開開始、約約束、資資源的變變化、設設備失效效等)均均發(fā)生在在各時間間段的邊邊界上。。非標準連連續(xù)時間間分布(NUDM)，將時間間表達為為連續(xù)變變量，時時間段的的劃分為為非均勻勻方式，，時間段段的個數(shù)數(shù)與長度度非預先先確定，，它可以以在整個個調度期期內的任任意一點點開始。。離散事件件表示，，不存在在時間段段的劃分分，直接接以任務務和設備備上事件件的開始始、結束束時間來來表示。。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直觀，，簡單單，將將調度度水平平分成成的等等間隔隔時間間段。。問題題可以以表示示為一一個多多時段段的MILP模型。。但模模型規(guī)規(guī)模與與加工工時間間有關關，可可能產產生計計算復復雜性性問題題。NUDM直接通通過使使用連連續(xù)變變量來來表示示所有有事件件（如如：任任務的的開始始和結結束））的發(fā)發(fā)生時時間，，而不不是分分布在在每個個人為為分成成的等等間隔隔時間間段上上，從從而達達到減減少變變量的的數(shù)目目的目目的。。問題題最后后表示示為MINLP，模型較為為復雜。模模型規(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.7 Constraints3,382EquipmentGanttChart-UtilityConsumptionGraph基于UDM的調度優(yōu)優(yōu)化模型基于UDM的調度優(yōu)優(yōu)化模型AssignmentConstraintsCalculationofdurationandfinishtimeoftaskiMassbalancesUtilityConstraintTighteningConstraints計劃調度優(yōu)優(yōu)化方法－－數(shù)學規(guī)劃劃數(shù)學規(guī)劃理理論包括：：排隊網絡方方法(QueingNetwork)線性規(guī)劃(LinearProgramming,LP)非線性規(guī)劃劃(Non-linearProgramming,NLP)動態(tài)規(guī)劃(DynamicalProgramming,DP)混合整數(shù)線線性規(guī)劃(MixedIntegerLinearProgramming,MILP)工業(yè)中的應應用最為廣廣泛的是混混合整數(shù)規(guī)規(guī)劃。計劃調度優(yōu)優(yōu)化方法－－數(shù)學規(guī)劃劃優(yōu)點：主要優(yōu)點是是其全局優(yōu)優(yōu)化的觀點點，對所有有的分配與與次序決策策都同時做做出，能夠夠有效地評評價方案的的質量。對于凸問題題能夠得到到全局最優(yōu)優(yōu)解。即使使求解過程程在達到到到最佳解之之前終止，，對于凸問問題也能夠夠得到達到到全局最優(yōu)優(yōu)解的范圍圍，能夠有有效地評價價方案的質質量。缺點：盡管通用算算法很有效效，但也往往往不能在在可行時間間內得到一一個可行解解。必須針針對特定問問題，開發(fā)發(fā)和使用特特殊的算法法。而且問問題發(fā)生輕輕微變化后后，原先的的算法就可可能失效。。用戶必須將將問題抽象象為形式化化的模型。。相同的問問題可以描描述為不同同的模型。。計劃調度優(yōu)優(yōu)化方法－－人工智能能生產過程是是高維對象象，采用規(guī)規(guī)劃模型求求解調度問問題，隨著著維數(shù)的增增加，計算算量呈指數(shù)數(shù)增長。為了提高求求解效率、、減少計算算工作量，，提出了不不少基于規(guī)規(guī)則的優(yōu)化化方法。對對于提高計計算效率起起到了重要要的作用；；采用人工智智能的方法法(如各各種搜索的的方法、專專家系統(tǒng)的的方法等)對于解解決具體的的調度問題題，不僅可可以簡化問問題，而且且能獲得合合乎實際的的滿意解。。運籌學和人人工智能融融合兩類方法采采用了不同同的模型，，不同的術術語，各有有其特點，，但都未能能真正解決決調度與計計劃決策問問題。由于生產環(huán)環(huán)境的動態(tài)態(tài)性，生產產領域知識識的多樣性性，調度問問題的復雜雜性，必須須將人、數(shù)數(shù)學方法和和信息技術術結合起來來研究生產產領域的管管理調度問問題。注重算法在在實際問題題中的應用用，以及實實際調度與與計劃問題題的解決。。分解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)柔性性化，高效率率的調度系統(tǒng)統(tǒng)。通過為約約束傳播者封封裝不同的算算法，能把適適合特定的問問題的求解算算法考慮進去去，使得柔性性成為可能。。約束規(guī)劃適合合于處理含有有大量約束的的調度與再調調度問題。約束規(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ū)域內搜索。。由于它它一次次產生生一組組方案案，它它也適適合于于使用用并行行處理理。方案的的質量量因為為成本本函數(shù)數(shù)上的的界限限不能能獲得得，所所以估估價起起來有有困難難。算法的的收斂斂速度度很難難預測測。智能方方法－－Agent自主性性：根根據自自己的的需要要，自自主地地控制制其行行為合作性性：可可與其其他Agent交互協(xié)協(xié)商，，通過過合作作共同同完成成感應性性：可可以主主動而而有選選擇地地觀察察外部部環(huán)境境，及及時采采取動動作存在性性：不不斷觀觀察環(huán)環(huán)境，，更新新內態(tài)態(tài)，選選擇并并執(zhí)行行相應應的動動作MAS是由由若干干具有有一個個或多多個目目標的的Agent按按照一一定的的信息息關系系、控控制關關系以以及問問題求求解能能力的的分布布模式式而組組成的的，是是一個個松散散耦合合的Agent網絡絡，其其內部部Agent之之間的的組織織結構構可靈靈活改改變。?！搬槍r間間而設設計(design-to-time)””的實實時Agent調度度方案案ExPlanTechExPlanTech–aproductionplanningsystemwithafunctionalityto:estimatingduedatesandresourcesrequirementsprovidingaprojectplanimplementingre-planningMultiAgentsystem(MAS)MultiAgentsystem(MAS)operator:aninstanceoftheppaandpmaclasses––projectconfigurationanddecomposition,managementoftheoverallprojectworkshop:aninstanceofthepaclass––schedulingandresourceallocationonadepartmentorCNCmachinedatabaseagent:aninstanceofthepaclass––anintegrationagent,integratesExPlanTechwithfactoryERPmaterialagent:aninstanceofthepaclass––integratesanMRP-materialresourceplanningsystemSpecialvisualizationandusermanipulationmeta-agent仿真模模擬仿真模模擬提提供對對全部部任務務，次次序,先后后和時時間選選擇決決定的的結果果的直直接觀觀察，，能夠夠以較較低的的計算算成本本對方方案進進行快快速而而詳細細的分分析。。仿真模模擬的的方法法能夠夠用來來測試試用戶戶提出出的各各種候候選方方案。。如果它它與一一個較較為粗粗略但但卻快快速的的調度度求解解方法法結合合，通通過不不斷的的重復復仿真真與求求解，，從而而能夠夠實現(xiàn)現(xiàn)在線線調度度。SupplyChainCustomersRetailersDistributioncentersWarehouses/AssemblypointsProductionFacilitiesMaterialFlowOrderFlowSchedulingwithinSupplyChainIExcesscapacity:Changeoverto“idle””sometimesveryexpensive(e.g.furnaces,mills)Heavily-loadedplants:Includebacklogcosts(usuallyasmultipleofholdingcost)LongplanninghorizonsProductionTargetsDeliveriesonlyatspecifieddatesHighpeaksindemand(productiontargets)MajorTrade-off:ChangeoverCostvs.InventoryCost024681012(months)SchedulingwithinSupplyChainIIMinimizationofcostoveralongtimehorizonwithduedatesExistingModelsinChemELiteratureMathematicalProgrammingModels(95%)?Maximizationofproduction;mi