基于时间Petri网和启发式搜索的FMS调度方法

TIMED PETRI NETS AND HEURISTIC SEARCH-BASED FMS SCHEDULING

本文利用时间Petri网对FMS调度问题进行建模,满足约束条件的Petri网模型将调度问题限制在可行调度区域内.利用能够发现最优解的启发式调度算法,可将可行调度空间进一步减少.这种集成Petri网模型和启发式搜索技术的调度方法能有效地解决调度问题的结构复杂性和计算复杂性。

In this paper, FMS scheduling problems are modeled by the timed petri nets. The timed petri nets can model some inportant characteristics of FMSs. So the Petri net model of an FMS scheduling problem which reflects the given constraints would limit the search within the feasible schedules space. By making use of a heuristic scheduling algorithm which meets the lower bound condition of the algorithm A*, the search space can be further reduced and an optimal path can be found. This new scheduling approach which combines Petri net modeling with heuristic search can effectively handle with the structural complexity and computational complexity of FMS scheduling problems.