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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

具體數(shù)學(xué)模型為：

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

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

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

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

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

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

1.數(shù)據(jù)模型

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

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

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

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

圖1 某研制計劃甘特圖

圖2 資源沖突示意圖

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

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

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

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

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

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