一类分批排序问题的复杂性分析及近似算法OA北大核心CSCDCSTPCD
Complexity analysis of class of problems on batch scheduling and its approximated algorithm
探讨了分批排序问题,分析了极小化加权总完工时间问题1|B,rj∈{0,r}|∑ωjCj的复杂性,证明了此问题的NP-完备性,并对一类特定问题进行了研究,给出了解决问题的近似算法,证明了其可行性,进而对算法的性能进行了分析,结果表明算法有效地降低了计算复杂度.
张建伟;张保威;郭云飞
信息工程大学,国家数字交换系统工程技术研究中心,郑州,450002郑州轻工业学院,计算机与通信工程学院,郑州,450002郑州轻工业学院,计算机与通信工程学院,郑州,450002
信息技术与安全科学
分批排序复杂度近似算法NP完备性性能分析
《计算机工程与应用》 2007 (3)
175-178,4
河南省自然科学基金资助项目(0411010500).
评论