摘要
为了能在多项式时间内解决随机排序问题,针对一类特殊的单机随机排序问题1|pj^exp(jλ)|E(∑wjDj)进行研究,分别从不可中断情形和可中断情形证明,得出由于指数分布的特性,该问题均有多项式最优算法,其最优算法为WSEPT规则。
In order to solve stochastic scheduling problems in polynomial time, we studied a class of single machine stochastic scheduling problems 1｜Pj～exp（λj）｜E（∑wjDj）.It is proved that because of the specific property of exponential distribution, the problems have polynomial optimal algorithms in both nonpreemptive and preemptive situation. Its optimal algorithm is WSEPT rule.
出处
《河北科技大学学报》
CAS
2008年第4期286-288,298,共4页
Journal of Hebei University of Science and Technology
关键词
随机排序
指数分布
优先策略
中断
stochastic schedule
exponential distribution
priority policy
preemption
