(A) study on the machine grouping problem using K-way decomposition of weighted networks

Abstract

In this thesis, machine grouping problem is discussed. Actual grouping problem was modeled as an optimal k-way decompotion of weighted bipartite networks due to Kumar et al. However, actual manufacturing situations cannot be precisely represented by weighted bipartite networks. This study proposes a new network representation to reflect actual manufacturing situations such as manufacturing sequence and machining (or operation) characteristics and formulates the problem as a 0-1 quadratic program with linear constraints. We convert the program into linear one, and then show that optimal solution can be obtained by integer linear programming techniques. Lastly, an efficient heuristic procedure is developed which utilizes basically Kernighan-Lin two-way uniform partitioning algorithm. Two experiment results are presented to show that the heuristic solution procedure is efficient and requires a little computer time.