到达时间服从泊松分布的平行机队列的最优随机排序问题  

Optimal Stochastic Scheduling in Multiclass Parallel Queues of Poisson Arrivals

作　　者：王艳红 雷松泽[2] 张文娟 李蕊 WANG Yanhong;LEI Songze;ZHANG Wenjuan;LI Rui(School of Freshman,Xi'an Technological University,Xi'an 710021;School of Computer Science and Engineering,Xi'an Technological University,Xi'an 710021;School of Science,Xi'an Technological University,Xi'an 710021)

机构地区：[1]西安工业大学新生院,西安710021 [2]西安工业大学计算机科学与工程学院,西安710021 [3]西安工业大学基础学院,西安710021

出　　处：《计算机与数字工程》2024年第2期403-405,422,共4页Computer & Digital Engineering

基　　金：2021年陕西省科技厅面上项目(编号:2021JM-440)资助。

摘　　要：论文考虑多个分布下,根据每类加工时间函数最小化目标函数的不同类别的随机排序问题。这个问题常出现在分布式系统、网络和应用程序方面。模型中,最优排序策略在每台机器上是一个简单的静态优先策略。在这种排序策略下,排序问题可以寻找到最佳路径矩阵。考虑一个非线性规划问题,证明了任何局部最优即为全局最优,大大简化了,优化问题的解决方案。在到达时间为泊松分布的情形下,论文提供了一个最佳的排序策略,能够最小化每类时间函数。对一般各种静态实例应用此方法,可得到简单的近似算法。This paper considers the problem of scheduling different classes of customers on multiple distributed servers to minimize 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 optimal 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 response time variances.Applying this analysis to various static instances of the general problem leads to rederive many results,yielding simple approximation algorithms whose guarantees match the best known results.

关 键 词：泊松分布 随机排序 静态优先策略 非线性规划 

分 类 号：O223[理学—运筹学与控制论]