Size Constrained K-Means Clustering for Controlled Design Structure Matrix Partitioning

In this paper, we propose a novel clustering algorithm for Design Structure Matrices (DSMs) with the goal of providing a balanced system partitioning. DSMs are one of the standard forms of modeling the dependency structure between system components. They naturally reveal the complexity of the system and often provide insights for organizational management. In particular, partitioning a DSM into multiple clusters is widely studied in the literature, as the cluster structure either gives rise to a natural work breakdown structure for the organization or highlights hidden dependencies between clusters. Often, such clustering methods work directly on DSMs by permuting rows and columns randomly, making scalability an issue due to the exponentially growing search space with respect to DSM size. In this paper, we propose an alternative approach to clustering a DSM in its spectral space using the k-means algorithm. The spectral space of a DSM is the low-dimensional eigenvector space of the Laplacian of the given matrix, which is invariant to the row-column permutation of the original DSM. Furthermore, we introduce an Integer Linear Programming (ILP) method to constrain the size of each cluster to balance the resulting partitions, which is often not achievable using the generic kmeans algorithm. The DSM from a medium-sized jet engine is used to demonstrate the method's balancing properties. Then synthetic DSMs are used to show the method's scalability which is compared to the generic simulated annealing clustering algorithm.