The University of Maryland

Institute for Systems Research

CIM LAB

Planning and Scheduling of Manufacturing Systems: An Approach Based on t-invariants of Petri Nets

Project Overview

This project is devoted to the behavior, evaluation, and management of non-cyclic discrete manufacturing systems. We introduce a special class of Petri nets called CFIOs (Conflict Free nets with Input and Output transitions). It has been shown that these properties guarantee that the underlying manufacturing system is manageable, and we develop a method that takes advantage of the qualitative properties of CFIOs to perform planning and scheduling in manufacturing systems. The approach utilizes reduction rules developed to facilitate the computation of the CFIO invariants.

Ongoing Research

The generation of shop floor schedules has not received much attention in the Petri net community. Furthermore, problems arise in integrating research done with Petri nets in different areas of manufacturing systems analysis. A comprehensive analysis requires specification, functional modeling, preservation of qualitative properties, planning, and scheduling. Research conducted in these areas has not necessarily used the same platforms. Underlying models include color Petri nets, simple Petri nets, and event graphs. This undermines the strongest aspect of Petri nets: their usefulness at each step in the analysis of a real system.

In an effort to overcome this drawback we use for scheduling the models introduced for the modeling and planning steps. On these models we develop a critical path-based scheduling algorithm. Thus there is a continuation of analysis as we create schedules using nets that preserve desirable qualitative propertie, are sutiable for modeling manufacturing systems, and provide results for the planning problem.

Contributions

• Introduction of a special class of conflict-free Petri nets which enables the modeling and analysis of non-cyclic discrete system
• Theoretical results related to the properties of CFIO nets
• Reduction rules for the simplified computation of CFIO t-invariants
• Decomposition of a complex system model into a set of simple CFIOs and the use of these CFIOs for the overall system management
• Application of the above methodology to perform production planning in manufacturing system

Finally, the most important contribution of this methodology is the development of a tool for both behavior evaluation and management of non-cyclic discrete systems. If the system is managed using this tool, the qualitative aspects of behavior can be ignored during the computation of control because these aspects are built into the model. Furthermore, the tool provides an approach to achieve an appropriate compromise (or balance) between the flexibility of the system and the computational burden during management.