枣庄学院学报
棘莊學院學報
조장학원학보
JOURNAL OF ZAOZHUANG UNIVERSITY
2010年
5期
36-38
,共3页
可拒绝分批排序%动态规划%NP-难%到达时间
可拒絕分批排序%動態規劃%NP-難%到達時間
가거절분비배서%동태규화%NP-난%도체시간
研究了一类极小化加权总完工时间的可拒绝分批排序问题.首先证明了该问题是NP-难的,然后对于所有工件的加工时间相同的情况,给出了时间复杂性为O(n2)的动态规划算法,在此基础上,对于工件有两种到达时间的情况给出了多项式时间算法.
研究瞭一類極小化加權總完工時間的可拒絕分批排序問題.首先證明瞭該問題是NP-難的,然後對于所有工件的加工時間相同的情況,給齣瞭時間複雜性為O(n2)的動態規劃算法,在此基礎上,對于工件有兩種到達時間的情況給齣瞭多項式時間算法.
연구료일류겁소화가권총완공시간적가거절분비배서문제.수선증명료해문제시NP-난적,연후대우소유공건적가공시간상동적정황,급출료시간복잡성위O(n2)적동태규화산법,재차기출상,대우공건유량충도체시간적정황급출료다항식시간산법.
