A Petri Net based algorithm for minimizing total tardiness in flexible manufacturing systems |
| |
Authors: | Gonzalo Mejía Carlos Montoya |
| |
Institution: | (1) Department of Industrial Engineering, Universidad de los Andes, PYLO Research Group, Bogotá, Colombia |
| |
Abstract: | Petri Nets have been extensively used for modeling and simulating of the dynamics of flexible manufacturing systems. Petri
Nets can capture features such as parallel machines, alternative routings, batch sizes, multiplicity of resources, to name
but a few. However, Petri Nets have not been very popular for scheduling in manufacturing due to the Petri Net “state explosion”
combined with the NP-hard nature of many of such problems. A promising approach for scheduling consists of generating only
portions of the Petri Net state space with heuristic search methods. Thus far, most of this scheduling work with Petri Nets
has been oriented to minimize makespan. The problem of minimizing total tardiness and other due date-related criteria has
received little attention. In this paper, we extend the Beam A* Search algorithm presented in a previous work with capability to handle the total tardiness criterion. Computational tests
were conducted on Petri Net models of both flexible job shop and flexible manufacturing systems. The results suggest that
the Petri Net approach is also valid to minimize due date related criteria in flexible systems. |
| |
Keywords: | Petri Nets Heuristic search Beam search Scheduling Flexible manufacturing systems |
本文献已被 SpringerLink 等数据库收录! |
|