论文研究-最优箭线图的判定与唯一性.pdf
需积分: 11 38 浏览量
2019-09-20
10:16:06
上传
评论
收藏 285KB PDF 举报
1999 年 3 月 系统工程理论与实践 第 3 期
最优箭线图的判定与唯一性
α
闻振卫
(
苏州大学 数学科学学院, 江苏 苏州 215006
)
摘要 统筹图又叫计划网络图或箭线
(
工程
)
图. 任给一个有限偏序集
(
简称序集, 其元素叫做工序或
作业
)
, 要绘制它的一个最优统筹图
(
含虚工序数最少者
)
是一个尚未解决的困难问题. 本文给出了一
个判定一序集存在唯一最优箭线图的充分条件以及绘制这类序集的最优箭线图的方法; 并指出: 若
P
一个序集满足
W
2
free
和
M
2
free
, 则
P
的最优箭线图唯一且可在多项式时间内作出.
关键词 序集 箭线图 统筹图 虚工序 框图
The Judgem ent and U niqueness
of Op tim al A rrow D iagram
W EN Zhenw ei
(
Suzhou U niversity
,
Suzhou
215006
)
Abstract
Given a finite partially o rdered set
(
poset
)
,
the elem ents of w hich are called
tasks
,
it is a hard p roblem to construct its op tim al PERT netwo rk
,
the one w ith the
sm allest num ber of dumm y tasks
.
In this paper it is p resented a m ethod for constructing
the op tim al arrow diagram fo r a type of po sets w hich areW
2
free o r M
2
free w ith height
2.
It is also show n that
:
if a po set
P
isW
2
free andM
2
free
,
then the op tim al arrow dia2
gram of
P
is unique
,
w hich can be constructed in a polynom ial tim e
.
Keywords
partially o rdered set
;
arrow diagram
;
PERT netwo rk
;
diagram
1 基本概念, 引言
一个偏序集
(
P
, Φ
)
, 也叫序集或有序集, 以下简称序集, 简记作
P
, 它是由一个集合
P
和
P
上的一个
满足自反性、传递性和反对称性的二元关系“Φ ”组成的. 本文只讨论有限序集. 并把序集的元素叫做工序
(
或作业
)
.
若在序集
P
上,
x
Φ
y
且
x
≠
y
, 则称
x
是
y
的一个前工序, 并记作
x
<
y
(
P
)
或
x
<
y
, 或
y
>
x
; 若
x
<
y
(
P
)
; 且不存在
z
∈
P
使
x
<
z
<
y
(
P
)
, 则称
x
是
y
的一个紧前工序, 也叫
y
复盖
x
, 并记作
x
;
y
(
P
)
或
x
;
y
, 或
y
:
x
, 若在
P
上
x
Κ
y
且
y
Κ
x
, 则称在
P
上
x
与
y
不可比, 并记作
x
‖
y
(
P
)
或
x
‖
y
. 序集
P
的框图
(
节点图
)
D
(
P
)
是一个满足如下条件的有向图: 当且仅当
x
;
y
(
P
)
时, 点
x
到点
y
有一条有向弧
(
边
)
, 并且
把点
y
绘制在水平高度高于点
x
的任何处, 并省去有向弧的箭头.
例 1 下面的
(
1
)
和
(
2
)
都表示同一序集
P
:
1
)
P
和其上的紧前关系由表 1 给出:
表 1
工序名称
x
1
x
2
x
3
x
4
x
5
x
6
x
7
紧前工序 - - -
x
1
x
2
x
2
x
3
x
4
x
1
x
3
x
5
α
收稿日期: 1996204210
© 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
剩余12页未读，继续阅读
评论0
最新资源