面向状态空间爆炸的自动制造系统智能化调度策略研究

The intelligent scheduling of automated manufacturing systems can effectively control the system state evolution and minimize the production cost and time. It also avoids poor production planning which often results in economic loss. On the other hand, state space explosion means the number of states in a system model often increases exponentially with the model size, which may cause that the explicit state presentation and the scheduling in such a state space can only be applied to small systems. To cope with the state space explosion problem in the automated manufacturing systems, this project will propose an implicit symbolic state presentation and its intelligent heuristic scheduling strategies, which is to provide an effective method to model and intelligent schedule reasonably sized and dynamically changing automated manufacturing systems. It will study how to apply the ordered binary decision diagraph (BDD) technique to the timed generalized Petri net models and define the Boolean characteristic functions of the state sets in the models with time and resource constraints. It will also research the optimal match of the variable order and the BDD structure based on relations between different operations. Furthermore, it will propose the symbolic representation mechanism of the heuristic functions based on state attributes and research the following key scheduling techniques: parallel heuristic A* search, incremental A* search with local variation, search guiding, state space pruning, etc. The project tries to investigate the strategies of implicit state representation and intelligent scheduling optimization of dynamic automated manufacturing systems with variant products. The goal of the project is to present a system scheduling optimization strategy and its technical implementation which can be applied widely and meet the needs of real production systems.

自动制造系统的智能调度可有效控制系统的状态演化、优化生产周期和制造成本，并避免因规划不妥而造成的经济损失。状态空间爆炸是指系统可达状态数随系统规模呈指数增长，导致显示状态表示及其上的调度方法只能用于小型系统。课题围绕自动制造系统的状态空间爆炸问题，深入研究系统的隐式状态表示及其智能启发式调度策略，以实现具有一定规模、动态变化自动制造系统的符号化建模与智能调度控制。研究有序BDD技术应用于系统赋时一般Petri网的机制，构建时间和资源约束下模型状态集的布尔特征函数表示，建立基于操作相关度的变量顺序与BDD结构的优化匹配；研究基于状态属性的符号化启发函数，结合并行启发式A*搜索、局部变动下增量A*搜索、搜索导向和状态空间剪枝等关键技术，对变品种、动态连续生产自动制造系统的隐式状态表示和智能调度技术进行科学研讨，力求给出应用范围广、通用性较强、符合实际生产需要的系统状态建模与调度优化的技术实现。

自动制造系统的自动化、智能化水平代表了一个国家制造业的发达程度。目前自动制造系统建模分析与调度控制中的状态空间爆炸问题越来越突出，即系统可达状态数量随系统规模的增加呈指数增长，导致传统模型的显示状态表示及其最优调度方法只能应用于规模较小的系统，因此如何缓解状态空间爆炸问题，使得相关建模分析与最优调度优化方法可以应用于更复杂的实际系统具有重要意义。通过本项目的研究，我们建立了自动制造系统普通赋时Petri网模型的有序二元决策图压缩表示规则，构建了含时间模型状态演化的布尔特征函数，实现了赋时系统模型的符号化隐式建模与快速调度优化，使得原本常规显式方法无法最优调度控制的一些自动制造系统变得可以调度与分析；提出了可适用于含有托肯剩余时间、弧权值大于一与多资源拷贝系统模型A*调度的可采纳启发函数，加快调度路径搜索速度的同时并保证结果的最优性；针对系统的死锁监督器合成，提出了一种整数线性规划迭代方法，构建了多个相对小得多且可更快执行的监督器合成方法，并给出了一种高效的冗余约束去除策略；在此基础上，还提出了在库所不变量设计过程中减少关联库所数量的方法，进一步提高了控制器的求解速度；搭建和实现了赋时Petri网模型隐式状态表示与智能调度平台。基于课题的资助，出版了英文学术专著1部，发表相关学术论文10篇，其中IEEE汇刊IEEE T-SMC，IEEE T-CST，IEEE T-ASE和IEEE/CAA JAS论文5篇，培养博士研究生2人，硕士研究生10人，申请或授权国家发明专利11项，并与北方信息控制研究院和南京莱斯科技开展了合作研究，将相关成果应用到多机器人协作系统与智能交通系统的调度与规划中。超额完成了计划书规定的内容，研究成果达到了预期目标。