時間依賴調(diào)度方法及在敏捷衛(wèi)星任務(wù)規(guī)劃中的應(yīng)用研究.pdf

1、調(diào)度研究的問題是在一定的時間范圍內(nèi)將有限的資源分配給不同的任務(wù)，一個可行的調(diào)度方案必須滿足問題中涉及的任務(wù)、資源及時間等所有約束，調(diào)度的目標(biāo)是從所有可行方案中找出一個最優(yōu)或滿意解。對調(diào)度問題的研究始于二十世紀中期，在過去幾十年中調(diào)度領(lǐng)域內(nèi)新問題、新理論和新方法層出不窮。時間依賴調(diào)度便是調(diào)度領(lǐng)域內(nèi)相對新穎的一個研究課題。在時間依賴調(diào)度問題中，存在一個或多個元素與時間緊密關(guān)聯(lián)。事實上，“時間依賴調(diào)度”一詞，最初被用來描述工件的加工持續(xù)時間依

2、賴于其加工開始時間的問題。在該問題中，工件的加工時間不再是一個固定值，而是隨著加工開始時間的不同而變化的，這也是當(dāng)前研究受到最多關(guān)注的一類時間依賴調(diào)度問題。然而除此之外，加工一個工件獲得的收益（或引起的懲罰）、加工不同工件之間需要的轉(zhuǎn)換時間也可能依賴于開工時間（或完工時間），這兩種特點可分別稱為時間依賴的收益和時間依賴的轉(zhuǎn)換時間，在生產(chǎn)制造、物流配送等行業(yè)中廣泛存在，在敏捷衛(wèi)星任務(wù)規(guī)劃中也顯得尤為突出。本研究主要內(nèi)容包括：
　?、?/p>

3、提出了考慮提早-延期懲罰調(diào)度問題的求解算法。考慮提早-延期懲罰的調(diào)度問題是一種典型的具有時間依賴收益特點的調(diào)度問題。機器加工一個工件引起的懲罰項不是一個固定值，而是依賴于工件的完工時間?？紤]每個工件具有不等的釋放時間、交貨期、提早和延期懲罰系數(shù)，分別為單機環(huán)境和并行機環(huán)境下的調(diào)度問題建立了數(shù)學(xué)模型。單機環(huán)境下，提出了求解問題的模因演化算法。其中，在給定工件加工序列的情況下，考慮工件具有不同的釋放時間和轉(zhuǎn)換時間，提出了一種改進的最優(yōu)定時算

4、法來確定各工件的加工時間并計算目標(biāo)函數(shù)值，通過和經(jīng)典遺傳算法以及OPL的實驗比較，驗證了算法的優(yōu)化性能。并行機環(huán)境下，一是將求解單機問題的模因演化算法進行了擴展使之應(yīng)用于并行機環(huán)境，二是在給定工件加工序列的情況下提出了一種改進的構(gòu)造啟發(fā)式算法確定工件的加工機器及開工時間，通過實驗分析給出了這兩種算法各自的適用場景。
　?、铺岢隽擞唵问芾砼c調(diào)度問題的求解算法。訂單受理與調(diào)度問題是一個同時結(jié)合了選擇與調(diào)度特點和時間依賴收益特點的問題。

5、為最大化完工訂單的收益，需要將選擇和調(diào)度這兩個決策過程集成考慮，從所有訂單中選擇出一部分加工并為各訂單安排加工時間，加工訂單獲得的收益依賴于訂單的完工時間。建立了該問題的數(shù)學(xué)模型，提出了求解該問題的差異化控制遺傳算法。算法中針對該問題的特點提出了一種衡量個體之間差異大小的準(zhǔn)則，使用差異化控制策略使算法在搜索過程中始終保持一個差異化種群，引入基于析構(gòu)與構(gòu)造策略的迭代貪婪啟發(fā)式算法作為局部搜索算法。通過與其他五種算法在大量標(biāo)準(zhǔn)測試算例上的測

6、試，驗證了本文算法優(yōu)良的優(yōu)化性能。
　?、翘岢隽司哂卸鄷r間依賴特點調(diào)度問題的求解算法。研究了一個同時結(jié)合了時間依賴轉(zhuǎn)換時間、選擇與調(diào)度結(jié)合和時間依賴收益特點的調(diào)度問題。該問題是在訂單受理與調(diào)度問題的基礎(chǔ)上，引入時間依賴轉(zhuǎn)換時間以及提早-延期懲罰，非常復(fù)雜、難以求解。本文采用位于0和1之間的實數(shù)作為編碼方式，每個實數(shù)表示工件的實際完工時間占整個時間窗口長度的比率。當(dāng)給定一個實值向量時，根據(jù)向量中的各實數(shù)預(yù)先確定對應(yīng)工件的開工時間和完

7、工時間，并且根據(jù)工件的開工和完工時間計算不同工件之間需要的轉(zhuǎn)換時間。在此基礎(chǔ)上建立一個有向無環(huán)圖，圖中最長路徑上的節(jié)點即為被安排加工的工件，路徑的長度即為該實值向量對應(yīng)的目標(biāo)函數(shù)。提出一種基于該有向圖適應(yīng)度評價的混合差分進化算法，通過和其他三種算法在測試算例上的實驗分析驗證了算法的有效性。
　?、仍诿艚菪l(wèi)星任務(wù)規(guī)劃上的應(yīng)用。以我國在研的某型敏捷衛(wèi)星為例，以工程應(yīng)用中的姿態(tài)轉(zhuǎn)換時間函數(shù)作為時間依賴轉(zhuǎn)換時間的計算方式，將本文的時間依賴