摘要
探讨了分批排序问题,分析了极小化加权总完工时间问题1｜B,rj∈｛0,r｝｜!!jCj的复杂性,证明了此问题的NP-完备性,并对一类特定问题进行了研究,给出了解决问题的近似算法,证明了其可行性,进而对算法的性能进行了分析,结果表明算法有效地降低了计算复杂度。
The problem of batch scheduling is discussed especially the problem, of minimizing the total weighted completed time,namely problems 1｜B,rj=∈{0,r}｜∑ωjCjBesides its analyzed and the NP-completeness is proved.Then this paper focuses on a class of special case of the problem and proposes an approximated algorithm to solve the problem.The proof showes that it is feasible and its capability is improved.
出处
《计算机工程与应用》
CSCD
北大核心
2007年第3期175-178,共4页
Computer Engineering and Applications
基金
河南省自然科学基金资助项目(0411010500)。
关键词
分批排序
复杂度
近似算法
NP完备性
性能分析
batch scheduling
complexity
approximated algorithm
NP-completeness
capability analysis
