Symbolic Scheduling of Robotic Cellular Manufacturing Systems With Timed Petri Nets

Bo Huang, Meng Chu Zhou

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

To reduce the computational burden in the scheduling of robotic cellular manufacturing (RCM) systems based on Petri nets' (PNs) reachability graphs, existing methods mainly focus on the relaxation of a graph search algorithm at the cost of schedule optimality. Different from that, this article presents a method that accelerates the search process by using symbolic representations and manipulations. The proposed method uses binary decision diagrams (BDDs) to functionally represent and evolve discrete and place-timed PNs of RCM systems and then schedule them with a symbolic A* search to find an optimal solution with minimal makespan. It uses compact BDD structures to represent sets of states, instead of individual states, and then performs efficient Boolean manipulations to evolve the net and search for a system schedule. A heuristic function and its Boolean implementations for the symbolic A* search are developed. The admissibility of the proposed heuristic function is proven, which guarantees the optimality of the obtained schedule. The computational time is thus reduced without sacrificing the schedule optimality. Finally, experiments are carried out to show the effectiveness and efficiency of the presented method.

Original languageEnglish (US)
JournalIEEE Transactions on Control Systems Technology
DOIs
StateAccepted/In press - 2022

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Keywords

  • Binary decision diagrams (BDDs)
  • Cellular manufacturing
  • Costs
  • Job shop scheduling
  • Optimal scheduling
  • Petri nets
  • Schedules
  • Search problems
  • robotic cellular manufacturing systems
  • scheduling
  • timed Petri nets (PNs).

Fingerprint

Dive into the research topics of 'Symbolic Scheduling of Robotic Cellular Manufacturing Systems With Timed Petri Nets'. Together they form a unique fingerprint.

Cite this