交换机中周期流优化调度问题的复杂性 |
| |
作者单位: | 扬州大学信息工程学院,东南大学计算机科学与工程学院 |
| |
摘 要: | 研究了交换机中周期流量的优化调度问题,着重讨论了该问题的复杂性.依据呼损率定义了交换机周期流量调度的最优化问题,并对其子问题,嵌套周期流优化调度的复杂性进行了研究.证明了一种受限Max2Sat问题的NP完全性,并通过将该问题多项式归约到交换机周期流量调度的最优化问题,由此证明了仅有1和2周期的交换机周期流优化调度问题是强NPC问题.并利用该结果证明了任意嵌套周期的优化调度问题也是强NPC的.这表明对于任意嵌套周期流优化调度问题不存在伪多项式算法.
|
关 键 词: | 交换机 调度 周期流 硬实时 NP完全 |
Complexity of periodic traffic optimal scheduling problem in switches |
| |
Authors: | Wu Jun Li Wei Li Bin |
| |
Affiliation: | Wu Jun1 Li Wei2 Li Bin1 |
| |
Abstract: | 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. |
| |
Keywords: | switch scheduling periodic traffic hard real-time NPC(non-deterministic polynomial complete) |
本文献已被 CNKI 等数据库收录! |
|