Modified Hamiltonian chain: A graph theoretic approach to group technology

Graph theory can be effectively applied to the group technology configuration problem (GTCP). Earlier attempts were made to use graph theoretic algorithms, e.g. minimal spanning tree (MST), tree search, and branch & bound to solve the group technology (GT) problem. The proposed algorithm is based on modified Hamiltonian chain (MHC) and consists of two stages. Stage I forms the graph from the machine part incidence matrix. Stage II generates a modified Hamiltonian chain which is a subgraph of the main graph developed in Stage I, and it gives machine sequence and part sequence directly. Dummy edges are considered in MHC for better accessibility in order to arrive at a block diagonal solution to the problem. This paper presents a simple approach by designing a MHC in the graph theoretic method to solve the group technology configuration problem. Results obtained from testing the method are compared with the other well-known methods and found to be satisfactory.