譯文--離散優(yōu)化方法及其在規(guī)劃調(diào)度集成中的作用

1、<p>　　本科畢業(yè)論文外文翻譯</p><p>　　離散優(yōu)化方法及其在規(guī)劃調(diào)度集成中的作用</p><p>　　Computers and chemical engineering, 2001, 25 pages150-168</p><p>　　Ignacio E. Grossmann1, Susara A. van den Heever and I

2、iro Harjunkoski</p><p><b>　　摘要</b></p><p>　　流程運作、物流和供應(yīng)鏈管理的改善，需要規(guī)劃調(diào)度優(yōu)化模型新的的發(fā)展。本文首先回顧了在流程運作中規(guī)劃調(diào)度模型的幾種主要類型并且建立了這些問題的基本的數(shù)學(xué)結(jié)構(gòu)模型。我們將會看到，這些模型在本質(zhì)上易受時間分布的影響（離散或連續(xù)），并且往往是受離散型時間分布決定。然后，我們簡要回顧了混

3、合整數(shù)線性、非線性規(guī)劃，離散規(guī)劃和約束規(guī)劃的發(fā)展近況以及解決這些問題的基本的技術(shù)。本論文提出了規(guī)劃調(diào)度的一種基本公式來說明本文討論的模型和方法。</p><p>　　關(guān)鍵詞:規(guī)劃；調(diào)度；優(yōu)化；混合整數(shù)規(guī)劃 </p><p><b>　　1 引言</b></p><p>　　過去5—7年化學(xué)工藝規(guī)劃調(diào)度優(yōu)化模型的發(fā)展引起了巨大的關(guān)注。一個主要原因

4、是業(yè)界意識到，在化學(xué)工藝中通過改善制造物流可以降低巨大潛在的成本。降低成本例子包括更低的庫存，更低的轉(zhuǎn)換成本，降低產(chǎn)量不足。規(guī)劃和調(diào)度帶來的利益，進一步加強了業(yè)界改善供應(yīng)鏈動態(tài)管理的目標。最終，大規(guī)模計算和數(shù)學(xué)規(guī)劃的優(yōu)勢促進了將這些技術(shù)應(yīng)用于規(guī)劃調(diào)度問題。</p><p>　　本文的目的是提供基于規(guī)劃調(diào)度模型優(yōu)化的概述，回顧解決這類問題可行的解決策略和數(shù)學(xué)規(guī)劃方法。最后，我們列舉了三個例子來說明本文討論的一些技術(shù)

5、的應(yīng)用。</p><p>　　1.1 規(guī)劃和調(diào)度的回顧 </p><p>　　隨著時間的推移，規(guī)劃和調(diào)度處理分配現(xiàn)有資源成為一種集成任務(wù)。工藝系統(tǒng)中，規(guī)劃調(diào)度指設(shè)備的分配策略或者是為制造一個或多個產(chǎn)品進行人力資源的教育任務(wù)。規(guī)劃與調(diào)度的區(qū)別并不總是明確的。然而，一般來講他們的不同在于，規(guī)劃處理較長時間跨度（如數(shù)周、數(shù)個月），主要涉及高層次的如投資、新的設(shè)施和生產(chǎn)水平的決策。另一方面，調(diào)度處

6、理較短的時間跨度（如數(shù)天、 數(shù)星期），重點是處理排序的決策。規(guī)劃在利潤最大化中場扮演重要角色，而調(diào)度強調(diào)確定排序的可行性或者在最短的時間完成要求的任務(wù)。因此，往往規(guī)劃比調(diào)度發(fā)揮更大的經(jīng)濟因素作用。應(yīng)當指出的是，然而，通過規(guī)劃和調(diào)度同步的決策，計劃與調(diào)度的區(qū)別越來越多的模糊，特別是文中供應(yīng)鏈優(yōu)化方面的問題。</p><p><b>　　1.2 規(guī)劃 </b></p><p&

7、gt;　　本文并沒有詳細的描述規(guī)劃和調(diào)度。在這一節(jié)，我們因此主要為讀者列出一些關(guān)于特殊規(guī)劃問題和問題類型的論文，以及規(guī)劃問題本質(zhì)的一般性討論。雖然沒有單獨適用于所有規(guī)劃類型問題的論述，但可以在運籌學(xué)中特殊規(guī)劃問題資料中找到這方面的論述。Erengucetal（1999年）論述了關(guān)于集成生產(chǎn)和供應(yīng)鏈分配規(guī)劃的工作。他們討論供應(yīng)鏈的不同階段，給出了一些基本的公式和來自運籌學(xué)界的嚴格的評估相關(guān)的文獻。其他論述討論了貨運運輸模型（Crainic

8、 and Laporte，1997），電力設(shè)施規(guī)劃的優(yōu)化方法（Hobbs，1995），考慮隨機或動態(tài)問題特性的戰(zhàn)略設(shè)施定位方法（Owen and Daskin，1998）。在化學(xué)工程學(xué)中，在（Shah，1998）中可以找到用于單一和多站點規(guī)劃與調(diào)度的論述，并且可以在Reklaitis（1991，1992）和 Rippin（1993）中，找到批量/半連續(xù)設(shè)備規(guī)劃與調(diào)度的論述。</p><p>　　依據(jù)相關(guān)的決策和

9、考慮的時間限度可將規(guī)劃問題大致可分為戰(zhàn)略、戰(zhàn)術(shù)或業(yè)務(wù)。戰(zhàn)略規(guī)劃涵蓋了最長的時間限度，通常為在一至數(shù)年，其決策在整個組織范圍并且關(guān)注與大的投資。戰(zhàn)略規(guī)劃問題包括設(shè)施選址問題（e.g.Mazzola and Neebe，1999），化學(xué)平臺投資規(guī)劃（e.g. Iyer et al., 1998; Van den Heever and Grossmann, 2000），流程網(wǎng)絡(luò)長期規(guī)劃（e.g. Sahinidis et al., 1989）

