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

?

任務(wù)到達(dá)時(shí)間服從泊松分布的隨機(jī)排序*

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

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

關(guān)鍵詞：隨機(jī)排序；到達(dá)時(shí)間；泊松分布；多項(xiàng)式最優(yōu)算法

基金資助：陜西省教育廳項(xiàng)目（15JK1371）

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

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

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

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

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

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

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

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

式（3）等價(jià)于

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

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

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

也可表示為

由 V＝V1＋V2

得

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

最小化該目標(biāo)函數(shù)等價(jià)于最小化

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

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

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

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

3　結(jié)論

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

參考文獻(xiàn)：

［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ī)排序模型及求解方法［J］．?dāng)?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］ 錢頌迪．運(yùn)籌學(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)計(jì)［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．

（責(zé)任編輯、校對 張立新）

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àn)榻M合最優(yōu)化．E-mail：wyhmath＠yeah．net．

*收稿日期：2015-03-23

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

文獻(xiàn)標(biāo)志碼：中圖號(hào)： O223 A

文章編號(hào)：1673-9965（2016）01-0005-03