基于时序Petri网的机器人柔性作业车间无死锁调度优化算法

A deadlock-free scheduling algorithm of robotic flexible job shops based on temporal Petri nets

研究了一类源于芯片生产等智能制造领域的机器人柔性作业车间调度问题。针对该类问题在算法设计过程中,需要同时考虑工件加工、机器人运输和死锁求解等带来的问题,提出了一种基于时序Petri网的无死锁调度优化算法。首先,对问题进行时序Petri网建模,提出了一种基于Petri网变迁串的解表示形式,以方便死锁求解和算法寻优;其次,通过对问题死锁的结构分析和分类,提出了一种死锁判断和求解算法,并证明了算法可在多项式时间内求解任意类型死锁,同时也能在一定程度上保证解的优良结构;最后,提出了问题的一种离散蜂群算法求解方案,在算法寻优过程中进行实时死锁求解以保证解的可行性和较快的收敛速度。不同规模实例的数值实验和与问题最优解及最优解下界的比较分析表明,提出的算法对不同类型实例都体现了较好的性能和较低的时间复杂度。该研究为复杂作业车间实时调度问题的算法研究提供了新思路和方法。

A robotic flexible job shop scheduling problem originating from intelligent manufacturing fields such as chip manufacturing was studied.To solve this problem,it is necessary to consider the difficulties caused by job processing,robot transportation and deadlock solving.As a result,a deadlockfree scheduling optimization algorithm based on temporal Petri net was proposed.Firstly,the problem was modeled by temporal Petri net,and a solution representation based on Petri net transition string was proposed to facilitate deadlock solving and algorithm optimization.Secondly,through the analysis and classification of the deadlock structure,a deadlock detection and resolution algorithm was proposed,and it was proved that the algorithm could solve any type of deadlock in polynomial time,and at the same time could ensure the good structure of the solution to a certain extent.Finally,a discrete swarm algorithm was proposed to solve the problem.In the optimization process of the algorithm,deadlock was solved to ensure the feasibility of the solution and fast convergence speed.The numerical experiments of different scale instances and the comparison with the optimal solution and the lower bound of the optimal solution showed that the proposed algorithm had good performance and lower time complexity for different types of instances.The study provides a new idea and method for the algorithm research of complex job shop realtime scheduling problems.