Optimal Stochastic Scheduling in Multiclass Parallel Queues of Poisson Arrivals
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.
poisson distributionstochastic schedulingstatic priority policynonlinear programming problem
国家科技期刊平台
NSTL
万方数据
