柔性制造系统中的无死锁调度

摘要

柔性制造在当今追求多品种小批量的生产中具有相当重要的地位。多年来，很多专家学者致力于关于柔性制造的理论和方法的研究。柔性制造系统中的调度问题和死锁问题一直是两个研究热点，他们是两个独立的NP-hard问题，由于计算复杂度的原因，始终没有彻底的解决方案。很多现有的研究成果都是对他们分别进行讨论，而事实上，在资源有限的柔性制造系统中，如果不考虑死锁问题，调度很可能是不可行的。因此，我们将死锁问题集成在调度问题中，提出了一种无死锁调度方案。 针对柔性制造系统有缓冲区和无缓冲区两种情况，我们分别提出了基于启发式规则的无死锁调度算法。该算法基于集束搜索方法，局部评价函数和全局评价函数。在没有缓冲区的制造系统中，常常会产生无死锁不安全状态，因此，当系统遇到死锁时将采用回溯步骤使系统恢复到以前状态。在有缓冲区的制造系统中，不存在无死锁不安全状态，所以只需采用单步前瞻的无死锁预防策略就可以保证系统运行于无死锁状态下，因此也不需要回溯步骤。因为两种方法都是基于启发式的规则，他们需要的计算时间很短，适合在线运行。总之，他们是折衷了计算时间的消耗和调度结果的质量的算法。