检索结果-内蒙古大学图书馆

Heavy traffic analysis of multi-class bipartite queueing systems under FCFS

queueing systemS 2024年第3-4期106卷 239-284页

作者： Hillas, Lisa Aoki Caldentey, Rene Gupta, Varun Univ Auckland ISOM Dept Auckland New Zealand Northwestern Univ Dept Comp Sci Evanston IL USA

This paper examines the performance of multi-class, multi-server bipartite queueing systems, where each arriving customer is compatible with only a subset of servers. We focus on the system's performance under a first-come, first-served-assign longest idle server service discipline. In this discipline, an idle server is matched with the compatible customer who has been waiting the longest, and a customer who can be served by multiple idle servers is routed to the server that has been idle for the longest period. We analyse the system under conventional heavy-traffic conditions, where the traffic intensity approaches one from below. Building upon the formulation and results of Afeche et al. (Oper Res 70(1):363-401, 2022), we generalize the model by allowing the vector of arrival rates to approach the heavy-traffic limit from an arbitrary direction. We characterize the steady-state waiting times of the various customer classes and demonstrate that a much wider range of waiting time outcomes is achievable. Furthermore, we establish that the matching probabilities, i.e. the probabilities of different customer classes being served by different servers, do not depend on the direction along which the system approaches heavy traffic. We also investigate the design of compatibility between customer classes and servers, finding that a service provider who has complete control over the matching can design a delay-minimizing matching by considering only the limiting arrival rates. When some constraints on the compatibility structure exist, the direction of convergence to heavy-traffic affects which compatibility structure minimizes delay. Additionally, we discover that the bipartite matching queueing system exhibits a form of Braess's paradox, where adding more connectivity to an existing system can lead to higher average waiting times, despite the fact that neither customers nor servers act strategically.

关键词： multi-class queueing system First-come-first-served Bipartite matching Steady-state analysis

来源：评论

学校读者我要写书评

暂无评论

On the Optimal Design of a Bipartite Matching queueing system

引用

OPERATIONS RESEARCH 2022年第1期70卷 363-401页

作者： Afeche, Philipp Caldentey, Rene Gupta, Varun Univ Toronto Rotman Sch Management Toronto ON M5S 3E6 Canada Univ Chicago Booth Sch Business Chicago IL 60637 USA

We consider a multiclass multiserver queueing system and study the problem of designing an optimal matching topology (or service compatibility structure) between customer classes and servers under a first come first served-assign longest idle server (FCFS-ALIS) service discipline. Specifically, we are interested in finding matching topologies that optimize-in a Pareto efficiency sense-the trade-off between two competing objectives: (i) minimizing customers' waiting time delays and (ii) maximizing matching rewards generated by pairing customers and servers. Our analysis of the problemis divided into three main parts. First, under heavy-traffic conditions, we show that any bipartite matching system can be partitioned into a collection of complete resource pooling (CRP) subsystems, which are interconnected by means of a direct acyclic graph (DAG). We show that this, together with the aggregate service capacity on each CRP, fully determines the vector of steady-state waiting times. In particular, we show that the average (scaled) steady-state delay across all customer classes is asymptotically equal to the number of CRP components divided by the total system capacity. Second, since computing matching rewards under a FCFS-ALIS service discipline is computationally infeasible as the number of customer classes and servers grow large, we propose a quadratic programming (QP) formulation to approximate matching rewards. We show that the QP formulation is exact for a number of instances of the problem and provides a very good approximation in general. Extensive numerical experiments show that in over 98% of problem instances the relative error between the exact rewards and the QP approximate rewards is less than 2%. Lastly, combining our characterization of average delays in terms of the number of CRP components and the QP formulation to compute matching rewards, we propose a mixed-integer linear program that can be used to find the set of matching topologies that define the P

关键词： multi-class queueing system first-come-first-served bipartite matching steady-state analysis flexibility design

来源：评论

学校读者我要写书评

暂无评论

Linear programming relaxations and marginal productivity index policies for the buffer sharing problem

引用

queueing systemS 2008年第3-4期60卷 247-269页

作者： Cao, Jianhua Nyberg, Christian Lund Univ Elect & Informat Technol Dept S-22100 Lund Sweden

We study the dynamic admission control for a finite shared buffer with support of multiclass traffic under Markovian assumptions. The problem is often referred to as buffer sharing in the literature. From the linear programming (LP) formulation of the continuous-time Markov decision process (MDP), we construct a hierarchy of increasingly stronger LP relaxations where the hierarchy levels equal the number of job classes. Each relaxation in the hierarchy is obtained by projecting the original achievable performance region onto a polytope of simpler structure. We propose a heuristic policy for admission control, which is based on the theory of Marginal Productivity Index (MPI) and the Lagrangian decomposition of the first order LP relaxation. The dual of the relaxed buffer space constraint in the first order LP relaxation is used as a proxy to the cost of buffer space. Given that each of the decomposed queueing admission control problems satisfies the indexability condition, the proposed heuristic accepts a new arrival if there is enough buffer space left and the MPI of the current job class is greater than the incurred cost of buffer usage. Our numerical examples for the cases of two and eight job classes show the near-optimal performance of the proposed MPI heuristic.

关键词： Buffer sharing problem multi-class queueing system Linear programming relaxation Marginal productivity index policy Markov decision process 60K25 60K30 68M20 90B05 90B22 90B18 90C08 90C40 90C59

来源：评论

学校读者我要写书评

暂无评论

An analysis of Klimov's problem with parallel servers

引用

MATHEMATICAL METHODS OF OPERATIONS RESEARCH 2003年第1期58卷 1-28页

作者： Glazebrook, KD Univ Edinburgh Sch Management Edinburgh EH8 9JY Midlothian Scotland

We introduce a family of undiscounted branching bandits on parallel servers under controls which can impose priorities between customer classes. This family can be used to model a wide range of multi-class queueing scheduling problems, with the capacity to incorporate problem features such as machine breakdowns, complex patterns of preemption/non-preemption and semi-Markov extensions. An index policy (which we call Klimov's rule) is developed which is optimal in the particular case of a single server. An expression for its cost suboptimality is given for parallel servers. Under additional conditions on the nature of the stochastic evolution of the systems concerned, the policy is shown to be asymptotically optimal in a heavy traffic limit. These general results are utilised to develop an analysis of the index policy for a parallel server version of Klimov's classical M/GI/1 system with Bernoulli feedback.

关键词： achievable region branching bandit Gittins index imposed priorities Klimov network multi-class queueing system parallel scheduling

来源：评论

学校读者我要写书评

暂无评论

A semidefinite programming approach to the optimal control of a single server queueing system with imposed second moment constraints

引用

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY 1999年第7期50卷 765-773页

作者： Ansell, PS Glazebrook, KD Mitrani, I Niño-Mora, J Univ Newcastle Upon Tyne Sch Math & Stat Newcastle Upon Tyne NE1 7RU Tyne & Wear England

classical analyses of the dynamic control of multi-class queueing systems frequently yield simple priority policies as optimal. However, such policies can often result in excessive queue lengths for the low priority jobs/customers. We propose a stochastic optimisation problem in the context of a two class M/M/1 system which seeks to mitigate this through the imposition of constraints on the second moments of queue lengths. We analyse the performance of two families of parametrised heuristic policies for this problem. To evaluate these policies we develop lower bounds on the optimum cost through the achievable region approach. A numerical study points to the strength of performance of threshold policies and to directions for future research.

关键词： achievable region Gittins index multi-class queueing system semidefinite program stochastic optimisation

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：