Resource allocation in a flexible manufacturing system by graph matching

Resource allocation in a flexible manufacturing system (FMS), such as assignment of resources to tasks, can be solved efficiently using graph matching methods. The FMS is modeled as a graph: the vertices are resources and tasks, and the edges ar relationships between the resources and tasks. Resources are allocated by finding a match in the graph. The general matching problem is reviewed as an optimization problem; the more specific maximum cardinality 1-matching problem is discussed in detail. A direct parallelization of an algorithm is described which may be regarded as an archetype for implementation on a distributed network of computers in a large FMS. In such an FMS, planning activities such as resource allocation are decentralized, allowing for quicker and more detailed planning