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.
본 논문에서는 machine grouping 문제에 대해 다룬다. machine grouping 문제는 이미 Kumar 등에 의해 weighted bipartite network 의 k-way 분할로 모형화되었다. 그러나, 실제의 제조 상황은 weighted bipartite network 으로는 정확히 표시될 수 없다. 이 논문에서는 가공순서, 기계 ( 또는 작업) 특성과 같은 실제 제조 상황을 모델에 반영시키기 위해 새로운 network 표현 방법을 제시하며, machine grouping 문제는 0-1 quadratic programming 으로 수리모형화 된다. 그리고 quadratic 형태는 선형으로 변환되어 정수선형계획법을 이용하여 최적해를 구할 수 있음을 보인다.
또한 현실적인 크기의 machine grouping 문제를 다루기 위해 효율적인 발견적 기법이 제시된다. 여기에서 제시되는 발견적 기법은 기본적으로 Kernighan 과 Lin 의 2-way 균형 분할기법을 이용하고 있다. 그리고, 발견적 기법의 효율성을 보이기 위해 몇가지 실험결과를 제시하였다.
