为了生存和发展,越来越多的现代化企业把柔性制造系统作为提高他们竞争能力的有效手段。然而在这种自动化制造系统中资源高度共享,当工件进入系统并竞争有限资源时,如果缺乏有效的调度和控制方法,就会发生死锁现象。死锁现象给自动制造系统的生产能力带来巨大的损失,对死锁的有效处理是获得高生产率的必要条件。由此,制造系统中的死锁问题受到学术界和工业界的广泛关注。本文针对制造系统中的死锁问题,从制造系统的调度和控制着手,运用利用Petri网或图论模型对不同类型的自动制造系统进行建模,并在此基础上提出了多种无死锁调度算法和死锁避免方法。1.提出了一种基于Petri网和遗传算法的无死锁调度算法,并把该算法用于无缓冲区的单资源分配系统(即无缓冲Jobshop问题)和多资源分配系统。该算法对Petri网中的变迁序列进行编码,并在染色体解码过程中引入了不可行解的修复过程,利用高效死锁检测算法,调整染色体中变迁的触发序列,从而使得更多的变迁可以得到顺利触发,改善种群中染色体的质量,提高搜索效率。对调整基因序列后仍然不可行的解,通过增加惩罚项降低其适应度,以避免调度算法收敛于不可行解。利用文中提出的方法可以得到一个无死锁的加工次序,且能够保证系统获得最优或近优的性能指标。2.利用有向图论方法对考虑中央缓冲区的制造系统以及具有特殊缓冲结构的轨道导引小车搬运系统建立了有向图模型,并在此基础上提出了基于图论和遗传算法的无死锁调度方法。对于考虑中央缓冲区的制造系统,所提出的算法在染色体的解码过程中嵌入了一种基于图论的死锁检测算法来调整工件对资源请求序列以使更多事件可以发生。由于考虑缓冲区时的系统结构的特殊性,利用死锁检测算法对染色体中的基因序列进行调整后,可以保证得到的解总是可行解。本文提出的无死锁调度算法可以解决制造系统中含有在不同数量的中央缓冲区时的无死锁调度问题,从而为缓冲区容量的设计提供了依据。对于一类轨道导引小车具有双输入双输出特殊结构缓冲区的物料传输系统,本章中给出了综合考虑系统死锁和调度问题的优化算法。利用有向图模型对该系统提出了有效死锁避免规则,并在此基础上给出了基于遗传算法的无死锁调度方法,以使轨道导引小车在最短的行程内完成工件输送任务。3.提出了两种改进银行家算法用以避免自动制造系统中的避免现象。第一种方法运用有向图模型对单资源请求的自动制造系统进行建模,在此基础上对每一个子图按照一定的次序分别应用局部银行家算法。这种方法比传统的集中式银行家算法需要更少的在线计算时间,却能保证相同的柔性。针对有向图难以描述的具有柔性路由和多资源请求的制造系统,文中提出了第二种基于Petri网模型的改进银行家算法。该死锁避免策略采用了两种途径以减少安全性检查的计算量。首先在活动加工路径中引入了可退出库所。其次,在银行家算法的每一次迭代过程中,只在最短距离活动进程集合中而不是所有的进程中,寻找可退出的进程,这样可以减少无意义的搜索过程。4.从有向图模型的结构特点出发,提出了新的用于柔性制造系统的分布式死锁避免策略,它是对原有算法的一种改进。首先对整个制造系统建立有向图模型,并对该模型进行分解成多个子系统,然后对每个独立子系统加入相应的局部死锁避免策略以控制死锁的发生,这样使得整个系统的死锁避免更加简洁方便。文章中给出了死锁避免策略的柔性以及计算复杂度,结论表明本文提出的方法比原有的死锁避免算法能使系统运行在更大的容许状态空间中,即在避免死锁的同时,能使更多的工件在系统中同时进行加工操作,从而提高机器设备的利用率。5.对带有不可控和不可观变迁Petri网模型,提出了一种基于禁止弧Petri网及区域理论的控制器综合方法,以解决系统中的死锁问题。该方法根据Petri网的可达图,计算得到最大容许的活性状态空间和所需要禁止的状态转化集合。为禁止系统进入危险区域(死锁状态或者潜在死锁状态),并保持活性空间的最大可达性,在Petri网中增加控制库所及和其相连接的禁止弧。