In this thesis, the machine-part grouping problem in group technology (GT) manufacturing systems is considered. Many methods have been proposed to find mutually independent machine cells. Most of them usually assume that each part has only one fixed process routing which indicates the sequence of facilities used to process each part. Grouping problem with single routing is referred to the simple GT problem(SGTP) in this thesis.
However, this assumption may not be realistic in GT environment since each operation of a particular part may be performed on alternative machines. Grouping problem with multiple process routings is called the generalized GT problem(GGTP) in this thesis. The main concern of this thesis is to develop some methods for solving GGTP. The objective is to find the machine-part cells which attain the fewest intercellular moves of parts in a GT manufacturing systems.
First, a similarity coefficient method is proposed. Considering that the existing similarity coefficient methods which use the similarity coefficient defined between routings cause the critical problem in terms of the computational complexity, new generalized similarity coefficient defined between machines is suggested. The new coefficient includes existing machine similarity coefficient for solving SGTP as a special case and can handle both SGTP and GGTP. A reduction algorithm using the generalized similarity coefficient is developed. The algorithm resolves the machine chaining problem by incorporating multiple clustering criteria.
Second, reduced p-median models using integer programming are proposed. By introducing the new generalized similarity coefficient, new models include much smaller number of binary variables and constraints than the original p-median model given by Kusiak(1987). To heighten the solution quality in terms of the number of exceptional elements, two-stage approach reassigning the bottleneck or idle machines is established.
Third, a part-based assignment model using a simple linear program is proposed. By formulating the MPGP with simple assignment model, we can save considerable computation time compared with solving the p-median model which is an integer program. An algorithm using the optimal assign-ment solution at each stage is developed.
Last, integer linear and integer quadratic formulations which attempt to directly minimize the total number of exceptional elements are proposed. Different from the previous methods that rely on the similarity concept in order to group machines into cells and parts into families, the formulations deal directly with the exceptional elements. Two approximation models are suggested to solve the integer quadratic formulation.
본 논문은 그룹테크놀러지 생산시스템에서의 기계-부품 그룹핑 문제를 다룬다. 그룹핑 문제를 풀기 위해 많은 방법들이 제시되었는데 이들은 대개 하나의 부품에 대하여 오직 한 가지의 공정절차만이 있다는 가정하에서 그룹핑을 시도하였다. 그러나 실제로는 하나의 부품에 대하여 여러개의 공정절차가 설계될 수 있다. 여기서는 이러한 복수개의 공정절차가 존재하는 경우의 기계-부품 그룹핑을 해결하기 위한 방법들을 제시한다.
복수공정을 갖는 그룹핑 문제를 풀기 위한 기존의 방법들의 가장 큰 문제점은 부품사이에 정의되는 유사성계수를 이용함으로써 다루는 문제사이즈가 커진다는 점이다. 실제의 그룹핑 문제에서는 대개 기계수보다 부품수가 훨씬 많으므로 이것은 중대한 제약이 된다. 본 논문에서는 복수공정을 취급할 수 있는 기계 사이에서 정의되는 일반화된 유사성계수를 처음으로 제시한다. 기계 사이에서 정의되는 일반화된 유사성계수를 이용하여 휴리스틱 클러스터링 알고리즘을 제시한다. 기존의 클러스터링 알고리즘이 오직 하나의 기준을 이용함으로써 빈번히 Machine Chaining 을 야기하는 데 반하여 본 논문에서 제시되는 알고리즘은 매 단계마다 여러 가지 기준을 동시에 사용함으로써 이러한 문제점을 피하고 독립적인 기계그룹을 얻는다.
둘째로, 위에서 정의된 기계사이의 유사성계수를 이용하여 복수 공정의 그룹핑 문제를 푸는 p-median 모델을 제시한다. 이 모델은 Kusiak 에 의해 제시된 모델보다 훨씬 적은 수의 이진변수와 제약식을 갖는다. 독립적인 그룹핑을 방해하는 예외적인 원소수를 최소로하기 위해 bottleneck machine 을 재할당하는 2 단계 모델을 제시한다.
세째로, 그룹핑 문제를 간단한 선형계획문제인 할당문제를 이용하여 푸는 방법을 제시한다. 이것은 부품사이의 유사성계수를 이용하지만 순선형 계획문제이므로 정수계획문제인 p-median 모델보다 훨씬 적은 계산시간을 요한다. 매 단계에서 할당문제의 최적해를 이용하여 그룹핑을 시도하는 알고리즘이 제시된다.
네째로, 그룹핑문제를 풀기 위해 기계나 부품사이의 유사성계수를 이용하는 위의 방법들과는 달리 직접 예외적원소수를 최소로 하는 두 가지의 수리계획모델을 제시한다. 하나는 단일공정문제를 푸는 Boctor 모델을 복수공정문제로 확장한 선형정수계획모델인데 단일공정문제와는 다른 몇 가지 흥미 있는 결과가 제시된다. 다른 하나는 비선형정수계획모델인데 이것은 Boctor 모델의 목적함수를 이차함수로 표현해 본 것이다. 이를 풀기 위한 두 가지의 근사모델이 제시되는데 이것의 전체 최적해를 구하는 것은 얼마나 좋은 초기해를 발견할 수 있느냐에 달려있고 이는 미래의 흥미 있는 연구과제로 남겨진다.
