A deadlock-free scheduling algorithm of robotic flexible job shops based on temporal Petri nets
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 deadlock-free 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 real-time scheduling problems.
job shop schedulingdiscrete bee colony algorithmsingle robotPetri netsblocking and deadlock
NETL
NSTL
万方数据
