惠晓龙，郜振鑫

资源受限的项目调度问题(Resource Constrained Project Scheduling Problem，RCPSP)属于NP－hard 问题;广泛存在于制造系统等调度问题，它通过合理地分配资源，达到项目执行工期最短等优化目标［1］。在合理分配资源的过程中，死锁是一个重要的研究课题，目前人们从控制的角度提出了多种死锁避免控制策略，但是这些策略无法优化系统的运行性能，因此系统的无死锁优化调度是一个值得研究的问题［2－5］。传统的优化调度只有一个优化目标，而在实际项目中往往存在多个优化调度目标。

本文针对制造系统的赋时Petri 网模型，研究以总工期最短和紧急项目工期最短为优化目标的无死锁调度问题，建立系统的多目标无死锁蚁群调度算法。蚁群算法采用最大最小蚂蚁系统，通过修改状态转移概率公式，并给出算法最优解的评价函数，使蚂蚁综合多个优化目标选择路径。单只蚂蚁选择下一步可执行的操作时，进行死锁判断，将死锁避免控制策略嵌入到算法，实现无死锁调度。仿真结果验证了本文提出的多目标无死锁蚁群调度算法的可行性和有效性。

1 系统的Petri 网模型

Petri 网［2］结构是一个三元组N=(P，T，F)，其中P和T 都是有限但互不相交的集合。P 是位置(Place)的集合，T 是变迁(Transition)的集合，F⊆(P×T)∪(T×P)是有向弧(Arc)的集合。

Petri 网N 的一个标识或状态是一个映射M∶P→Z+，其中Z+={0，1，2，…}。给定标记Petri 网N=(P，T，F，M0)，用T*表示T 的所有变迁序列的集合，∀a=t0，t1，t2，…，tn∈T*，如果Miti＞Mi+1，i=0，1，2，…，n，则称a 为在M0下的可行序列，称Mi(i=1，2，…，n+1)为从M0的可达标识或状态。Petri 网N 中的一条路径是一个序列αuv=(u=x1，x2，…，xk+1=v)，其中xi∈P∪T，(xi，xi+1)∈F，i=1，…，k，k 是α 的长度。

本文采用位置赋时Petri 网模拟系统的特征，模型中一个标记必须在位置中经过一定时延，记作d(p)，才能进入下一个位置。……