基于时间Petri网和启发式搜索的柔性制造系统调度算法

利用库所延迟Petri网对柔性制造系统进行建模,在Petri网激发变迁生成的可达树中进行启发式搜索,求解最小完成时间调度策略,并改进了现有计算机器剩余时间的启发式函数,对剩余加工操作进行准确分类,以保证算法的最优性.为了提高算法的求解效率,改进后的启发式函数考虑了未产成操作的剩余时间,以使预测值更加准确并减少了计算量.同时,利用实验验证了所提出方法的正确性和有效性.

Scheduling Flexible Manufacturing System Based on Timed Petri Net and Heuristic Search

Abstract： The place-timed Petri net was used to model the flexible manufacturing system scheduling problems. Combined with the execution capacity and heuristic search, Petri net can achieve the minimum makespan strategy by expanding the partial reachability tree. The heuristic function for calculating the machine remaining operation time was improved. First, remaining operations for general FMS were classified into two categories to guarantee the optimality. Besides, the remaining time of on processing operations was also considered, which improved the lower bound for heuristic function. As a result, the optimal scheduling strategy could be achieved in less effort. Experiment results demonstrate the proposed heuristic function performs better as expected.