基于OPL的帶資源的計劃優(yōu)化方法研究與實踐

楊偉宏、王易南、徐珊珊、岳曉飛、王曉鵬 /北京宇航系統(tǒng)工程研究所

型號研制計劃是航天工程管理重要的表征形式，是保證型號研制能否按期保質完成的重要指導性文件，在型號研制管理中占有特殊的地位。型號研制計劃規(guī)定了各參研、參制單位研制任務的邏輯順序、任務和資源的關聯(lián)關系以及工期要求，是在型號研制過程中開展指揮、控制、評價等管理工作的主要依據和基準。因此，航天型號管理的本質是圍繞研制計劃的管理，必須以型號研制計劃為綱，才能抓住型號管理的主線，做到綱舉目張。

型號研制計劃受到各種技術以及技術研發(fā)進展的影響，當在新技術應用或技術實現(xiàn)過程中出現(xiàn)各種可能或矛盾時，必然影響研制計劃全局，如有些重要的計劃安排有可能因為總體技術狀態(tài)的改變而需要重新調整。與人類認識世界的過程一樣，技術實現(xiàn)過程也是一個循環(huán)往復的過程，型號研制計劃雖然在執(zhí)行過程中具有一定的強制性，但與對客觀世界的認識過程是統(tǒng)一的、目標是一致的，其復雜性和動態(tài)性就表現(xiàn)在技術實現(xiàn)過程與最終目標的不斷折衷。因此，在型號研制過程中型號研制計劃需要不斷調整，而這種調整是客觀的，也是必要的。正是由于型號研制計劃在航天型號管理中的重要作用，以及其特有的復雜性、動態(tài)性，使得在實際計劃管理中急需一種既能反映計劃各個任務之間的邏輯關系，又能反映資源配置使用情況的管理工具和方法。

一、帶資源的計劃優(yōu)化的必要性和理論依據

1.計劃優(yōu)化的必要性

按照項目管理理論，開展航天型號研制計劃管理是一個復雜的網絡體系。各研制任務之間的關系不僅是一套時間進度管理的關系，也是一套資源配置管理的關系。 同 時，要特別體現(xiàn)研制任務之間的邏輯關系，借以控制和跟蹤技術狀態(tài)變化。這些關系有的可以與時間進度關系重合，有的則僅僅是在單個計劃任務上才能結合在一起，共同形成多重網絡。在經典項目管理中，關鍵路徑是指直接影響項目最終完成時間的任務集合，而在型號實際管理過程中關鍵路徑有時是多重的。確定關鍵路徑，不但要從時間進度關系上考慮，還要從技術風險上考慮。此外，在不同節(jié)點中改變計劃任務的某一個屬性或數值時，很可能影響與之有關的下游任務是否還是關鍵路徑、影響其他任務的資源是否能夠按期投入使用等。

編制計劃應當客觀準確地反映型號研制實際，不能脫離實際以人為主觀因素或要求編制計劃。特別是各承研、承制單位的型號研制計劃，由于涉及的專業(yè)繁雜，必須全面統(tǒng)籌考慮各種要素才能編制出系統(tǒng)、科學、可行的計劃。

當前，各承研、承制單位大都面臨多型號并舉的實際情況，在實際型號研制活動中資源爭奪現(xiàn)象比較普遍，同一個資源被多個型號使用，如試驗場地會發(fā)生沖突、主要設計人員的時間分配出現(xiàn)“撞車” 等，進而導致資源不足或資源沖突等問題，這些是計劃執(zhí)行不力引發(fā)計劃調整最常見也是最主要的原因。因此，計劃管理中有效的資源配置和平衡管理能力已經成為確保計劃完成的決定性因素，如何實現(xiàn)帶資源的計劃優(yōu)化是型號研制計劃管理中亟待解決的問題。

這些關系有的可以與時間進度關系重合，有的則僅僅是在單個計劃任務上才能結合在一起，共同形成多重網絡。在經典項目管理中，關鍵路徑是指直接影響項目最終完成時間的任務集合，而在型號實際管理過程中關鍵路徑有時是多重的。確定關鍵路徑，不但要從時間進度關系上考慮，還要從技術風險上考慮。此外，在不同節(jié)點中改變計劃任務的某一個屬性或數值時，很可能影響與之有關的下游任務是否還是關鍵路徑、影響其他任務的資源是否能夠按期投入使用等。

