到达时间服从泊松分布的平行机队列的最优随机排序问题
Optimal Stochastic Scheduling in Multiclass Parallel Queues of Poisson Arrivals
王艳红 1雷松泽 2张文娟 3李蕊1
作者信息
- 1. 西安工业大学新生院 西安 710021
- 2. 西安工业大学计算机科学与工程学院 西安 710021
- 3. 西安工业大学基础学院 西安 710021
- 折叠
摘要
论文考虑多个分布下,根据每类加工时间函数最小化目标函数的不同类别的随机排序问题.这个问题常出现在分布式系统、网络和应用程序方面.模型中,最优排序策略在每台机器上是一个简单的静态优先策略.在这种排序策略下,排序问题可以寻找到最佳路径矩阵.考虑一个非线性规划问题,证明了任何局部最优即为全局最优,大大简化了,优化问题的解决方案.在到达时间为泊松分布的情形下,论文提供了一个最佳的排序策略,能够最小化每类时间函数.对一般各种静态实例应用此方法,可得到简单的近似算法.
Abstract
This paper considers the problem of scheduling different classes of customers on multiple distributed servers to min-imize an objective function based on per-class mean processing times.This problem arises in a wide range of distributed systems,networks and applications.Within the context of this model,it observes that the optimal sequencing strategy at each of the servers is a simple static priority policy.Using this observation,it argues that the globally optimal scheduling problem reduces to finding an op-timal routing matrix under this sequencing policy.It formulates the latter problem as a nonlinear programming problem and show that any interior local minimum is a global minimum,which significantly simplifies the solution of the optimization problem.In the case of poisson arrivals,this paper provides an optimal scheduling strategy that also tends to minimize a function of the per-class re-sponse time variances.Applying this analysis to various static instances of the general problem leads to rederive many results,yield-ing simple approximation algorithms whose guarantees match the best known results.
关键词
泊松分布/随机排序/静态优先策略/非线性规划Key words
poisson distribution/stochastic scheduling/static priority policy/nonlinear programming problem引用本文复制引用
基金项目
2021年陕西省科技厅面上项目(2021JM-440)
出版年
2024
国家科技期刊平台
NSTL
万方数据