10、，這種規(guī)劃在考慮長遠投資決策是非常重要的。戰(zhàn)術(shù)規(guī)劃通常是幾個月到一年的時間跨度，其決策包括生產(chǎn)、庫存和分配。中期生產(chǎn)計劃或供應(yīng)鏈規(guī)劃是一個很好的戰(zhàn)術(shù)規(guī)劃例子，（e.g. Bok et al., 2000; McDonald and Karimi,1997; Perea et al., 2000; Dimitriadis et al., 1997）。業(yè)務(wù)規(guī)劃通常是一個星期到三個月的時間跨度，涉及的決策為實際的操作和資源分配。應(yīng)用包括設(shè)施系

11、統(tǒng)的運作規(guī)劃（(e.g.Iyer and Grossmann, 1998b）和再運作規(guī)劃(e.g. Mo</p><p>　　在不確定的條件，規(guī)劃模型分為確定性或者是隨機性。確定性模型假設(shè)價格、需求和可能性的預(yù)測是確定的，這些模型在短期規(guī)劃與調(diào)度中是足夠的。但是在較長的時間跨度下復(fù)合的不確定的模型被認為是更重要的。然而，盡管不確定性是復(fù)合的，確定性模型依舊是有用的，因為它們可以用于分析不確定參數(shù)的不同場景，這種參

12、數(shù)沒有額外的復(fù)雜性與隨機模型。此外，確定性模型是構(gòu)成不確定性模型的基礎(chǔ)。隨機模型包括或明確的不確定性概率分布，而且往往由于其復(fù)雜性需要專門的解決方案方法。已將出版了大量的關(guān)于不確定的流程規(guī)劃方面的文章。因此，我們請讀者閱讀新近的一些出版物：Liu和Sahinidis（1996）提出了一個不確定性隨機規(guī)劃的兩階段規(guī)劃方法。這些作者先考慮離散隨機參數(shù)和開發(fā)了分解算法解決方案，然后，他們將其應(yīng)用于連續(xù)隨機變量。 Ieraetritou et.

13、al.（1996）討論不確定設(shè)計與規(guī)劃的建模問題，提出了一種針對聯(lián)合多期/隨機規(guī)劃問題分解算法。Clay 和 Grossmann（1997）提出需求和成本不確定的規(guī)劃問題，并借助不確定因素分布函數(shù)計算這些有限離散概率。他們還提出一個迭代聚合/分解算法，該算法針對兩階段隨</p><p><b>　　1.3 調(diào)度</b></p><p>　　在Rippin（1993）中

14、能找到全面的論述調(diào)度，Rippin提出強調(diào)設(shè)計、規(guī)劃和調(diào)度的批量工藝系統(tǒng)工程的基本地位。Reklaitis（1991，1992）對批量處理運作作了全面的論述。他的主要重點是描述調(diào)度問題的基本組成部分以及現(xiàn)有的解決方法。Pekny 和 Zentner（1994）總結(jié)了基本的調(diào)度技術(shù)，這種技術(shù)與計算機技術(shù)相結(jié)合。Grossmann et al. (1996)提供了一個混合整數(shù)優(yōu)化技術(shù)批處理調(diào)度的概述，其強調(diào)混合整數(shù)線性（混合整數(shù)線性規(guī)劃）和

15、混合整數(shù)非線性（混合整數(shù)非線性規(guī)劃）問題一般的目的方法。Pinto 和Grossmann (1998)提出了調(diào)度問題的分類和整數(shù)、混合整數(shù)約束的主要類型的特點，這些約束用于作業(yè)排序決策。Shah（1998）進行了單一和多點調(diào)度方法的概述，而Pekny and Reklaitis (1998)提出了關(guān)于調(diào)度問題計算復(fù)雜性的論述。相似的設(shè)備和相連的單元顯示了設(shè)備的典型性。在系列設(shè)備，產(chǎn)品按照同一生產(chǎn)路線，因此它可以確定工廠車間的具體方向。網(wǎng)

16、絡(luò)的任意拓撲結(jié)構(gòu)往往會出現(xiàn)產(chǎn)品低相似性和或設(shè)備互聯(lián)。大多數(shù)方法不處理大量確定性平衡，而是，產(chǎn)</p><p>　　建模調(diào)度的一個主要問題是要考慮時間。最普遍是一個持續(xù)的時域。 如果是一個離散時間，時間間隔將是均衡的和固定的。在這種情況下，需要利用充分大數(shù)量的時間間隔來說明原始問題的近似值。然而，離散時間的一個優(yōu)點是容易控制資源量和庫存水平。在連續(xù)時間方案里，通?？梢约俣ㄒ粋€很小數(shù)目時間或時間事件，盡管往往引進非線

17、性在模型。</p><p>　　另一個車間調(diào)度問題是處理中間存儲。有四種不同轉(zhuǎn)移策略：零等待（ZW），無中間存儲（NIS），有限中間存儲（FIS）的和無限中間存儲（UIS）（Ku et al，1987）。 重要的是有限中間存儲最一般情況。然而，另外三種主要優(yōu)勢是沒有必要的模型庫存水平。在車間進程調(diào)度，加工任務(wù)需要設(shè)備和人力資源。設(shè)備可能包括，例如，蒸汽，電力，冷卻水等，在一些調(diào)度應(yīng)用中，除了裝備，有限的資源是

18、有限的需要 。資源約束調(diào)度問題是艱難的的，因為這樣的事實：除了達到產(chǎn)品要求的單位有效分配，還需要考慮可行離散優(yōu)化方法及其在規(guī)劃和調(diào)度整合中的作用 。</p><p><b>　　圖2：網(wǎng)絡(luò)數(shù)值</b></p><p>　　短期調(diào)度相關(guān)的工廠，必須滿足不同需求的個人客戶訂單模式。在這種情況下，產(chǎn)品對每個要求給出一個關(guān)聯(lián)的訂單，設(shè)置某些產(chǎn)品的數(shù)量和截止日期。與此相反，循環(huán)

19、調(diào)度與穩(wěn)定的市場經(jīng)營相關(guān)，這種情況下產(chǎn)品需求穩(wěn)定不變，這使得調(diào)度更加簡化。當切換產(chǎn)品，甚至在相同的產(chǎn)品有一個或多個批次，單元可能為達到產(chǎn)品質(zhì)量需要重新安裝。改變多少根據(jù)工廠里單元和產(chǎn)品的性質(zhì)而定。依耐改變的排序是最普遍和困難的局面，每一個連續(xù)可能引起不同的時間或成本的要求。例如，可能需要轉(zhuǎn)換每批次或之后的若干批，無論對產(chǎn)品的性質(zhì)如何。</p><p>　　從所有的化學(xué)工程文獻已提出的調(diào)度模型中，最一般模式是由Ko

20、ndili等人提出的（1993），這種模型解決了一批業(yè)務(wù)短期調(diào)度。混合整數(shù)線性規(guī)劃模型的功能包括以下內(nèi)容：（一）加工任務(wù)無須固定，（二）可處理可變大小批次與混合的可能性， （三）不同的中間儲存和轉(zhuǎn)移政策可以適應(yīng)，以及資源的限制。在由Kondili等工作中（1993），一個主要假設(shè)是時域離散，但這種做法往往意味著必須對原始數(shù)據(jù)執(zhí)行一些四舍五入。此外，轉(zhuǎn)換時間通常被忽略，因為它們不能輕易處理這一模式。由Kondili等人（1993）提出混合

21、整數(shù)線性規(guī)劃模型的重要方面是任務(wù)網(wǎng)（STN）的展現(xiàn)。</p><p>　　圖3：最優(yōu)圖網(wǎng)絡(luò)計劃。</p><p>　　該網(wǎng)絡(luò)兩種類型的節(jié)點：（一）國家對應(yīng)的節(jié)點飼料，中間產(chǎn)品和最終產(chǎn)品的;（二）任務(wù)節(jié)點代表處理步驟。圖2提供了一個狀態(tài)工作網(wǎng)絡(luò)的例子，應(yīng)當指出該設(shè)備是分開考慮。一般假定每個單元可以執(zhí)行數(shù)個STN任務(wù)。由此產(chǎn)生的混合整數(shù)線性規(guī)劃模型決定了作業(yè)時間、設(shè)備操作、材料流動。我們的目標

22、是獲得利潤最大化功能。圖3顯示了在圖2示例最優(yōu)調(diào)度的結(jié)果。應(yīng)當指出，通過Shah et al（1993）改進的混合整數(shù)線性規(guī)劃，可以解決與之相當大的問題。此外，Pantelides（1994）提出的資源任務(wù)網(wǎng)絡(luò)（RTN），從而導(dǎo)致更緊湊型模式，與STN相比，盡管它實際上是同等的，有趣的是，在上文圖1，無論是STN和RTN都可以處理任意拓撲結(jié)構(gòu)的網(wǎng)絡(luò)，可以處理一般的流程平衡，基于離散型的，能夠處理所有類型和資源的限制，并處理短期變化要求。

23、</p><p><b>　　2 數(shù)學(xué)規(guī)劃 </b></p><p>　　規(guī)劃和調(diào)度問題一般分為離散/連續(xù)優(yōu)化問題，因而我們找到一些目前條件下主要的數(shù)學(xué)規(guī)劃技術(shù)的討論。這些優(yōu)化問題以代數(shù)形式表現(xiàn)，它們對應(yīng)于混合整數(shù)優(yōu)化，問題有以下形式： minZ=f (x,y) (MIP)</p><p&

24、gt;　　條件 </p><p><b>　　h(x,y)=0</b></p><p><b>　　g(x,y)<=0</b></p><p>　　x∈X,y∈{0,1}m </p><p>　　這里f（x，y）是目標函數(shù)（如成本）， H（x，y）= 0是描述系統(tǒng)性能

25、的方程（物料平衡，生產(chǎn)率），而g（x，y）《=0為可行的計劃和調(diào)度約束的不等式。 變量x是連續(xù)的，一般對應(yīng)狀態(tài)變量，而y是離散變量， 通常僅限于采取0-1值，如設(shè)備分配和作業(yè)排序。如果所有的對應(yīng)于線性混合整數(shù)規(guī)劃是線性的（MILP）。如果沒有0-1變量，混合整數(shù)規(guī)劃根據(jù)函數(shù)是否為線性分成非線性規(guī)劃或線性規(guī)劃。</p><p>　　在例如GAMS (Brookeet al., 1992)和AMPL (Fourer

26、et al., 1992)建模系統(tǒng)下，能夠有效的實施主要數(shù)學(xué)規(guī)劃的問題的成型和解決辦法。盡管這些系統(tǒng)需要對模型能夠清晰的用代數(shù)形式表達出來，他們的優(yōu)點是自動解決各類型的問題。他們還執(zhí)行自動分化并允許有索引的方程使用，而且大量的模型可以很容易地生成。它還應(yīng)該指出，這些建模系統(tǒng)在廣泛使用的個人電腦中易實現(xiàn)的。我們在下文回顧數(shù)學(xué)規(guī)劃模型的幾種主要類型。</p><p>　　2.1 線性和混合整數(shù)規(guī)劃</p>

27、<p>　　這毫無疑問是計劃調(diào)度中最普遍的模型，原因是這些模式大多數(shù)涉及離散時間情況和規(guī)范的簡單績效模型。盡管以前大部分模型是線性規(guī)劃，但現(xiàn)今由于離散決策使得大部分模型為混合整數(shù)規(guī)劃，而這些決策包括投資、計劃的擴展和實施、調(diào)度的分配和排序決策。 混合整數(shù)線性規(guī)劃問題的一般的形式： minZ =aTx+bTy（混合整數(shù)線性規(guī)劃） </p><p><b>　

28、　條件</b></p><p>　　Ax + By<=d</p><p>　　x>=0, y∈{0,1}m</p><p>　　對于在沒有離散變量y的例子，問題簡化為一個線性規(guī)劃（L）的問題。 這是一個凸優(yōu)化問題的特殊類型， 此最優(yōu)解是可行域的一個頂點。該解決方案 問題在很大程度上依賴于單純形算法（Chvatal, 1983; Saigal

29、, 1995），盡管最近內(nèi)點方法（Marsten et al，1990）由于他們能解決非常大的問題，日益受到注意?；旌险麛?shù)線性規(guī)劃方法主要依賴基于分支定界方法 （Nemhauser and Wolsey, 1988），這種方法包括枚舉樹子在每個節(jié)點得到線性規(guī)劃的解。這些方法通過割平面法正在改進（Balas et ，1993），這種方法為得到最優(yōu)解而產(chǎn)生下界。線性規(guī)劃和混合整數(shù)線性規(guī)劃被廣泛使用，最出名的包括： CLEX（ILOG，200

30、0），OSL（IBM，1992）及XPRESS（Dash Associates，1999），他們解決問題的功能取得了令人矚目的成就。值得注意的是，由于混合整數(shù)線性規(guī)劃問題是NP問題，能夠解決有大量0-1變量的問題。</p><p>　　2.2 非線性規(guī)劃</p><p>　　非線性規(guī)劃模型優(yōu)于線性規(guī)劃模型， 可以清晰的描述非線性而且主要用于實時優(yōu)化。這些模型僅涉及連續(xù)變量并且對于規(guī)劃和調(diào)

31、度是有限制的。對應(yīng)的非線性規(guī)劃可以表達問題如下： </p><p>　　Min Z = f (x)</p><p><b>　　條件</b></p><p><b>　　h (x) = 0</b></p><p>　　g (x) <=0 </p><

32、;p><b>　　x∈X</b></p><p>　　Karush Kuhn Tucker（Minoux，1983）給出了非線性規(guī)劃的條件，包括函數(shù)是連續(xù)的、可微的、確定的制約條件。非線性規(guī)劃問題的解決依耐與連續(xù)二次規(guī)劃算法 （SQP）（Han，1976;Powell，1978; Schittkowski，1981），或減少梯度法（Murtagh和 Saunders，1978，1982

33、）。</p><p>　　2.3 混合整數(shù)非線性規(guī)劃</p><p>　　混合整數(shù)非線性規(guī)劃模型一般發(fā)生這樣的規(guī)劃和調(diào)度，其使用連續(xù)時間，尤其是循環(huán)策略和非線性性能模型?；旌险麛?shù)非線性規(guī)劃問題通常是混合整數(shù)規(guī)劃的一特例，其中0-1變量是線性而連續(xù)變量是非線性： </p><p>　　Min Z = cTy + f(x) (MINLP)</p>

