Heuristic Scheduling for Robotic Job Shops Using Petri Nets and Artificial Potential Fields

摘要

Numerous mobile robots are employed for material transporting in today’s manufacturing industry. Therefore, it is crucial to consider the time consumption of both process operations and transportation to minimize the makespan. This paper addresses the joint scheduling optimization problem of automated guided vehicle (AGV) routing and task allocation for robotic job shops (RJSs). A novel artificial potential field (APF) design method is developed based on place-timed Petri nets (PNs) for heuristic scheduling in RJSs. First, a real-life scale RJS is modeled with a place-timed PN, which contains a route subnet and several task ones. The scheduling problem is then transformed into a search one for the transition firing sequence with the minimum makespan, which can be obtained by the A* algorithm. Second, a task-APF design method is proposed for sorting processes. It defines potential energy parameters for places in task subnets by utilizing the topological structure of PNs. The heuristic function <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$h_{\mathrm {MPD}}$ </tex-math></inline-formula> is obtained, and it is proved to be admissible. Experimental results show that the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$h_{\mathrm {MPD}}$ </tex-math></inline-formula> heuristic enables the A* algorithm to generate an optimal schedule for RJSs, and its search efficiency surpasses that of the most advanced admissible heuristic functions available, particularly in the scenario described in this paper. However, its search efficiency decreases significantly when the number of jobs and AGVs increases. Third, a route-APF design method is proposed for AGV routing, and a novel heuristic function, denoted by <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$h_{\mathrm {TPD}}$ </tex-math></inline-formula>, is developed based on the task-APF and route-APF. Experimental results demonstrate that <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$h_{\mathrm {TPD}}$ </tex-math></inline-formula> is more adaptable for scheduling RJSs with large-scale jobs and multiple AGVs than <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$h_{\mathrm {MPD}}$ </tex-math></inline-formula>, which improves the search efficiency by an average of one order of magnitude. It can find an optimal or near-optimal schedule within a reasonable amount of time, even when dealing with hundreds of jobs and multiple AGVs. Note to Practitioners—Scheduling manufacturing systems is typically an essential and complex combinatorial optimization problem, known as NP-hard, involving AGV routing and processing sorting. To address these challenges, we propose a heuristic scheduling method with two heuristic functions, which are constructed by a novel artificial potential field design method based on place-timed Petri nets. This approach can produce a high-quality schedule within a reasonable time frame and demonstrates superiority in scheduling, especially for large-scale jobs in robotic job shops. Therefore, it can be applied to real-life scheduling problems of manufacturing systems.