交换机中周期流优化调度问题的复杂性

研究了交换机中周期流量的优化调度问题,着重讨论了该问题的复杂性.依据呼损率定义了交换机周期流量调度的最优化问题,并对其子问题,嵌套周期流优化调度的复杂性进行了研究.证明了一种受限Max2Sat问题的NP完全性,并通过将该问题多项式归约到交换机周期流量调度的最优化问题,由此证明了仅有1和2周期的交换机周期流优化调度问题是强NPC问题.并利用该结果证明了任意嵌套周期的优化调度问题也是强NPC的.这表明对于任意嵌套周期流优化调度问题不存在伪多项式算法.

Complexity of periodic traffic optimal scheduling problem in switches

The multi-ate periodic traffic scheduling problem in switches has been investigated,especially on the complexity of the problem.An optimal scheduling problem in terms of switch call congestion ration is proposed,and its sub-problem,i.e.,nested multi-ate periodic traffic scheduling problem is also studied.A restricted Max2Sat problem is proved to be NP(non-deterministic polynomial) complete,and by reducing this problem to optimal scheduling problem with only one and two periods,it is proved that the problem is also strongly NPC(non-deterministic polynomial complete).And this result is generalized to show that any nested periodic traffic optimal scheduling problems are also strongly NPC,which means there is no pseudo-polynomial time algorithm to solve these problems.