34、<p>　　條件 By+ g(x)<=0</p><p>　　x∈X,y∈{0,1}m</p><p>　　對混合整數(shù)非線性規(guī)劃問題的主要方法包括分支定界法（BB）（Gupta和Ravindran，1985;Borchers和Mitchell，1994;Stubbs和Mehrotra，1996），其為線性規(guī)劃例子的擴展。</p><

35、;p>　　3 基于邏輯的優(yōu)化 </p><p>　　近年來，一個新的趨勢已經(jīng)出現(xiàn)，就是探索解決離散/連續(xù)優(yōu)化問題的方法。這些方法，有利于問題的表述而且往往降低組合搜索，正在對規(guī)劃與調(diào)度問題研究產(chǎn)生重大影響。兩個主要方法是廣義析編程總值（GD）（拉曼和格羅斯曼，1994年）和約束規(guī)劃（范Hentenryck， 1989）。</p><p>　　3.1 廣義析取規(guī)劃</p>

36、<p>　　廣義析取規(guī)劃的基本思路是用持續(xù)變量來形成一個目標函數(shù)，但三個類型的約束：（一）離散決策是非獨立的; （二）包括運籌學(xué)運算的析取命題;（三）只有布爾變量的純邏輯約束。更具體地說，問題如下： </p><p>　　Min Z = ∑ck + f (x) (GDP)</p><p><b>　　條件</b></p><p>

