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

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)注。一個(gè)主要原因

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

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

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

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

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

9、考慮的時(shí)間限度可將規(guī)劃問題大致可分為戰(zhàn)略、戰(zhàn)術(shù)或業(yè)務(wù)。戰(zhàn)略規(guī)劃涵蓋了最長的時(shí)間限度，通常為在一至數(shù)年，其決策在整個(gè)組織范圍并且關(guān)注與大的投資。戰(zhàn)略規(guī)劃問題包括設(shè)施選址問題（e.g.Mazzola and Neebe，1999），化學(xué)平臺(tái)投資規(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ī)劃在考慮長遠(yuǎn)投資決策是非常重要的。戰(zhàn)術(shù)規(guī)劃通常是幾個(gè)月到一年的時(shí)間跨度，其決策包括生產(chǎn)、庫存和分配。中期生產(chǎn)計(jì)劃或供應(yīng)鏈規(guī)劃是一個(gè)很好的戰(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ī)劃通常是一個(gè)星期到三個(gè)月的時(shí)間跨度，涉及的決策為實(shí)際的操作和資源分配。應(yīng)用包括設(shè)施系

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

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

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

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

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

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

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

18、有限的需要 。資源約束調(diào)度問題是艱難的的，因?yàn)檫@樣的事實(shí)：除了達(dá)到產(chǎn)品要求的單位有效分配，還需要考慮可行離散優(yōu)化方法及其在規(guī)劃和調(diào)度整合中的作用 。</p><p><b>　　圖2：網(wǎng)絡(luò)數(shù)值</b></p><p>　　短期調(diào)度相關(guān)的工廠，必須滿足不同需求的個(gè)人客戶訂單模式。在這種情況下，產(chǎn)品對(duì)每個(gè)要求給出一個(gè)關(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)度更加簡化。當(dāng)切換產(chǎn)品，甚至在相同的產(chǎn)品有一個(gè)或多個(gè)批次，單元可能為達(dá)到產(chǎn)品質(zhì)量需要重新安裝。改變多少根據(jù)工廠里單元和產(chǎn)品的性質(zhì)而定。依耐改變的排序是最普遍和困難的局面，每一個(gè)連續(xù)可能引起不同的時(shí)間或成本的要求。例如，可能需要轉(zhuǎn)換每批次或之后的若干批，無論對(duì)產(chǎn)品的性質(zhì)如何。</p><p>　　從所有的化學(xué)工程文獻(xiàn)已提出的調(diào)度模型中，最一般模式是由Ko

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

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

22、是獲得利潤最大化功能。圖3顯示了在圖2示例最優(yōu)調(diào)度的結(jié)果。應(yīng)當(dāng)指出，通過Shah et al（1993）改進(jìn)的混合整數(shù)線性規(guī)劃，可以解決與之相當(dāng)大的問題。此外，Pantelides（1994）提出的資源任務(wù)網(wǎng)絡(luò)（RTN），從而導(dǎo)致更緊湊型模式，與STN相比，盡管它實(shí)際上是同等的，有趣的是，在上文圖1，無論是STN和RTN都可以處理任意拓?fù)浣Y(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)，它們對(duì)應(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）是目標(biāo)函數(shù)（如成本）， H（x，y）= 0是描述系統(tǒng)性能

25、的方程（物料平衡，生產(chǎn)率），而g（x，y）《=0為可行的計(jì)劃和調(diào)度約束的不等式。 變量x是連續(xù)的，一般對(duì)應(yīng)狀態(tài)變量，而y是離散變量， 通常僅限于采取0-1值，如設(shè)備分配和作業(yè)排序。如果所有的對(duì)應(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í)施主要數(shù)學(xué)規(guī)劃的問題的成型和解決辦法。盡管這些系統(tǒng)需要對(duì)模型能夠清晰的用代數(shù)形式表達(dá)出來，他們的優(yōu)點(diǎn)是自動(dòng)解決各類型的問題。他們還執(zhí)行自動(dòng)分化并允許有索引的方程使用，而且大量的模型可以很容易地生成。它還應(yīng)該指出，這些建模系統(tǒng)在廣泛使用的個(gè)人電腦中易實(shí)現(xiàn)的。我們?cè)谙挛幕仡檾?shù)學(xué)規(guī)劃模型的幾種主要類型。</p><p>　　2.1 線性和混合整數(shù)規(guī)劃</p>

27、<p>　　這毫無疑問是計(jì)劃調(diào)度中最普遍的模型，原因是這些模式大多數(shù)涉及離散時(shí)間情況和規(guī)范的簡單績效模型。盡管以前大部分模型是線性規(guī)劃，但現(xiàn)今由于離散決策使得大部分模型為混合整數(shù)規(guī)劃，而這些決策包括投資、計(jì)劃的擴(kuò)展和實(shí)施、調(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>　　對(duì)于在沒有離散變量y的例子，問題簡化為一個(gè)線性規(guī)劃（L）的問題。 這是一個(gè)凸優(yōu)化問題的特殊類型， 此最優(yōu)解是可行域的一個(gè)頂點(diǎn)。該解決方案 問題在很大程度上依賴于單純形算法（Chvatal, 1983; Saigal

29、, 1995），盡管最近內(nèi)點(diǎn)方法（Marsten et al，1990）由于他們能解決非常大的問題，日益受到注意?；旌险麛?shù)線性規(guī)劃方法主要依賴基于分支定界方法 （Nemhauser and Wolsey, 1988），這種方法包括枚舉樹子在每個(gè)節(jié)點(diǎn)得到線性規(guī)劃的解。這些方法通過割平面法正在改進(jìn)（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ī)劃模型， 可以清晰的描述非線性而且主要用于實(shí)時(shí)優(yōu)化。這些模型僅涉及連續(xù)變量并且對(duì)于規(guī)劃和調(diào)

31、度是有限制的。對(duì)應(yīng)的非線性規(guī)劃可以表達(dá)問題如下： </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ù)時(shí)間，尤其是循環(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>　　對(duì)混合整數(shù)非線性規(guī)劃問題的主要方法包括分支定界法（BB）（Gupta和Ravindran，1985;Borchers和Mitchell，1994;Stubbs和Mehrotra，1996），其為線性規(guī)劃例子的擴(kuò)展。</p><

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

51、決，而仍在一個(gè)最佳或接近最優(yōu)的解決方案。文獻(xiàn)中已提出了分解方案.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)，該模型包括不同層級(jí)的，從設(shè)計(jì)層次，到規(guī)劃，到調(diào)度。 Ruszczyn

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

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

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

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

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

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

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

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

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

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

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

63、的上限，將其綁定到原來的問題，然后詳細(xì)優(yōu)化調(diào)度，可單獨(dú)為每個(gè)站點(diǎn)減少計(jì)算量固定目標(biāo)。威爾</p><p>　　上述辦法，通過聚集在上層時(shí)間問題規(guī)劃在較低的水平分列其后的問題。另外一個(gè)子問題得到解決后，每次迭代，以確定最佳的新聚合計(jì)劃和從聚集子問題的信息用于在每次迭代消除較低級(jí)別的變量。結(jié)果發(fā)現(xiàn)，錯(cuò)誤時(shí)間內(nèi)聚集非常小，主要是由于子問題的最佳聚合。其他匯總計(jì)劃包括產(chǎn)品的聚合?；趫鼍澳Ｐ停瑘鼍熬酆峡梢约涌旖鉀Q方案的時(shí)

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

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

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

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

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

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

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

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

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