Duality and linear programs for stability and performance analysis of queueing networks and scheduling policies
Duality and linear programs for stability and performance analysis of queueing networks and scheduling policies
复制标题
用于排队网络和调度策略的稳定性和性能分析的对偶和线性程序
DOI：
--
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
Sean P. Meyn
中科院分区：
文献类型：
--
作者：
P. Kumar;Sean P. Meyn
获得各种线性规划，对排队网络和调度策略进行性能分析和稳定性/不稳定性判定。作者展示了系统性能与平均漂移稳定性分析之间的强对偶关系。性能LP限制了所有平稳非空转调度策略的性能。如果它是有界的，那么它的对偶，称为漂移LP，有一个可行解，它是一个合成矩阵。与此合成矩阵相关的二次型具有负漂移，使得作者可以得出结论，所有平稳非空转调度策略在具有几何收敛的指数矩的很强意义下是稳定的。有些系统满足一组辅助的线性约束。它们的性能也受到性能LP的限制，前提是它们是稳定的，即对于零件的数量来说，具有有限的第一力矩。如果Performance LP不可行，则系统不稳定。性能LP对偶的任何可行解都提供了一个负漂移的二次函数。如果这个二次型是合成的，那么系统是强稳定的。否则，系统要么是不稳定的，要么是高度非鲁棒的，因为任意小的扰动都可能导致系统不稳定。这些结果适用于流体模型，允许研究非指数分布的网络。稳定性的另一个LP测试避免了复合性检查。如果单调LP是有界的，那么系统对于所有较小的到达率都是稳定的。最后，有限时间LP提供了系统性能的暂态边界
Obtains a variety of linear programs to conduct the performance analysis and stability/instability determination of queueing networks and scheduling policies. The authors exhibit a strong duality relationship between the performance of a system, and its stability analysis via mean drift. A Performance LP bounds the performance of all stationary non-idling scheduling policies. If it is bounded, then its dual, called the Drift LP, has a feasible solution, which is a copositive matrix. The quadratic form associated with this copositive matrix has a negative drift, allowing the authors to conclude that all stationary non-idling scheduling policies are stable in the very strong sense of having a geometrically converging exponential moment. Some systems satisfy an auxiliary set of linear constraints. Their performance is also bounded by a Performance LP, provided that they are stable, i.e., have a finite first moment for the number of parts. If the Performance LP is infeasible, then the system is unstable. Any feasible solution to the dual of the Performance LP provides a quadratic function with a negative drift. If this quadratic form is copositive, then the system is strongly stable as above. If not, the system is either unstable, or else is highly non-robust in that arbitrarily small perturbations can lead to an unstable system. These results carry over to fluid models, allowing the study of networks with non-exponential distributions. Another LP test of stability avoids a copositivity check. If a Monotone LP is bounded, then the system is stable for all smaller arrival rates. Finally, a Finite Time LP provides transient bounds on the performance of the system.<<ETX>>