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

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

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

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

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

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

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

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