37、;　　其中x是連續(xù)變量和y是布爾變量。目標函數(shù)涉及項f（x）的為連續(xù)變量（如營運成本），ck值依賴于離散選擇。</p><p>　　對于非線性問題的情況（GDP），李和格羅斯曼（1999）重新擬訂開發(fā)和算法，其依賴于代數(shù)描述。重新擬訂導(dǎo)致緊的混合整數(shù)非線性規(guī)劃問題，同時 </p><p>　　圖4：邊尋找車間作業(yè)調(diào)度技術(shù)</p><p>　　該算法一般涉及分支定界

38、方法，該方法由析取方法執(zhí)行。對于流程網(wǎng)絡(luò)問題，Turkay和Grossmann（1996）提出了一個以邏輯為基礎(chǔ)的外逼近算法。該算法包括解決減少空間的非線性規(guī)劃。</p><p><b>　　3.2 約束規(guī)劃</b></p><p>　　作為新近出現(xiàn)的基于邏輯優(yōu)化的領(lǐng)域，對于調(diào)度問題的確定類型被證明是成功的。規(guī)劃的基本理念（Van Hentenryck，1989;P

39、uget，1994）是使用嚴密的語言表達優(yōu)化問題，其變量是連續(xù)的整數(shù)，而且可以表示約束代數(shù)形式（如H（工）= 0），（例如，[A1x《=b1] _ [A2x《=b2]），或作為條件邏輯（例如如果g（x）《=0則r（x）= 0）。此外該語言能支持特殊的明確的函數(shù)，例如所有的不同的約束。該語言包括C + +的程序，雖然最近的趨勢，為社會提供更高水平的語言如OPL。其他商業(yè)C軟件套件包括 ILOG的求解。而不是依靠傳統(tǒng)的數(shù)學(xué)規(guī)劃方法，CP依賴

