凸优化方法及其在排队系统中的应用研究

The Convex Optimization Method and Its Applications to Queuing Systems

理论上可以证明严格凸优化问题有惟一的全局最优解;应用中有快速的多项式时间算法求解这一全局最优解。因此对难于解决的排队系统性能指标优化问题,如负荷配置问题,可以利用排队系统的凸性应用凸优化方法求解。本文基于排队理论建立排队系统负荷配置的非线性优化模型,设计一种优化变量转换方法并经适当的约束条件合并将该模型转换为凸优化模型,并引入凸优化内点法作为负荷配置的有效计算工具。实例计算结果表明,基于排队理论的非线性凸优化模型,其优化结果能保证充分利用设备的生产能力及最低的在制品库存;同时凸优化内点算法具有迭代次数少、收敛速度快的优点;涉及排队系统中其他性能指标的优化问题,也可以采用类似的方法求其最优解。

Theoretically, for a strictly convex problem, there is a unique global solution; practically, when put in the right form, convex optimization can be globally solved by fast polynomial time algorithms. Therefore, intractable optimization (problems) of performance measures of queuing systems can be solved by this method. Based on the queuing theory, a (nonlinear) load optimal allocation model is proposed in this paper. A novel transformation of the optimization variables is also devised and the constraints are properly combined so as to make this model into a convex one. The interior-point method for convex optimization is presented here as a computationally efficient tool. Finally, this model is evaluated on a real example, from which such conclusions are drawn that the optimum result can ensure the full utilization of machines and the least (amount) of work-in-process(WIP) in queuing systems; the interior-point method needs fewer iterations with significant (computational) savings; other performance measures of queuing systems can also be optimized in the similar way.