CAJ | 학술논문

针对成本约束有向无环图DAG(directed acyclic graph)表示的网格工作流完工时间最小化问题,提出两个基于优先级规则的迭代启发算法.算法利用并行活动特征定义正向分层和逆向分层两个概念,将其分别引入最大收益规则MP(maximum profit),得到正分层最大收益规则MPTL(maximum profit with top level)和逆分层最大收益规则MPBL(maximum profit with bottom level).两规则每次迭代尽量以完工时间的最小增加换取总费用的最大降低,逐步将分层初始解构造为满足成本约束的可行解.模拟结果表明,两规则在获得较少迭代次数和运行时间的同时,能显著改进MP规则的平均性能,且MPBL优于MPTL.
침대성본약속유향무배도DAG(directed acyclic graph)표시적망격공작류완공시간최소화문제,제출량개기우우선급규칙적질대계발산법.산법이용병행활동특정정의정향분층화역향분층량개개념,장기분별인입최대수익규칙MP(maximum profit),득도정분층최대수익규칙MPTL(maximum profit with top level)화역분층최대수익규칙MPBL(maximum profit with bottom level).량규칙매차질대진량이완공시간적최소증가환취총비용적최대강저,축보장분층초시해구조위만족성본약속적가행해.모의결과표명,량규칙재획득교소질대차수화운행시간적동시,능현저개진MP규칙적평균성능,차MPBL우우MPTL.