Underlying concepts

Introduction

The software tools developed for the DCS project, StrEmbed and PartFind, rely on a range of underlying mathematical concepts and methods to allow the user to realise the assembly structure of products and to modify, manage and investigate the configuration of multiple BoMs for a product. Here we present an overview of the most important mathematical concepts that are referred to throughout this online resource, where all concepts are highlighted in bold.

Combination. A particular arrangement of distinct objects, the study of which is known as combinatorics, and which is distinct from a permutation in that the order of objects does not matter. Combinations arise in a range of scientific and real-world fields, for example, probability and statistics, graph theory, computer science and biology.

In the DCS project, combinatorics is used to support the representation of the assembly structure of products and, more specifically, (a) to calculate the number of all possible ways a product can be assembled as a BoM and (b) to encode a particular assembly structure in the context of all possible structures using a method called lexicographic ordering.

For example, to represent a product with N = 5 parts, we would label each part with the numbers 1 to 5, and the total number of possible combinations of those parts is 2^N = 32. Then, if a particular BoM for the product has two sub-assemblies containing parts 1, 2 and 5, and another containing parts 3 and 4, the combinatorial identities of those two sub-assemblies would be {1, 2, 5} and {3, 4}. Lexicographic ordering then allows us to identify that {1, 2, 5} is combination 3 out of 10 possible three-part sub-assemblies and {3, 4} is combination 8 out of 10 possible two-part sub-assemblies.

- References: combinations (Wikipedia), combinations (Mathworld), lexicographic ordering (Wikipedia)

Embedding. In mathematics, the concept of embedding consists of an instance of a mathematical structure being contained within another instance.

In StrEmbed, the proof-of-concept software developed for the DCS project, the process of adding a BoM to a lattice structure is an example of an embedding, since both BoMs and lattices are represented in the DCS software tool, StrEmbed, as directed, acyclic graphs. Multiple BoMs can be embedded within a lattice. StrEmbed can be used to transform, align and integrate BoMs, as shown in the scenarios here. Two test cases were used to verify StrEmbed's functionality: a five-piece puzzle and a ten-piece torch. After verifying StrEmbed's functionality, a railway carriage model (20+ parts) was used as a case study in order to demonstrate the underlying mathematical tools were applicable to more complex BoMs.

Below are six figures, each pair of which corresponds to a BoM for the five-piece puzzle test case used in this scenario: Integrating BoMs. The five components of the puzzle are A, B, C, D and E. Each BoM has a different assembly structure and can be represented as a lattice. All three lattices are shown embedded in the same underlying 2^5 Boolean lattice.

- References: embedding (Wikipedia)

Configuration 1 (puzzle 1b)

Configuration 2 (puzzle 1c)

Configuration 3 (puzzle 1d)

Graph. A set of nodes (or vertices) and edges (or arcs), where nodes represent distinct objects and edges represent connections or relationships between them. Graphs can be used to represent a wide range of real-world objects such as social networks and computer systems, or for solving logistics problems, for example.

In the DCS project, graphs are used in two distinct ways. In the engineering design part of the project, graphs are used to represent the BoM structure of products. Specifically, we use directed, acyclic graphs. "Directed" means that the edges, i.e. the connections between objects, are in one direction; this directedness is a representation of the parent-child relationship between the parts and sub-assemblies in a product BoM. "Acyclic" means that no cycles can exist within the BoM structure, and in practice this means items can have at most one parent; this is a representation of the fact that items can be included in at most one sub-assembly. In the context of lattices, directed edges represent cover (or covered-by) relationships, which are equivalent to parent-child relationships in a corresponding BoM.

In the machine learning part of the DCS project (see this page: Finding and classifying parts by shape), graphs are used to represent the topology of parts and sub-assemblies, with each graph node corresponding to a face in an item's shape model and each edge to an interface between two faces. In this case, the graphs used are attributed, directed and cyclic, where "attributed" refers to the fact that face-specific data can be stored at each node, and "cyclic" refers to the fact that there may exist two connections (edges) between faces, one in each direction.

- References: graphs (Wikipedia), graphs (Wolfram Mathworld), directed acyclic graphs (Wikipedia)

Lattice. A lattice is a mathematical structure that can be used to represent part-whole relationships. It is the set of all possible combinations of a particular set of objects and the parent-child relationships between them, and is a kind of partially ordered set (poset). Each object is considered discrete and indivisible.

A Boolean lattice is a specific kind of lattice that can be used to represent bills of materials (BoMs) to support various stages in a product's lifecycle. In the DCS project, the objects of interest are the invisible parts (components) of a BoM and any number of sub-assemblies of those parts, and the parent-child relationships are between sub-assemblies and parts (or other sub-assemblies). That is, a top-level BoM typically consists of a number of sub-assemblies and individual parts. Any such grouping of sub-assemblies and components, when assembled into a BoM, can be considered a particular combination of those components, and many possible combinations exist.

Since a BoM consists of indivisible parts (for the purpose of the stages of the product lifycycle concerned), it can therefore be represented by a lattice. With this lattice, a Boolean lattice can be generated. However, only some sub-lattices of this Boolean lattice are suitable for representing BoMs. For example, for a BoM with five components, the corresponding Boolean lattice has five atoms and the total number of valid sub-lattices of this Boolean lattice - which corresponds to the number of valid BoMs they represent - is 10.

In StrEmbed, the lattice for a project, which contains one or more BoMs, is the smallest possible graph containing all BoMs in a project, and each node and edge in the lattice contains a reference to at least one BoM. It is important to note that not all possible nodes and edges of the lattice are realised: only those represented by actual objects in the BoMs contained in the lattice are realised. All matches between BoMs - i.e. links between common items across BoMs - can be recovered immediately from the lattice.

In practice, the lattice for a particular project in StrEmbed is realised as a directed, acyclic graph, as is each BoM in a project. Whereas item-specific data (name, shape) is stored at each node of the graph representing a BoM, in the lattice the data at each node simply consists of references to the items within any BoMs that are represented by that node.

Strictly speaking, the lattice for a particular project is realised in StrEmbed as the smallest possible graph that contains subgraphs that are isomorphic to the graphs of each BoM that it refers to.

- References: posets (Wolfram Mathworld), graph isomorphisms (Wikipedia)

Underlying concepts

Introduction

Further reading