2.調度優(yōu)化理論

計劃優(yōu)化屬于現(xiàn)代運籌學的調度問題。調度是指考慮隨時間的變化，如何安排有限的資源在執(zhí)行任務的同時滿足特定的約束。調度問題分為作業(yè)車間調度問題、群體作業(yè)調度問題、并行機床調度問題、資源約束的項目調度問題和多處理器調度問題等幾個大類。

調度問題一般采用三段式的描述方法，即α/β/γ的表達方式，α表示機床的環(huán)境或資源的環(huán)境因素，β表示過程和約束的情況，γ表示優(yōu)化的目標是什么。

根據算法理論，對復雜算法的難度采用是否在一定限制下完成計算作為衡量，即存在一個多項式函數g(x)， 如 果復雜問題的算法在該多項式描述的時間內完成計算，則稱該算法為解決該問題的多項式時間算法，該問題則被稱為多項式時間可解問題。多項式函數增長的速度比指數函數增長的速度慢得多，因此如果能夠證明一個問題存在算法，且算法是多項式算法，則認為該算法是高效的，此問題也被稱為P 問題。

NP 問題：可以在多項式時間內驗證某個解是否合法，但不能確定存在多項式算法的問題。

NP 難問題：如果對于某個問題X，任意NP 問題Y，都有YocpolyX（X 比Y 難）， 則X 是NP 難問題(比NP 問題難，但不是NP 問題)。

NP 完全問題：如果問題是NP 難問題，且它是一個NP 問題。

實際中，典型的NP 完全問題有著色問題、TSP、劃分問題、作業(yè)車間調度問題等幾種。經證明，帶資源的計劃優(yōu)化問題也屬于NP 完全問題。

二、帶資源的計劃優(yōu)化模型與解決方法

1.帶資源的計劃優(yōu)化模型

帶資源的計劃優(yōu)化問題在調度理論中表示為Pm/prec，multi-s，Pij=PJ/Cmax。 其 中，Pm表示多項目，prec表示具有緊前關系，s為單項任務需要資源的最大的項數。

具體數學模型為：

j為任務數，Pij為第i個資源加工第j個任務的工期，這里要求Pij=PJ，即所有資源對同一任務的工期是一樣的。Rj為任務j的使用資源集合，D為緊前、緊后關系集合。優(yōu)化目標是最大完成時間（makespanCmax）最小。

2.計劃優(yōu)化的實現(xiàn)

運籌學在20 世紀40 年代出現(xiàn)以來，經過科技工作者的不斷完善已經成為具有完整理論體系的龐大理論體系。近幾十年各種優(yōu)化算法不斷涌現(xiàn)，在國際、國內科研生產和經濟管理等各個方面取得了大量成果，如廣泛用于科研管理的優(yōu)化算法主要有線性規(guī)劃方法、動態(tài)規(guī)劃方法、組合優(yōu)化方法等。同時，面對市場的強烈需求，市面上發(fā)布了許多有效的計算工具和軟件系統(tǒng)，為實際應用提供了強大的支撐。

Ilog 公司是國外一家專業(yè)從事優(yōu)化計算系統(tǒng)開發(fā)的公司，旗下有一系列產品。OPL studio（簡稱OPL）是一個集成環(huán)境的優(yōu)化計算系統(tǒng)，能夠解算線性規(guī)劃、整數規(guī)劃、混合整數規(guī)劃等問題，其核心是Complex 優(yōu)化模塊。該軟件擁有其他軟件沒有的Activity 對象，該對象專門用來進行計劃和高級排產問題（APS）的建模，能夠充分體現(xiàn)項目的特點，便于使用。此外，與該對象相關的資源類型的定義，項目之間緊前、緊后關系的定義等均非常獨特，大大簡化了計劃優(yōu)化問題建模的難度。另外，OPL 同樣可以和數據庫系統(tǒng)接口，方便模型與數據的對接。

使用OPL 語言明確優(yōu)化目標、約束條件、任務和資源的關系，就完成了模型的構建。

三、帶資源的計劃優(yōu)化應用效果

1.數據模型

