摘要
统筹图又叫计划网络图或箭线（工程）图．任给一个有限偏序集（简称序集，其元素叫做工序或作业），要绘制它的一个最优统筹图（含虚工序数最少者）是一个尚未解决的困难问题．本文给出了一个判定一序集存在唯一最优箭线图的充分条件以及绘制这类序集的最优箭线图的方法；并指出：若Ｐ一个序集满足Ｗ－ｆｒｅｅ和Ｍ－ｆｒｅｅ，则Ｐ的最优箭线图唯一且可在多项式时间内作出．
Given a finite partially ordered set (poset), the elements of which are called tasks, it is a hard problem to construct its optimal PERT network, the one with the smallest number of dummy tasks. In this paper it is presented a method for constructing the optimal arrow diagram for a type of posets which are W free or M free with height 2. It is also shown that: if a poset P is W free and M free, then the optimal arrow diagram of P is unique, which can be constructed in a polynomial time.
出处
《系统工程理论与实践》
EI
CSCD
北大核心
1999年第3期1-12,52,共13页
Systems Engineering-Theory & Practice
关键词
序集
箭线图
统筹图
虚工序
框图
唯一性
partially ordered set
arrow diagram
PERT network
diagram
