Deadlock-free scheduling method for flexible manufacturing systems based on timed colored petri nets and anytime heuristic search

Olatunde T. Baruwa, Miquel Angel Piera, Antoni Guasch

Research output: Contribution to journalArticleResearchpeer-review

48 Citations (Scopus)

Abstract

© 2013 IEEE. This paper addresses the deadlock (DL)-free scheduling problem of flexible manufacturing systems (FMS) characterized by resource sharing, limited buffer capacity, routing flexibility, and the availability of material handling systems. The FMS scheduling problem is formulated using timed colored Petri net (TCPN) modeling where each operation has a certain number of preconditions, an estimated duration, and a set of postconditions. Based on the reachability analysis of TCPN modeling, we propose a new anytime heuristic search algorithm which finds optimal or near-optimal DL-free schedules with respect to makespan as the performance criterion. The methodology tackles the time-constrained problem of very demanding systems (high diversity production and make-to-order) in which computational time is a critical factor to produce optimal schedules that are DL-free. In such a rapidly changing environment and under tight customer due-dates, producing optimal schedules becomes intractable given the time limitations and the NP-hard nature of scheduling problems. The proposed anytime search algorithm combines breadth-first iterative deepening A∗ with suboptimal breadth-first heuristic search and backtracking. It guarantees that the search produces the best solution obtained so far within the allotted computation time and provides better solutions when given more time. The effectiveness of the approach is evaluated on a comprehensive benchmark set of DL-prone FMS examples and the computational results show the superiority of the proposed approach over the previous works.
Original languageEnglish
Article number6994297
Pages (from-to)831-846
JournalIEEE Transactions on Systems, Man, and Cybernetics: Systems
Volume45
Issue number5
DOIs
Publication statusPublished - 1 May 2015

Keywords

  • Anytime heuristic search
  • deadlock-free
  • flexible manufacturing systems (FMS)
  • Petri nets (PN)
  • reachability analysis
  • scheduling

Fingerprint Dive into the research topics of 'Deadlock-free scheduling method for flexible manufacturing systems based on timed colored petri nets and anytime heuristic search'. Together they form a unique fingerprint.

Cite this