40、于使用隱枚舉搜索樹。這種樹通常是列舉部分解決方案。在樹中的每個節(jié)點搜索，約束傳播是通過域名進行減少的變量。這包括例如在問題范圍不斷減少變量和/或網(wǎng)域的情況下離散變量，前者使用更嚴格的程序單調(diào)的線性和職能范圍，而后者則要么是進行推理技術(shù)或者是專門程序。一個很好的例子是“邊調(diào)查”車間作業(yè)調(diào)度方法。圖4給出一個簡單的這種方法的例子，以解決析對工作相對加工i和j。</p><p>　　3.3 一種通用析取模型的集成規(guī)劃和

41、調(diào)度</p><p>　　在過去，規(guī)劃和調(diào)度模式已在很大程度上分別得到了解決。最近才出現(xiàn)同時規(guī)劃和調(diào)度模型（如Papageorgiou和Pantelides， Birewar和Grossmann，1990）。但是進展表明同時規(guī)劃與調(diào)度模型問題是棘手的。這是由于由此產(chǎn)生的規(guī)模與規(guī)劃和調(diào)度的時間不匹配。這表明，有必要獲取有效的綜合規(guī)劃和調(diào)度模型和算法。在這一節(jié)我們提出了一個模型，反映了決策層次可利用的潛在有效解決方案

42、。</p><p>　　上一節(jié)的論述，可以得出結(jié)論，廣泛應(yīng)用于規(guī)劃與調(diào)度的線性規(guī)劃和混合整數(shù)線性規(guī)劃方法，已成為相當強大。此外，自然語言處理方法，能夠面對越來越大的問題，正在通過嚴格的全局優(yōu)化算法?？傊?，這些發(fā)展有助于更快速的解決混合整數(shù)線性規(guī)劃問題。一個新的激動人心的新方向，是邏輯的優(yōu)化，如廣義析取編程方法和約束規(guī)劃，這將會保證制定以促進問題的解決和改善效率和穩(wěn)健性。為了說明使用基于邏輯的方法，我們目前在本節(jié)一

43、展示了一般的混合整數(shù)線性規(guī)劃模型。正如我們所看到的模型，給出引起了普遍的析取程序，包括嵌入式，反映的等級性質(zhì)在整合的問題作出決定。我們使用的規(guī)劃離散時間，表示安排時間域。此外，我們假設(shè)該調(diào)度模型對應(yīng)于國家的任務(wù)網(wǎng)絡(luò)（STN）（Kondili，1993）。建立規(guī)劃和優(yōu)化調(diào)度模型，H是分為若干規(guī)劃期間，噸= 1 .. T和一個調(diào)度周期數(shù)，一個規(guī)劃期的長短，通常是在在幾個星期或幾個月秩序。我們定義集合（噸）來表示它的調(diào)度期間，屬于規(guī)劃期內(nèi)噸完

44、整設(shè)置參數(shù)和變量的定義如下： 集： </p><p><b>　　指數(shù)： </b></p><p><b>　　參數(shù)：</b></p><p>　　基于以上的定義，非線性問題模型如圖所示：</p><p>　　我們的目標（1）是盡量減少整個周期的成本，包括經(jīng)營成本，擴大成本,以及資源成本。銷售

45、額包括由負值分配到相應(yīng)的成本系數(shù)。特定的規(guī)劃期的全局約束，如超過混合器的大量平衡，如庫存的限制,為代表（3）。注意，這兩個（2）及（3）可 一般涉及，Äôass上，從以前的專賣變量期間，引起連接限制。此外，全局調(diào)度的限制（3），一般也涉及的調(diào)度時間延遲，運輸署，由于加工次，清理倍，轉(zhuǎn)換時間。約束（5） - （16）被分為一組嵌套每個單元析限制j.外層析代表決定將在J室設(shè)計或不，這是一個戰(zhàn)略規(guī)劃的決定。如果單位j是包含

46、在設(shè)計，（系列YJ = True），則在限制設(shè)置的析取左側(cè)應(yīng)用，否則（系列YJ =假），狀態(tài)變量子集J室與相關(guān)設(shè)置為零的各個時期通過在（4）矩陣DJT的。中間析代表的決定，在規(guī)劃期內(nèi)的經(jīng)營J室t或不要，只適用于如果系列YJ =真。如果 單位j管理，在時期噸（wjt =真），它可以 被解釋為任何行動或戰(zhàn)術(shù)計劃離散優(yōu)化方法及其在規(guī)劃和調(diào)度159整合中的作用寧決定，然后限制（5）及（6），以及兩位代表擴張其余脫節(jié)和調(diào)度決策，被應(yīng)用。 （5）代

