|
Título:
|
Deadlock-free scheduling method for flexible manufacturing systems based on timed colored Petri nets and Anytime Heuristic Search
|
|
Autor/a:
|
Baruwa, Olatunde; Piera, Miquel Angel; Guasch Petit, Antonio
|
|
Otros autores:
|
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ó |
|
Abstract:
|
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. |
|
Abstract:
|
Peer Reviewed |
|
Materia(s):
|
-À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 |
|
Derechos:
|
|
|
Tipo de documento:
|
Artículo - Versión presentada
Artículo |
|
Editor:
|
Institute of Electrical and Electronics Engineers (IEEE)
|
|
Compartir:
|
|
