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

Complexity of periodic traffic optimal scheduling problem in switches

作　　者：吴俊[1] 李伟[2] 李斌[1] 

机构地区：[1]扬州大学信息工程学院,扬州225009 [2]东南大学计算机科学与工程学院,南京210096

出　　处：《东南大学学报（自然科学版）》2008年第A01期8-11,共4页Journal of Southeast University：Natural Science Edition

基　　金：江苏省自然科学基金资助项目(06KJB520132);江苏省教育厅自然科学基金资助项目(06KJB520132)

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

关 键 词：交换机 调度 周期流 硬实时 NP完全 

分 类 号：U459.2[建筑科学—桥梁与隧道工程]