單機隨機排序問題的WSEPT規則近似?

王艷紅 雷松澤 張文娟 李 蕊

（1.西安工業大學理學院 西安 710021）（2.西安工業大學計算機科學與工程學院 西安 710021）

1 引言

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

2 問題描述

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

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

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

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

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

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

證畢。

引理2對于適應性策略P，將隨機任務集記為 J，有

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

對?j∈R成立，證畢。

4 WSEPT規則下的期望值上下界

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

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

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

證畢。

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

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

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

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

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

2）否則，用WSEPT規則排序所有任務。

稱之為最優2階策略。

證明：若已排序一個任務，則得到期望值至少為V 2及ADAPT≤2V，故在該種情形下達到4階近似。現考慮用WSEPT規則排序的情形，將在期限內完工的任務 j的概率記為πj，根據WSEPT規則，期望值為［16］

為4階近似，證畢。

6 結語

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