王艷紅 雷松澤 張文娟 李 蕊

（1.西安工業(yè)大學(xué)理學(xué)院 西安 710021）（2.西安工業(yè)大學(xué)計算機(jī)科學(xué)與工程學(xué)院 西安 710021）

1 引言

排序問題也稱調(diào)度問題，實際問題中，常有一些隨機(jī)因素，或者隨機(jī)數(shù)據(jù)在進(jìn)行決策之前不確定，這些隨機(jī)因素或者隨機(jī)數(shù)據(jù)即為隨機(jī)變量，隨機(jī)變量在進(jìn)行決策之前只知（或能統(tǒng)計出）其概率分布律，分布函數(shù)，均值和方差等。此類包含隨機(jī)變量的排序問題即為隨機(jī)排序問題［1］。很多現(xiàn)實問題中的參數(shù)是連續(xù)變化的，比如新任務(wù)的到達(dá)時間，資源衰退，任務(wù)的完工時間等。對于不確定性問題，很多近似算法已經(jīng)被提出，如最優(yōu)搜尋算法，蟻群算法，遺傳算法，機(jī)器規(guī)劃，基于尋找策略的人工智能，支配或啟發(fā)式算法以及商業(yè)化的有限容量排序等。對于一些排序問題，將其分解為各個分支，每個分支采用不同的處理方式，把這些分支綜合起來后可能會得到意想不到的效果及改善。給出隨機(jī)排序問題（調(diào)度問題）的最優(yōu)算法，可用于指導(dǎo)生產(chǎn)，優(yōu)化生產(chǎn)。對于隨機(jī)排序問題，由于隨機(jī)變量的不確定性，常通過研究其對應(yīng)的確定性問題來分析其最優(yōu)算法。雖然一些隨機(jī)排序問題對應(yīng)的確定性問題是NP-難的，但原隨機(jī)排序卻有多項式最優(yōu)算法。文獻(xiàn)［2～3］證明了最短期望加工時間優(yōu)先（Weighted Shortest Expected Processing Time First，WSEPT）規(guī)則為問題的最優(yōu)算法，而該問題對應(yīng)的確定性問題等價于背包問題［4～5］為 NP-難問題。

2 問題描述

本文對WSEPT規(guī)則在期望值角度給以新的更深入的分析。該分析對開始期限及完工期限模型均適用，包含兩方面：一是E[μ (J)]［6］（其中 J 表示用WSEPT排序的隨機(jī)任務(wù)集）的下界；二是（其中J表示用最優(yōu)適應(yīng)性策略排序的隨機(jī)任務(wù)集）的上界。在此之后，通過由WSEPT的期望值與最優(yōu)適應(yīng)性策略排序的期望值的關(guān)系來修正上下界。

假設(shè)，在非適應(yīng)性條件下，用WSEPT規(guī)則對任務(wù)進(jìn)行排序。記Mj=∑μi，對所有的i≤j。根據(jù)馬爾可夫不等式（馬爾可夫不等式給出了隨機(jī)變量的函數(shù)大于等于某正數(shù)的概率的上界），可得任務(wù)1，…，j的一個概率期望下界為1-Mj-1（對開始期望模型）及1-Mj（對完工期望模型）。但對于Mj-1≤1（或 Mj≤1）的情形，該下界僅限于小任務(wù)集。下述引理會給出一個更強(qiáng)的結(jié)論，當(dāng)任務(wù)1，…，j-1已經(jīng)成功排序后，通過計算期望值，任務(wù)j也能夠被成功排序。例如，在完工期限模型中，可給出完工期限為1-tj-1-μj的概率下界。其中tj-1為當(dāng)任務(wù) j-1已在完工期限內(nèi)完工時，任務(wù)1，…，j-1的總期望加工時間。因此，tj-1不會大于Mj-1，該新下界更強(qiáng)。

3 WSEPT規(guī)則下的E[ ]μ(J)上下界

引理1對于非適應(yīng)性策略P，將任務(wù) j的完工期限概率記為πj，將根據(jù)策略P排序的任務(wù)集記為J，則在開始期限模型中：

再考慮兩種情形。對于所有的 j∈[]n，若μj≤1-tj-1，則有 μj≤zj≤1，故1-zj≥0 。由式（4）可得式（8）的界：

否則，對某個 k，若 μk+1＞1-tk，對于最小的k ，當(dāng) j≤k 時，有 μj≤zj≤1，由式（4）得［7］

證畢。

引理2對于適應(yīng)性策略P，將隨機(jī)任務(wù)集記為 J，有

證明：假設(shè)P為相對于期限d的未來時間，任務(wù)集為R，將集合P從該點開始的隨機(jī)任務(wù)集記為J(d，R)。對于任意任務(wù)集R及R中相互獨立的任意隨機(jī)變量t≤1時，對 ||R進(jìn)行歸納，有

對?j∈R成立，證畢。

4 WSEPT規(guī)則下的期望值上下界

下面討論如何由WSEPT規(guī)則確定的期望值來獲取更優(yōu)的下界，以及由ADAPT規(guī)則獲取更優(yōu)的上界。在開始期限或完工期限模型中，用WSEPT規(guī)則對任務(wù)進(jìn)行排序。若用Wj來定義開始期限模型中的wj及完工期限模型中的w′j，則WSEPT排序為定義［10］

引理3在開始期限和完工期限模型中，ADAPT≤2V。

證明：對于一個最優(yōu)的適應(yīng)性策略P，用xj記P中的排序任務(wù) j的概率。在開始期限和完工期限模型中，在開始期限模型中Wj=wj，在完工期限模型中Wj=w′j。若

證畢。

引理4在開始期限模型中，由WSEPT規(guī)則確定的期望值至少為V。在完工期限模型中，由WSEPT規(guī)則確定的期望值至少為(1 -ε) V 。證明：根據(jù)WSEPT規(guī)則，用πj記在期限內(nèi)完成的任務(wù) j的概率。在開始期限模型中，得到的期望值為［13］

在完工期限模型中，由引理1可得，其期望值為(1 -ε) V 。

5 完工期限模型的4階近似策略［14～15］

以上分析說明在開始期限模型中，WSEPT為一個2階近似非適應(yīng)性策略。在完工期限模型中，用以下兩種解決方式能得到4階非適應(yīng)性策略。

1）若任務(wù) j滿足 w′j≥V 2，則僅排序這個任務(wù)。

2）否則，用WSEPT規(guī)則排序所有任務(wù)。

稱之為最優(yōu)2階策略。

證明：若已排序一個任務(wù)，則得到期望值至少為V 2及ADAPT≤2V，故在該種情形下達(dá)到4階近似?，F(xiàn)考慮用WSEPT規(guī)則排序的情形，將在期限內(nèi)完工的任務(wù) j的概率記為πj，根據(jù)WSEPT規(guī)則，期望值為［16］

為4階近似，證畢。

6 結(jié)語

為解決單機(jī)隨機(jī)排序問題，本文對開始期限及完工期限兩種模型，從期望值角度給出了其上下界，由WSEPT的期望值與最優(yōu)適應(yīng)性策略排序的期望值的關(guān)系來修正上下界。最終給出在完工期限模型下WSEPT規(guī)則的4階近似程度分析。