作业调度系统中的A*智能搜索算法研究与实现(2)

菜单

智能作业调度是指使用一些好的数学模型，将生活、生产等方面遇到的问题进行抽象、模拟，然后运用人工智能领域的各种算法，以求找到一些好的解决问题的方法，使得所研究的问题能够又快又好的得到解决。网格作业调度、现代制造系统多以及机器人系统等都需要进行作业调度，各种智能作业调度系统由此得到了广泛的研究和应用。

自21世纪以来，作为国民经济基础产业的制造业随着计算机和自动化技术的飞速发展也正发生着巨大的变化。现代的制造业中大都采用了机床自动化生产技术，然而这种大型生产线的建立不仅投资大，而且在产品更换和生产工艺修改等方面都需要较大的时间和费用，浪费了很多额外的人力、物力。另外，传统的生产线生产方式不能及时调整生产计划和调度，难以满足迅速变化的市场各种各样的需求。为了实现系统的生产自动化和调度灵活化，柔性制造系统正是在这样的背景下应运而生。论文网

柔性制造系统（Flexible Manufacturing System，FMS）是这样一种自动化制造系统：它以成组技术为基础，以多台柔性制造单元为核心，由自动化物流技术连接起来，并统一由主计算机进行管理和控制，能够高效率的生产大批量的多种多样的零部件。柔性制造系统各个组成单元都拥有一定的柔性，即它们能够根据生产任务和生产调度的不同进行及时的调整，从而适应了现代制造业中不断变化的需求以及不同类型任务的生产流水线。

柔性制造系统（ＦＭＳ）的分析和实施需要相应模型的支持，目前来说，在FMS系统建模领域，越来越多的注意力开始放在通过在Petri 网理论的基础上建模、仿真，以模拟现实中的真实系统。Petri网是Carl A.Petri博士于1962年首次提出的概念。它能够很好的描述系统的同步和异步等过程关系，还可以形象地表示离散事件动态系统（DEDS）中各种事件及其之间的变化关系，主要应用领域有计算机技术（如操作系统、人工智能、网络协议等）、机械制造（如柔性制造系统FMS）、自动化技术（如离散事件动态系统DEDS）等。近些年来，Petri网已在Flexible Manufacturing System中得到了越来越广泛的应用。

通过Petri网的分析研究，我们不仅可以看清系统的结构，还可以准确描述系统的状态变化等行为性的特征。不仅可以用图形来表示Petri网，同时还可以借助一些数学领域的方法分析其特性。综上所述，Petri网适合用于柔性制造系统的建模和分析。Petri网是一种较为常用的DEDS建模工具，利用Petri网建立离散事件动态系统有如下的特点：

（1）能够很直观地表示出事件的动态变化过程；

（2）能够准确地描述离散事件动态系统中的共享、并发、同步等过程；

（3）便于通过构建的模型来实现对实际系统的控制；

（4）通过定性、定量的分析得知系统的各种关键性能；

（5）Petri网模型还可以驱动离散事件以对实际系统进行高度的仿真。

另外一个重要问题是，柔性制造系统在完成建模之后如何进行系统的调度。柔性制造系统中可能在同一时间存在多条流水线进行生产，有可能涉及到资源共享的情况。另外，一个产品的加工工序中也可能存在多条可选的路径，这些都对柔性制造系统的调度提出了挑战和要求：即如何分配共享的资源、如何在多条可选操作中选择等等都需要FMS系统调度来解决。而且，经过实践的证明，其调度问题大都为NP完全问题，不存在统一的最优解，即便是比较简单的Petri网模型，其涉及到的调度规模都可能是很大的。本文使用Petri网对ＦＭＳ进行建模，将A*算法应用于模型中，给出了基于Petri网的FMS的合理调度。