最优箭线图的判定与唯一性

闻振卫

系统工程理论与实践 ›› 1999, Vol. 19 ›› Issue (3) : 1-12.

PDF(286 KB)
PDF(286 KB)
系统工程理论与实践 ›› 1999, Vol. 19 ›› Issue (3) : 1-12. DOI: 10.12011/1000-6788(1999)3-1
论文

最优箭线图的判定与唯一性

    闻振卫
作者信息 +

The Judgement and Uniqueness of Optimal Arrow Diagram

    Zhen Wei WEN
Author information +
文章历史 +

摘要

统筹图又叫计划网络图或箭线(工程)图.任给一个有限偏序集(简称序集,其元素叫做工序或作业),要绘制它的一个最优统筹图(含虚工序数最少者)是一个尚未解决的困难问题.本文给出了一个判定一序集存在唯一最优箭线图的充分条件以及绘制这类序集的最优箭线图的方法;并指出:若P一个序集满足W-free和M-free,则P的最优箭线图唯一且可在多项式时间内作出.

Abstract

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.

关键词

序集 / 箭线图 / 统筹图 / 虚工序 / 框图

Key words

partially ordered set / arrow diagram / PERT network / diagram

引用本文

导出引用
闻振卫. 最优箭线图的判定与唯一性. 系统工程理论与实践, 1999, 19(3): 1-12 https://doi.org/10.12011/1000-6788(1999)3-1
Zhen Wei WEN. The Judgement and Uniqueness of Optimal Arrow Diagram. Systems Engineering - Theory & Practice, 1999, 19(3): 1-12 https://doi.org/10.12011/1000-6788(1999)3-1
PDF(286 KB)

Accesses

Citation

Detail

段落导航
相关文章

/