47、表的限制這是一個給定的有效J室在某規(guī)劃如單位輸入周期噸，</p><p>　　單位的具體安排的決定代表第二個內(nèi)部脫節(jié)。正如在上一節(jié)不存在真正的泛化調(diào)度模型。因此，我們著眼于從思想 超扭曲調(diào)度首次提出了Kondili等。 （1993年），因為這一提法可以應(yīng)用到任意網(wǎng)絡(luò)結(jié)構(gòu)。請注意，這只是內(nèi)部析 調(diào)度時期內(nèi)適用畝的規(guī)劃期噸，為記為集合廉政的（t，k）段。這指出，如果工作，我是J室開始，在安排時間畝，（vijk =

48、True），則該批處理大小限制在（13）單位的能力和資源使用的計算方法在（14）。如果工作，我是不是在時期開始J室畝，（vijk =假），開始批量的規(guī)模和資源使用設(shè)置為零（15）和（16）分別。 約束（17）至（24）的邏輯命題代表之間的邏輯關(guān)系的離散變量。 （17）指出，在列入J室設(shè)計意味著它必須至少在一個操作期間噸，而（18）國家相反的，即該行動J室中的任何時期噸意味著包容在設(shè)計J室。同樣，約束（19）國 在這期間噸J室操作，意

49、味著它必須已擴大至少一次在了前一段時間，而（20）國家相反的是J室擴大在時期意味著它也可能在此經(jīng)營期。約束（21）規(guī)定，對機組運行在規(guī)劃期內(nèi)，溫T J意味著，至少有一個工作，我必須開始在調(diào)度上期畝屬于J室規(guī)劃期內(nèi)噸如果一個</p><p><b>　　4 解決策略</b></p><p>　　雖然中等規(guī)模的規(guī)劃和調(diào)度模型，如第二和第四部分展示的，能夠用第三部分討論的數(shù)

50、學(xué)規(guī)劃方法來解決，但是，更大的問題實例，而這些問題是需要精確的描述其特征，，需要一定的分解，聚合型和/或其解決方案使用的啟發(fā)式。在本節(jié)中,我們回顧這些第3節(jié)提到的一些適用于大規(guī)模的混合整數(shù)線性或非線性問題中方法。</p><p><b>　　4.1分解 </b></p><p>　　選擇分解法時，很重要地去考慮如何使該模型的結(jié)構(gòu)最有效，并選擇分解度 在合理的時間內(nèi)解

51、決，而仍在一個最佳或接近最優(yōu)的解決方案。文獻中已提出了分解方案.Benders分解（Benders，1962）和雙分解或拉格朗日松弛（例如Fisher，1981）分別利用了該模型的原始和二元結(jié)構(gòu)。交叉分解（如Van Roy，1983）利用原始和二元結(jié)構(gòu)，并且應(yīng)用于容易解決的原始和二元結(jié)構(gòu)模型。雙層分解（例如Iyer and Grossmann，1998）探索模型的結(jié)構(gòu)，該模型包括不同層級的，從設(shè)計層次，到規(guī)劃，到調(diào)度。 Ruszczyn

52、ski（1997）對于隨機問題分解方法給出了全面的分析。這些方法包括切割方法、增強拉格朗日分解、分裂方法和嵌套分解。下面，我們只詳細的討論拉格朗日松弛和二層分解，因為深入的討論所有分解方法已經(jīng)超出了范圍 。出于兩級問題的相關(guān)性提出了一個例子，聯(lián)合規(guī)劃和調(diào)度模型。關(guān)于拉格朗日松弛討論是出于它廣泛適用于大型優(yōu)化模型及其執(zhí)行緩解實踐。</p><p><b>　　4.2雙層分解</b></p

53、><p>　　探索聯(lián)合設(shè)計、規(guī)劃和/或調(diào)度模型的層次結(jié)構(gòu)的一個方法是將模型分解成高水平的高層次問題，低水平的低層次問題。艾耶和格羅斯曼（1998）為混合整數(shù)線性規(guī)劃算設(shè)計和規(guī)劃問題提出了兩層分解算法，其中上層包括主要的設(shè)計決策，而在較低水平，設(shè)計主要的規(guī)劃決策。Van den Heever和格羅斯曼（1999）利用非線性問題將這種方法應(yīng)用于混合整數(shù)非線性規(guī)劃（MINLP）?？紤]一個原始模型（規(guī)劃），下標 “P”指代設(shè)

54、計變量，“p”指代規(guī)劃變量。 </p><p>　　為得出高水平的設(shè)計問題（DP），所有的離散規(guī)劃變量是緩和的。這將導(dǎo)致分枝定界節(jié)點數(shù)量的減少，從而促進更快的解決方案。此外，一些約束和或變量可在此層次上聚合。 </p><p>　　解決設(shè)計問題（DP）后，離散設(shè)計變量被確定（如表格所示），隨之對于確定設(shè)計的低層次的規(guī)劃問題被解決。</p><p>　　min f

55、(xd, ¯yd, xp, yp) (PP)</p><p>　　DP和PP問題分層的得到解決，并且設(shè)計和整數(shù)分割加在每次迭代以確保最佳的解決方案。請注意，即使這兩種DP和PP在一個下降的空間，但同時考慮作為整體的設(shè)計及規(guī)劃模型。另一個好處是，這種方法，比較與解決作為整體的合并問題，它極大地降低了計算錯誤，同時仍然保證最優(yōu)解決原組合模型的案例。Papageorgiou（996b）為大批量半連續(xù)設(shè)備綜合運

