To access the full text documents, please follow this link: http://hdl.handle.net/2117/28096

Deadlock-free scheduling method for flexible manufacturing systems based on timed colored Petri nets and Anytime Heuristic Search
Baruwa, Olatunde T.; Piera, Miquel Angel; Guasch Petit, Antonio
Universitat Politècnica de Catalunya. Departament d'Enginyeria de Sistemes, Automàtica i Informàtica Industrial; Universitat Politècnica de Catalunya. LIAM - Laboratori de Modelització i Anàlisi de la Informació
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.
Peer Reviewed
Àrees temàtiques de la UPC::Informàtica::Automàtica i control
Petri nets
Automatic control
Color
Robots
Anytime heuristic search
deadlock-free
flexible manufacturing systems (FMS)
Petri nets (PN)
reachability analysis
scheduling
STATE-SPACE EXPLORATION
SUPERVISORY CONTROL
PREVENTION POLICY
AVOIDANCE
VEHICLE
SIPHONS
CONTROLLERS
WORKCELLS
BLOCKING
CELLS
Petri, Xarxes de
Control automàtic
Color
Robots
info:eu-repo/semantics/submittedVersion
Article
Institute of Electrical and Electronics Engineers (IEEE)
         

Show full item record

Related documents

Other documents of the same author

Casany Guerrero, María José; Cabrera Beán, Margarita Asuncion; Bragós Bardia, Ramon; Pérez, Marimar; Sánchez Terrones, Benjamín; Guasch Petit, Antonio; Garófano, F.; Gomis Bellmunt, Oriol; Rius Casals, Juan Manuel
Guasch Petit, Antonio; Figueras Jové, Jaume; Casanovas Garcia, Josep
Fonseca Casas, Pau; Casanovas Garcia, Josep; Figueras Jové, Jaume; Guasch Petit, Antonio
Guasch Petit, Antonio; Luker, P
 

Coordination

 

Supporters