Optimal Stochastic Scheduling in Multiclass Parallel Queues of Poisson Arrivals
WANG Yanhong
LEI Songze
ZHANG Wenjuan
LI Rui
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.
Keywords：poisson distributionstochastic schedulingstatic priority policynonlinear programming problem
Publication Date：2024-02-20
Online Publishing Date：2025-08-15(First online date of this platform, not the publication date of the document)
Pages：4( 403-405,422 )