在實際應用中，選擇一個具有代表性的某型號的某項研制任務的研制計劃進行優(yōu)化計算。該計劃被分解成59 項子任務（其中一項為里程碑計劃），資源共有4 類、12 個，其中總設計師（正副）2 人（ZS1、ZS2）、總體設計師4 人（ZT1-ZT4）、結構設計師4 人(JG1-JG4)、電氣設計師3 人(DQ1-DQ2)。根據實際型號研制規(guī)律和流程，計劃中各個子任務滿足一定的緊前、緊后關系。在計劃的中期設置了初樣評審任務，作為計劃中期的檢查節(jié)點。

按照優(yōu)化模型的要求，每個子任務具有明確的工期，子任務之間存在緊前、緊后的關系，關系由數據結構表示。此外，共有4 類資源，資源和子任務之間的映射關系通過數據結構表示，每個子任務使用2 類或2 類以上的資源配合完成。資源屬于唯一型資源，即在同一時間內不能被2個子任務同時使用。

2.計劃優(yōu)化計算過程與結果應用

首先，按照常規(guī)的依據主觀經驗的方法編制計劃，只考慮任務之間的邏輯關系，不考慮資源配置等情況，制定的計劃總工期為700 天，如圖1 所示。但是該計劃包含大量的資源沖突問題，如ZT3 的資源需求將超過其能力的300%，如圖2 所示。

圖1 某研制計劃甘特圖

圖2 資源沖突示意圖

經過OPL 系統(tǒng)優(yōu)化計算，系統(tǒng)通過調整子任務的開始時間，各項資源在時間軸上沒有沖突，給出了817 天的優(yōu)化計算結果，如圖3 所示，優(yōu)化后的計劃比原計劃更具有科學性和合理性。

從優(yōu)化計算結果中可以看到，雖然優(yōu)化后總工期比優(yōu)化前延長了117 天，但各個子任務和資源（本模型為雙資源）的匹配關系，以及任務之間的緊前、緊后的邏輯關系，資源的約束關系全部都得到了滿足。計劃優(yōu)化前，各個子任務的工期都是理想狀態(tài)，資源配置情況也是如此，但是在實施過程中由于實際執(zhí)行情況千變萬化，工期和資源配置發(fā)生變化是必然的，因此可以將初步優(yōu)化后的計劃視為項目的計劃基線。

圖3 優(yōu)化后與優(yōu)化前對比

從優(yōu)化計算結果中還可以得到各個資源的使用情況（資源負載率）。12 個資源（列中的單元）均按照要求承擔不同的子任務，其中資源ZT1 和資源DQ2 工作最飽滿，這就是計劃實施中的關鍵資源（不一定是關鍵鏈上的資源）。對于任務不飽滿的資源，也明確地給出了空閑時間，在計劃實施中可以在其空余時間段調配去承擔其他任務。

如果通過調整資源配置，增加關鍵資源的投入（增加ZT 和DQ 類資源的數量），減少任務不飽滿資源，再經過優(yōu)化計算，勢必會進一步縮短總工期。如果再將多個項目計劃進行聯(lián)合優(yōu)化計算，將本項目空閑的資源提供給其他需要該項資源的項目，從其他項目中爭取到本項目繼續(xù)的關鍵資源，計劃優(yōu)化的效果將會更加明顯。因此，通過OPL 系統(tǒng)優(yōu)化計算，不但可以幫助管理者科學編制計劃，而且還可以制定資源調整配置的策略，進而通過調整資源配置及資源和任務的關系，逐步逼近理想的工作目標。

后續(xù)，在型號研制計劃的大規(guī)模實踐中將會遇到計算量達十萬級和百萬級的優(yōu)化項目，這就需要有更加強大的計算引擎完成計算。目前，資源與子任務之間是按照唯一型關系設定的，在實踐工作中還會遇到總量約束型、能力恢復型等多種匹配類型的資源，需要進一步研究新的更加高效的模型和算法。此外，還需要關注計劃管理的復雜性和動態(tài)性，臨時性任務和資源配置需求在實際工作中會不時出現(xiàn)，各任務計劃完成時間也會出現(xiàn)一定的偏差，這就需要建立一個有效的信息采集機制，及時采集資源管理和計劃實施過程中的各種信息，并通過OPL 系統(tǒng)完成優(yōu)化計算，不斷完善制定最優(yōu)的調度方案，而開展這些工作需要從組織層面建立健全完善的規(guī)章制度和精細化的工作流程?！?/p>