王艷紅，李　蕊，張文娟（西安工業(yè)大學(xué)理學(xué)院，西安710021）

?

任務(wù)到達時間服從泊松分布的隨機排序*

王艷紅，李蕊，張文娟
（西安工業(yè)大學(xué)理學(xué)院，西安710021）

摘 要：研究在多項式時間內(nèi)任務(wù)到達時間服從泊松分布的隨機排序，描述了一類特殊的單機隨機排序問題，文中基于任務(wù)到達時間服從泊松分布，給出了該問題的多項式最優(yōu)算法，證明得出在不可中斷動態(tài)策略下有最優(yōu)解，最短期望加工時間優(yōu)先規(guī)則為其多項式最優(yōu)算法．

關(guān)鍵詞：隨機排序；到達時間；泊松分布；多項式最優(yōu)算法

基金資助：陜西省教育廳項目（15JK1371）

排序問題也稱調(diào)度問題，包含隨機變量的排序問題即為隨機排序問題［1］．對于不確定性問題，很多近似算法已經(jīng)被提出，如最優(yōu)搜尋算法，蟻群算法，遺傳算法，機器規(guī)劃，基于尋找策略的人工智能，支配或啟發(fā)式算法以及商業(yè)化的有限容量排序等．隨機排序在經(jīng)濟管理和計算機領(lǐng)域中較常出現(xiàn)，給出隨機排序問題（調(diào)度問題）的最優(yōu)算法，可用于指導(dǎo)生產(chǎn)，優(yōu)化生產(chǎn)．對于隨機排序問題，由于隨機變量的不確定性，很多隨機排序問題無多項式最優(yōu)算法，而我們對任務(wù)的到達時間，等待時間或目標函數(shù)加以約束，可能會得到該問題的多項式最優(yōu)算法．文獻［2-3］證明了最短期望加工時間優(yōu)先（Weighted Shortest Expected Processing Time Eirst，WSEPT）規(guī)則為問題的最優(yōu)算法，而該問題對應(yīng)的確定性問題等價于背包問題［4-5］為NP-難問題．任務(wù)的到達時間服從各種分布的隨機排序問題已經(jīng)得到了廣泛的研究，并形成了一定的研究成果．這些模型已經(jīng)廣泛應(yīng)用于計算機應(yīng)用和系統(tǒng)環(huán)境，以及通信網(wǎng)絡(luò)環(huán)境中．針對任務(wù)的到達時間服從泊松分布的隨機排序問題，文中基于泊松分布“流”分布特性，證明該類問題有多項式最優(yōu)算法．

1　問題描述與預(yù)備知識

設(shè)任務(wù)在一臺機器上加工，任務(wù)的到達時間服從泊松分布［1-2］，為泊松流，即

式中：rj為第j類任務(wù)的到達時間；t為時間；v為任務(wù)到達的速率；N（t）為任務(wù)數(shù)以時間t到達的隨機變量；l為N（t）的實數(shù)值．

考慮任務(wù)的到達速率分別為v1和v2的兩個任務(wù)類，兩個類的到達時間是相互獨立的泊松流．加工時間分布分別為G1（x）和G2（x），其中x為加工時間，記E（Wq1）和E（Wq2）分別為任務(wù)類1和任務(wù)類2在隊伍中的平均等待．

在機器上按照先到先服務(wù)（Eirst Come Eirst Served，ECES）原則［3］進行加工．在ECES原則下，該問題等價于任務(wù)的到達速率為v＝v1＋v2的一個任務(wù)類問題，即

若問題中每個任務(wù)在單位加工時間內(nèi)需支付1．00元，若一任務(wù)需加工x個單位時間，則需支付x元．現(xiàn)把兩個任務(wù)推廣為n個，設(shè)任務(wù)類k（1，…，n）有權(quán)重wk元．對于任務(wù)的到達時間服從松柏分布的隨機排序問題，由于到達時間為一個“流”，目標函數(shù)為任務(wù)的最小平均價值［4-5］，即

式中：vk為第k類任務(wù)的到達速率；E（Wqk）為第k類任務(wù)的平均等待．

式（3）等價于

該隨機排序問題用三參數(shù)法［6］表示為

2　隨機排序問題的最優(yōu)算法

證明 將系統(tǒng)中任務(wù)數(shù)的隨機變量［7-8］記為V，有

也可表示為

由 V＝V1＋V2

得

