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

Autor/a

Baruwa, Olatunde Temitope

Director/a

Piera, Miquel Àngel

Fecha de defensa

2015-07-27

ISBN

9788449054327

Depósito Legal

B-25283-2015

Páginas

140 p.



Departamento/Instituto

Universitat Autònoma de Barcelona. Departament de Telecomunicació i Enginyeria de Sistemes

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.


To gain competitive advantage in the global market, manufacturers have to quickly adapt their systems to respond to fluctuating customer demands under high-quality service factors. The high capital investment in flexible manufacturing systems (FMSs) together with the challenges of the rapidly changing market conditions has made efficient resource utilization become essential. To maximize the benefits of an FMS, appropriate scheduling techniques must be put in place to fully exploit the manufacturing flexibilities. The overall objective of this thesis is to establish a scheduling framework based on timed colored Petri net (TCPN) modeling for optimizing the performance of FMSs through the development of tools and efficient search methods based on the reachability graph (or state space) analysis. In the proposed TCPN-based scheduling methodology, the generation of an optimal production schedule involves the construction and traversal of the state space with a search algorithm. Also, a simulator is required for executing the TCPN model. It is quite natural to use graph search algorithms since the underlying analysis method relies on the reachability graph. Graph search strategy is an interdisciplinary technique that spans across the fields of Artificial intelligence (AI), Operations research (OR), and Computer science. This thesis focuses on AI-based heuristic search methods used in simulating only the best scenarios (as a shortest-path search problem). In this method, the exploration of reachability graphs are guided with heuristic functions that rely on the knowledge of the production plans. The contribution of this thesis is fourfold. The first provides the platform called TIMSPAT in which the other three contributions are implemented. Because of the complex data structure, TCPN-based scheduling using reachability graph analysis has been merely looked at in the literature. Thanks to the common data structure of the heuristic search methods, TIMSPAT is capable of incorporating different search algorithms in a single executable tool. So far, nine algorithms have been implemented, which includes the search algorithms proposed in this thesis and those by other authors. Second, a memory-efficient approach is developed to alleviate the scalability problem that appears in the state space exploration of FMS scheduling problems. The approach tackles the research questions: Is it necessary to store all the generated states to guarantee an optimal solution without revisiting states? and how can one reduce the number of states to be stored so that larger problems can be solved without forgoing optimality? It assumes that the state space graphs of a system with increasing problem size may contain repetitive patterns while the underlying model structure remains as constant as possible. The proposed solution is based on the notion that the structural behavior captured in the state space of a solvable smaller problem size can be extended to explore a larger size if the two problems share a certain kind of similarity. The third contribution presents two anytime heuristic search algorithms developed to overcome the drawbacks of conventional heuristic search algorithms. The first anytime algorithm adapts and improves an existing anytime algorithm to TCPN-based scheduling, while the second proposes a new algorithm that combines two heuristic search algorithms making them anytime for deadlock-free scheduling. The algorithms are suitable for both off-line and on-line scheduling purposes due to their effectiveness in adapting to different CPU constraints. The last contribution presents a TCPN-based approach to the simultaneous scheduling of machines and automated guided vehicles (AGVs) with conflict-free routing. Unlike the existing approaches that employ a decomposition framework, the entire scheduling problem is described in a single model. Two simultaneous scheduling models are proposed and evaluated using an event-driven vehicle assignment solution as opposed to the traditional dispatching rules.

Palabras clave

Colored petri net; Xarxa de petri acolorides; Redes de petri coloreadas; Flexible manufacturing systems; Sistemes de fabricació flexibles; Sistemas de fabricación flexibles

Materias

004 - Informática

Área de conocimiento

Tecnologies

Documentos

otb1de1.pdf

1.743Mb

 

Derechos

L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-nd/3.0/es/
L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-nd/3.0/es/

Este ítem aparece en la(s) siguiente(s) colección(ones)