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