該問題的目標函數(shù)［9］為

最小化該目標函數(shù)等價于最小化

證明基于兩個鄰接任務(wù)類的互換．設(shè)n≥3，任務(wù)類2與任務(wù)類3沒有按照λjωj規(guī)則排列，設(shè)任務(wù)類2排在任務(wù)類3之前，即

記∑（2，3）為當任務(wù)類2排在任務(wù)類3前的價值，具體為

∑（3，2）為當任務(wù)類3排在任務(wù)類2前的價值［10］．

可通過調(diào)換任務(wù)類2與任務(wù)類3來減少目標函數(shù)值．以上證明可一般化為任務(wù)類k與任務(wù)類k＋1（k＞1）．由此，WSEPT規(guī)則可實現(xiàn)該問題的最優(yōu)．

3　結(jié)論

文中對任務(wù)的到達時間服從泊松分布的隨機排序問題進行了研究，證明得出在不可中斷動態(tài)策略下有最優(yōu)解，WSEPT規(guī)則為該問題的最優(yōu)算法．上述證明得出該類問題可在多項式時間內(nèi)得以解決，滿足了我們的最優(yōu)要求，對實際的生產(chǎn)實踐有其指導(dǎo)意義．

參考文獻：

［1］ 唐恒永，趙傳立．排序引論［M］．北京：科學(xué)出版社，2002．TANG Hengyong，ZHAO Chuanli．Introduction to Scheduling［M］．Beijing：Science Press，2002．（in Chinese）

［2］ PINEDO M L．Scheduling-Theory，Algorithms and Systems［M］．Englewood Cliffs：Prentice Hall，1995．

［3］ 唐恒永．隨機排序模型及求解方法［J］．數(shù)學(xué)理論與應(yīng)用，1999，19（3）：22．TANG Hengyong．Model of Stochastic Scheduling and Solving Method［J］．Mathematical Theory and Application，1999，19（3）：22．（in Chinese）

［4］ 錢頌迪．運籌學(xué)［M］．北京：清華大學(xué)出版社，1990．QIAN Songdi．Operational Research［M］．Beijing：Tsinghua University Press，1990．（in Chinese）

［5］ PAPADIMITRIOU C H，STEIGLITZ K．Combinatorial Optimization：Algorithms and Complexity［M］．New York：Dover Publications Inc，1998．

［6］ 梁之舜．概率論與數(shù)理統(tǒng)計［M］．北京：高等教育出版社，2001．LIANG Zhishun．Probability and Statistics［M］．Beijing：Higher Education Press，2001．（in Chinese）

［7］ LI W，GLAZEBROOK K D．Stochastic Machine Scheduling with General Distributional Assumptions［J］．European Journal of Operational Research，1999，105 （3）：525．

［8］ WEBER R R，VARAIYA P，WALRAND J．Scheduling Jobs with Stochastically Ordered Processing Times on Parallel Machines to Minimize Expected Elowtime［J］．Journal of Applied Probability，1986，23：841．

［9］ KAMPKE T．On the Optimality of Static Priority Policies in Stochastic Scheduling on Parallel Machines ［J］．Journal of Applied Probability，1987，24：430．

［10］ PINEDO M．Stochastic Scheduling with Release Dates and Due Dates［J］．Operation Research，1983，31 （3）：559．

（責任編輯、校對 張立新）

Stochastic Scheduling Problems of Releases Times Obeying Poisson Distribution

WANG Yanhong，LI Rui，ZH ANG Wenjuan
（School of Science，Xi’an Technological University，Xi’an 710021，China）

Abstract：A class of single machine stochastic scheduling problems with the releases times obeying Poisson distribution are discussed in this paper to solve the stochastic scheduling problems in polynomial time．Based on the specific property of Poisson distribution，the polynomial optimal algorithm is presented．It is proved that the optimal algorithm is the rule of weighted shortest expected processing time first under the nonpreemptive dynamic policy．

Key words：stochastic schedule；releases times；poisson distribution；polynomial optimal algorithm

作者簡介：王艷紅（1981－），女，西安工業(yè)大學(xué)講師，主要研究方向為組合最優(yōu)化．E-mail：wyhmath＠yeah．net．

*收稿日期：2015-03-23

DOI：10．16185／j．jxatu．edu．cn．2016．01．002

文獻標志碼：中圖號： O223 A

文章編號：1673-9965（2016）01-0005-03