56、動規(guī)劃與調(diào)度提出類似的分解方法。在他們的工作中，高層次問題主要關(guān)注活動規(guī)劃決策，盡管調(diào)度決策匯總并且低水平的問題隨著一些規(guī)劃變量的確定而得到解決。再次兩層次都在整體上考慮問題。作者的經(jīng)驗，兩層分解方法，對于大型工業(yè)申請長期的時間范圍，特別是當隨著時間的聚集合并使用期，的效果特別好。如例一討論。 拉格朗日松弛。這是一個往往是應(yīng)用塊對角結(jié)構(gòu)模型的方法。在這種模式，對不同的變量和約束塊可以鑒定出一些與連接的“束縛”鏈接和變量（參見圖6）。某

57、些應(yīng)用程序包括不確定性的情況下規(guī)劃分解（Carøe和舒爾茨，1999），電廠單位（諾瓦克，1998），中期生產(chǎn)計劃（古普塔和馬拉納斯，1999），油田投資規(guī)劃（范登，2000）和聯(lián)合運輸和調(diào)度（Equiet，1997），</p><p>　　背后的拉格朗日松弛應(yīng)用的基本理念對塊對角結(jié)構(gòu)的分解，是dualize通過刪除連接限制設(shè)置的，并代之以它的目標函數(shù)，拉格朗日乘數(shù)就像在模型（LR）： </p&

58、gt;<p>　　模型（LR）正在分解到一個下界。變數(shù)的情況下可以通過引進與每個連接變量重復(fù)掛塊處理， 設(shè)置重復(fù)的平等，這種平等的對偶約束。這被稱為拉格朗日分解 （吉尼亞爾和Kim，198）。獲得最嚴格的下界至（l）需要解決的拉格朗日 偶問題（LD）的： </p><p>　　如果所有的約束是凸的，所有變量是連續(xù)的，在（LD）的優(yōu)化將等同于（L）的最優(yōu)化。然而，整數(shù)變量的存在或其他非凸性可能使二元

59、差距的存在，這意味著最優(yōu)解問題將嚴格小于真實的最優(yōu)化。 Guignard（1995）和Bazaraa等， （1994）提出全面對偶差距圖形來解釋整數(shù)變量和非凸約束的情況。求解（LD）可能難以實施而費時，盡管費希爾（1981）為此提出一些算法。一種求解雙重代碼是由Kiwiel（1994）提出的，但是這個代碼不廣泛為我們所知。求解雙重代碼以最優(yōu)，因此，往往規(guī)避通過使用迭代啟發(fā)式方法，即（LR）是解決產(chǎn)生下限為（L）和一個啟發(fā)式方法產(chǎn)生的（長

60、可行的解決方案）這亦是上限。更新在每次迭代 ，一些更新的規(guī)則，例如梯度方法（例如費雪，1981）。這種分解解決方法減少了計算量數(shù)，而原來的問題相關(guān)的算法不適于并行以減少計算量。對于拉格朗日松弛變量應(yīng)用，我們向讀者提到吉尼亞爾（1995）費希爾（1981，1985）。</p><p><b>　　4.3聚合 </b></p><p>　　對于一些模型，獲得合理時間內(nèi)最佳

61、解決方案，僅僅費解是不夠的，并且，某種形式聚合對于進一步降低模型大小是必要的。羅杰斯等（1991）關(guān)于聚合/分解在優(yōu)化中的應(yīng)用作了很好的論述。這些作者確定這一框架的重要組成部分，即聚合分析，分類分析和誤差分析。第一部分包括確定該模型的元素組合成一個元素，如何定義一個元素，而第二部分涉及反過來產(chǎn)生更精細模式。誤差分析決策由聚集和分類的誤差。這三個組件可以解決迭代順序或減少計算，來努力解決原來的問題，以及迭代辦法旨在減少在每次迭代的錯誤目標

62、。應(yīng)當指出，總的解決方案，配方不一定是可行的分解案例。然而，對某些型號有可能以這樣的方式，以聚集產(chǎn)量嚴格綁定到原來的問題，并保證其可行性。Iyer （1998）的石油油井聚集生產(chǎn)計劃的一個辦法，以減少數(shù)量約束，是一些為代理約束下聚集系數(shù)反復(fù)進行修改的線性結(jié)合（例如Ermoliev1997）。威爾金森等人（1996）使用約束聚合的方法來解決大規(guī)模生產(chǎn)和分配規(guī)劃的多個生產(chǎn)基地的問題。在工作中為上層水平總體模型求解制定生產(chǎn)目標，并產(chǎn)生一個嚴格

63、的上限，將其綁定到原來的問題，然后詳細優(yōu)化調(diào)度，可單獨為每個站點減少計算量固定目標。威爾</p><p>　　上述辦法，通過聚集在上層時間問題規(guī)劃在較低的水平分列其后的問題。另外一個子問題得到解決后，每次迭代，以確定最佳的新聚合計劃和從聚集子問題的信息用于在每次迭代消除較低級別的變量。結(jié)果發(fā)現(xiàn)，錯誤時間內(nèi)聚集非常小，主要是由于子問題的最佳聚合。其他匯總計劃包括產(chǎn)品的聚合。基于場景模型，場景聚合可以加快解決方案的時

64、間。該方案的做法是采用聚合一個混合整數(shù)線性多產(chǎn)品生產(chǎn)規(guī)劃。Jorsten和Leisten（1994）他們探索耦合之間的連續(xù)和整數(shù)規(guī)劃變量。除了分解和聚合技術(shù)，其他一些啟發(fā)式方法解決方案大規(guī)模的規(guī)劃和調(diào)度問題。其中一個啟發(fā)式是一個能力提出了啟發(fā)式轉(zhuǎn)變由艾哈邁德和Sahinidis（2000）一類的過程規(guī)劃問題。這些作者表明，他們的啟發(fā)式算法漸近消失隨著問題規(guī)模的增加。這是一個非常好的結(jié)果,考慮到時間呈指數(shù)的的增加，解決方案隨著時間為一個確

