第 38 卷 第 1 期
厦门大学学报
(
自然科学版
)
Vol
. 38
No
. 1
1999 年 1 月
Journal of Xiam en U niversity
(
N atural Science
)
Jan
. 1999
Johnson
算法的极大极小代数证明
①
彭 洪 张阿卜
(
厦门大学自动化系 厦门 361005
)
摘要
通过极大极小代数的方法对串行生产线进行建模, 并给出了
Johnson
算法的严格证
明.
关键词 离散事件动态系统,
Johnson
算法, 极大极小代数
中国图书分类号
TP
11
离散事件动态系统
(
D iscrete Event D ynam ic System
, 简称
DED S
)
是一种特殊的、复杂的
系统, 比如生产加工系统. 主要特点表现在: 1
)
离散性; 2
)
异步并发性; 3
)
随机性; 4
)
动态性. 它
的进程是由发生在离散时刻的事件所驱动的, 并且事件之间存在着复杂的相互作用关系, 因而
这种系统运行规律, 很难用通常的微分方程和差分方程来准确描述. 法国学者
Cohen
将极大
极小代数方法应用于对离散事件系统的研究, 这对于对系统特性的研究和对系统运行规律的
准确描述, 是十分有意义的, 将为该系统的分析、设计优化提供重要的依据和基础.
在调度问题中, Johnson 算法成功地解决了 Flow Shop 问题中的 nm F Fm ax
(
m = 2
)
问题, 而 nm F Fm ax
(
m > 2
)
就是一个N P 难题, 因此Johnson 算法在事实上提供了一个解
决诸如nm F Fm ax, 乃至 nm GFm ax 等 F low Shop 或 Job Shop 问题的辅助方案. 本文应
用极大代数的方法证明了 Johnson 算法的正确性, 同时也为对更复杂的问题研究采用极大代
数方法起到抛砖引玉的作用.
1 极大代数上串行生产线的模型
首先, 我们简单地介绍一下极大代数.
令 R 表示实数域, R
ϖ
= R ∪ { - ∞ }, 在 R
ϖ
上定义加法“g ”和乘法“⊙”, 令
a⊙b = a + b Π a, b ∈ R
ϖ
a g b = m ax
(
a
, b
)
Π a, b ∈ R
ϖ
其中“m ax”,“+ ”表示通常意义下的取极大和加法,“⊙”可省略或表示为“”.
不难证明, 运算“g ”,“⊙”满足结合律, 交换律和分配律. 令 e = 0, Ε= - ∞, 则对 Π a, b
∈ R
ϖ
有: e⊙a = a, Εg a = a, a⊙Ε= Ε, 因此, e, Ε可看作是单位元素“1”和零元素“0”.
在 R
ϖ
上规定了如上的运算“g ”,“⊙”后, R
ϖ
称为一个极大代数.
类似可以定义 R
ϖ
上的向量, 矩阵以及向量的数乘和加法, 以及矩阵的乘法.
①
本文 1998201215 收到; 福建省自然科学基金资助项目