洛阳理工学院学报（自然科学版）
洛暘理工學院學報（自然科學版）
락양리공학원학보（자연과학판）
JOURNAL OF LUOYANG INSTITUTE OF SCIENCE AND TECHNOLOGY
2012年
4期
79-83
,共5页
排序%批处理机%链优先约束%算法复杂性
排序%批處理機%鏈優先約束%算法複雜性
배서%비처리궤%련우선약속%산법복잡성
讨论问题1| chains,B|Cmax具体可描述为:有m条链,其中一条链上有n个工件,其余的m-1条链上的工件数之和为常数k,且工件的加工时间不限制,目标函数为最大完工时间.我们对该问题B=2的情况进行了深入的探讨,在研究过程中首次提出“合成链“算法,给出了时间复杂性为O(nk)的多项式时间算法.
討論問題1| chains,B|Cmax具體可描述為:有m條鏈,其中一條鏈上有n箇工件,其餘的m-1條鏈上的工件數之和為常數k,且工件的加工時間不限製,目標函數為最大完工時間.我們對該問題B=2的情況進行瞭深入的探討,在研究過程中首次提齣“閤成鏈“算法,給齣瞭時間複雜性為O(nk)的多項式時間算法.
토론문제1| chains,B|Cmax구체가묘술위:유m조련,기중일조련상유n개공건,기여적m-1조련상적공건수지화위상수k,차공건적가공시간불한제,목표함수위최대완공시간.아문대해문제B=2적정황진행료심입적탐토,재연구과정중수차제출“합성련“산법,급출료시간복잡성위O(nk)적다항식시간산법.
