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

Jian Chao Luo; Meng Chu Zhou; Jun Qiang Wang

doi:10.1109/TASE.2020.3029737

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

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-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 language	English (US)
Journal	IEEE Transactions on Automation Science and Engineering
DOIs	https://doi.org/10.1109/TASE.2020.3029737
State	Accepted/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

Access to Document

10.1109/TASE.2020.3029737

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

@article{c3083e8fa6f042f8bf438fa72d142e03,

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

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.",

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",

author = "Luo, {Jian Chao} and Zhou, {Meng Chu} and Wang, {Jun Qiang}",

year = "2020",

doi = "10.1109/TASE.2020.3029737",

language = "English (US)",

journal = "IEEE Transactions on Automation Science and Engineering",

issn = "1545-5955",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - JOUR

T1 - AB&B

T2 - An Anytime Branch and Bound Algorithm for Scheduling of Deadlock-Prone Flexible Manufacturing Systems

AU - Luo, Jian Chao

AU - Zhou, Meng Chu

AU - Wang, Jun Qiang

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

KW - Anytime branch and bound (AB&B) algorithm

KW - discrete event systems

KW - flexible manufacturing system (FMS)

KW - Frequency modulation

KW - Job shop scheduling

KW - machine learning

KW - Manufacturing systems

KW - optimization

KW - Petri net (PN)

KW - Production

KW - Schedules

KW - Scheduling algorithms

KW - scheduling.

KW - System recovery

UR - http://www.scopus.com/inward/record.url?scp=85098798842&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85098798842&partnerID=8YFLogxK

U2 - 10.1109/TASE.2020.3029737

DO - 10.1109/TASE.2020.3029737

M3 - Article

AN - SCOPUS:85098798842

JO - IEEE Transactions on Automation Science and Engineering

JF - IEEE Transactions on Automation Science and Engineering

SN - 1545-5955