65、切的數(shù)字求解算法。</p><p><b>　　4.4 實例 </b></p><p>　　在本節(jié)中，我們用例子，說明一些本文所涉及的主要內(nèi)容。例如 1的規(guī)劃問題，給出了一大型多期MINL模型，這需要一個分解使用/聚合策略。例如2描述了一個鋼鐵混合整數(shù)線性規(guī)劃調(diào)度模型制造，這也是通過特殊的處理分解。最后，描述了一個例子3 混合的CP /混合整數(shù)線性規(guī)劃的并行調(diào)度問題模

66、型，這表明了合并的優(yōu)勢方法而不是純粹的CP或保險計劃。 </p><p>　　圖7：領(lǐng)域配置，良好的平臺和生產(chǎn)平臺</p><p>　　工業(yè)領(lǐng)域的基礎(chǔ)設(shè)施規(guī)劃的運作和投資規(guī)劃中所涉及的設(shè)計與基礎(chǔ)設(shè)施規(guī)劃是一項具有挑戰(zhàn)性的問題，如涉及幾個復(fù)雜長期的時間限度，非線性庫存行為，并且復(fù)雜的財政規(guī)則導(dǎo)致多期財MINL模型。例如（詳見Van den Heever和格羅斯曼，2000），我們考

67、慮海上油田的基礎(chǔ)設(shè)施的設(shè)計，規(guī)劃和調(diào)度，需要作出將其 6年的季度分成24期來決策。正在審議的基礎(chǔ)設(shè)施由一個生產(chǎn)平臺（PP），2井平臺（WP），25井和連接管道（見圖7）。每個油田（F）有大量的油（R），而每一油井包含一些潛在的地點來鉆探。設(shè)計決定涉及作為繳費和WS，能力以及有關(guān)的決策，安裝了整個操作系統(tǒng)的范圍。規(guī)劃決策涉及在每個時期的生產(chǎn)概況，以及決定關(guān)于繳費、安裝和WS時，包括鉆井在設(shè)計，調(diào)度決策涉及的時間。這將得到一個混合整數(shù)非線性

68、規(guī)劃模型，這個模型包括9700個約束、5953個連續(xù)變量以及700個0-1變量。</p><p>　　為了解決這個商業(yè)模型如GAMS（布魯克等，1992年） （使用DICOT（維斯瓦納和格羅斯曼，1990），為解決混合整數(shù)線性規(guī)劃的CLEX 6.6（ILOG的公司，2000年）和為解決非線性規(guī)劃的CONOT2（Drud，1992）H9000/C110工作站），結(jié)果這一解決方案的處理器的時間為19386秒。為了克服

69、這一解決方案時間長度的問題， 當時，范登Heever和格羅斯曼（2000）開發(fā)迭代聚合/分解算法，該模型的CPU運行時間為1423S。</p><p>　　圖8：在6年之內(nèi)生產(chǎn)的形象該算法結(jié)合兩層分解、聚合時間和以邏輯為基礎(chǔ)的方法。原先設(shè)計和規(guī)劃的問題被分解為上層設(shè)計問題和較低層面的規(guī)劃問題，兩者都形成定析模型。那個上層設(shè)計問題是解決了總時間，之后，設(shè)計被固定，時段被分解，下一級的規(guī)劃問題隨之得到解決。這一結(jié)果

70、是用來確定一個新的時間聚集，通過動態(tài)規(guī)劃子問題和整數(shù)削減添加到設(shè)計問題，聚集參數(shù)更新，并反復(fù)迭代，直到終止準則達成協(xié)議。因此，聯(lián)合應(yīng)用分解和聚合導(dǎo)致解決時間的減少。此特定的模式，大幅度減少在計算工作，主要是由于聚集/ 分解，而析編程制定主要貢獻是在減少非凸，由于零流動和明確性代表性。但是，不同的規(guī)劃模型在析取編程方法可能會減少計算量，就表明了范登和 格羅斯曼（1999年網(wǎng)絡(luò)的過程中設(shè)計的情況下）并規(guī)劃和改造一批工廠。圖8顯示了過去6年的

71、總石油產(chǎn)量，而表1給出了最優(yōu)投資計劃獲得。請注意，只有25口油井最后被選擇。這個解決方案使成本節(jié)約數(shù)百萬美元，相比較，啟發(fā)式方法應(yīng)用于幾乎所有的指定正在鉆探油井。在Van den Heever（2000）中，基礎(chǔ)設(shè)施的規(guī)劃領(lǐng)域擴大到包括諸如特許權(quán)使用費，關(guān)稅和復(fù)雜的財政規(guī)則稅收。這導(dǎo)致任何解決方案模</p><p>　　圖9：鋼鐵生產(chǎn)處理步驟5 結(jié)論 </p><p>　　本文提出了一

72、個規(guī)劃和調(diào)度的概述。它已經(jīng)展示了這些問題促使離散優(yōu)化模型的提出，這些模型相關(guān)的數(shù)學(xué)規(guī)劃問題對應(yīng)整數(shù)規(guī)劃問題，這些問題在計算時表現(xiàn)為指數(shù)行為?；谶壿嫷膬?yōu)化技術(shù)不僅在簡化建模而且在降低計算需求提供了潛力。我們已經(jīng)說明了，使用基于邏輯優(yōu)化，通過廣義析取程序，集成規(guī)劃和調(diào)度流程網(wǎng)絡(luò)，作為建模工具。我們也給予了分解策略，因為這些是解決大型工業(yè)的問題必不可少的。最后，我們提出了3個例子，規(guī)劃油田，鋼鐵生產(chǎn)調(diào)度和調(diào)度的并行機，來說明可能的解決問題的