基于时间Petri网的自动制造系统排产优化方法

王艺翔,洪 良,田海霖,王晓华

(西安工程大学 电子信息学院,陕西 西安 710048)

0 引 言

由于自动制造系统[1]中存在事件冲突性与并发性等特点,当前的算法和模型已无法满足自动制造系统的生产要求,因此,对排产的优化显得尤为重要.近年来对排产问题的研究,已经取得了许多成果.Johnson在20世纪五十年代提出解决车间调度部分特殊问题的优化算法[2],开启了对调度问题的研究；Roslof提出了一种基于整数线性规划的算法[3],但用该算法求解生产调度问题时,随着对象的增多和时间的推移会产生状态空间爆炸的问题；文献[4]将人工智能算法运用到排程问题之中,提高了生产效率,但不能保证收敛到最优解；文献[5-7]对遗传算法做了比较全面的总结,遗传算法可以对生产线上的个别工序进行优化,但局限于无法满足多任务生产的情况.Petri网[8-10]在处理离散事件系统问题不仅可以描述系统的静态行为,也可以描述系统的动态行为[11],简单准确地表示系统中的并发、资源共享、冲突、相互抑制以及非确定性等特征,图像界面直观清晰，这些特点都十分有利于自动制造系统的建模. 文献[12]应用Petri网理论解决了传统方法由于状态空间爆炸造成的寻优计算难题. 目前,Petri网理论已经在大规模车间生产调度问题[13-16]中得到广泛应用,文献[17-19]讨论了利用时间Petri网对系统的建模和分析,给出了自动制造系统生产过程的调度算法,但缺少对多条线路自动制造系统的分析和优化……