AB&B: An Anytime Branch and Bound Algorithm for Scheduling of Deadlock-Prone Flexible Manufacturing Systems

Jian Chao Luo, Meng Chu Zhou, Jun Qiang Wang

Research output: Contribution to journalArticlepeer-review

Abstract

This work investigates a scheduling problem of deadlock-prone flexible manufacturing systems modeled by place-timed Petri nets. It proposes an anytime branch and bound (AB&B) algorithm for it to minimize system makespan based on the branch tree of a net model and a highly permissive deadlock controller. The proposed algorithm searches a sequence of transitions in the branch tree that evolves the model from the initial marking to the final one. In order to prune the branch tree and increase search speed, this work develops two pruning rules, a lower bound of makespan, and a novel branching strategy. Their usage ensures AB&B's high search efficiency. Experimental results demonstrate that the proposed algorithm surpasses the state-of-the-art ones.

Original languageEnglish (US)
JournalIEEE Transactions on Automation Science and Engineering
DOIs
StateAccepted/In press - 2020

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Keywords

  • Anytime branch and bound (AB&B) algorithm
  • discrete event systems
  • flexible manufacturing system (FMS)
  • Frequency modulation
  • Job shop scheduling
  • machine learning
  • Manufacturing systems
  • optimization
  • Petri net (PN)
  • Production
  • Schedules
  • Scheduling algorithms
  • scheduling.
  • System recovery

Fingerprint

Dive into the research topics of 'AB&B: An Anytime Branch and Bound Algorithm for Scheduling of Deadlock-Prone Flexible Manufacturing Systems'. Together they form a unique fingerprint.

Cite this