A timed state space-heuristic search framework for colored petri net-based scheduling of discrete event systems —an application to flexible manufacturing systems

Resumen

Para obtener una ventaja competitiva en el mercado global, los fabricantes tienen que adaptarse rápidamente sus sistemas para responder a las fluctuantes demandas de los clientes en virtud de factores de servicio de alta calidad. La alta inversión de capital en los sistemas de fabricación flexible (SFFs), junto con los desafíos de las condiciones de mercado que cambian rápidamente se ha convertido en esencial la utilización eficiente de los recursos. Para maximizar los beneficios de un SFF, se necesita una implantación de técnicas de programación e planificación adecuadas para aprovechar plenamente las flexibilidades de fabricación. El objetivo global de esta tesis es establecer un marco de programación basado en el modelado de redes de Petri coloreadas temporales (RdPCT) para optimizar el rendimiento de los SFF mediante el desarrollo de herramientas y métodos de búsqueda eficientes basados en el análisis del espacio de estados (EdE). El análisis del espacio del estado es una herramienta potente que se puede utilizar para automatizar la actividad de toma de decisiones en problemas de programación mediante el seguimiento de todos los posibles comportamientos del sistema modelado. Sin embargo, adolece del problema de explosión de espacio de estado debido a la complejidad computacional de los problemas de programación de la producción en SFFs. Lo que ha limitado su aplicabilidad a problemas de tamaño pequeño. En la metodología de la programación propuesta, la generación de un plan de producción óptimo consiste en la construcción y el recorrido del espacio de estados con un algoritmo de búsqueda. Además, se requiere un simulador para la ejecución del modelo de RdPCT. Es muy natural utilizar el gráfico algoritmos de búsqueda ya que el método de análisis subyacente se basa en el EdE. La estrategia de búsqueda gráfica es una técnica interdisciplinaria que atraviesa los campos de la inteligencia artificial (IA), la investigación operativa (OR), e Informática. Esta tesis se centra en los métodos de búsqueda heurística basados en IA que se utilizan para simular solamente los mejores escenarios (como un problema de búsqueda del camino más corto). En este método, la exploración de los EdE son guiados con funciones heurísticas que se basan en el conocimiento de los planes de producción. La contribución de esta tesis es cuádruple. La primera ofrece la plataforma en que se implementan las otras tres contribuciones: una herramienta para soporte de decisión automatizada y de uso especial llamado TIMed State space Performance Analysis Tool (TIMSPAT). En segundo lugar, se desarrolló un enfoque de memoria eficiente para aliviar el problema de escalabilidad que aparece en la exploración de EdE de problemas de programación FMS. En tercer lugar, se presenta dos algoritmos de búsqueda heurística a cualquier hora, desarrollados para superar las desventajas de los algoritmos de búsqueda heurística convencionales. Finalmente, la última contribución presenta un enfoque basado en RdPCT a la programación simultánea de máquinas y vehículos guiados automáticamente (AGV) con enrutamiento libre de conflictos.